Рубрика «Занимательные задачки»

Спасибо всем, кто уже принял участие в нашем конкурсе по программированию! Мы получили 60 решений от 34 уникальных участников. До конца конкурса осталась одна неделя (до 17 августа 2017, 23:59:59 UTC), и мы публикуем последние предварительные результаты.
Читать полностью »

image

Нашумевшие события последних месяцев наглядно показывают, насколько актуальной является проблема критических уязвимостей в программном обеспечении. Массовые атаки на пользователей с помощью вирусов-шифровальщиков WannaCry и Petya осуществлялись путем удалённой эксплуатации уязвимостей нулевого дня в сетевых сервисах Windows – SMBv1 и SMBv2. Нахождение и эксплуатация уязвимостей для удаленного выполнения кода – задачка явно не из легких. Однако лучшим из лучших специалистов по информационной безопасности всё по зубам!
В одном из заданий очного тура NeoQuest-2017 необходимо было найти уязвимости в доступной по сети программе-интерпретаторе команд, и с помощью их эксплуатации выполнить код на удаленном сервере. Для доказательства взлома нужно было прочитать содержимое файлового каталога на сервере – там, по условию, размещался ключ задания. Участникам был доступен бинарный файл интерпретатора. Итак, лёд тронулся!
Читать полностью »

«Я экспериментировал с задачами кубического представления в стиле предыдущей работы Эндрю и Ричарда Гая. Численные результаты были потрясающими…» (комментарий на MathOverflow)

Вот так ушедший на покой математик Аллан Маклауд наткнулся на это уравнение несколько лет назад. И оно действительно очень интересно. Честно говоря, это одно из лучших диофантовых уравнений, которое я когда-либо видел, но видел я их не очень много.

Я нашёл его, когда оно начало распространяться как выцепляющая в сети нердов картинка-псевдомем, придуманная чьим-то безжалостным умом (Сридхар, это был ты?). Я не понял сразу, что это такое. Картинка выглядела так:

Математический детектив: поиск положительных целых решений уравнения - 1
«95% людей не решат эту загадку. Сможете найти положительные целочисленные значения?»

Вы наверно уже видели похожие картинки-мемы. Это всегда чистейший мусор, кликбэйты: «95% выпускников МТИ не решат её!». «Она» — это какая-нибудь глупая или плохо сформулированная задачка, или же тривиальная разминка для мозга.

Но эта картинка совсем другая. Этот мем — умная или злобная шутка. Примерно у 99,999995% людей нет ни малейших шансов её решить, в том числе и у доброй части математиков из ведущих университетов, не занимающихся теорией чисел. Да, она решаема, но при этом по-настоящему сложна. (Кстати, её не придумал Сридхар, точнее, не он полностью. См. историю в этом комментарии).

Вы можете подумать, что если ничего другое не помогает, то можно просто заставить компьютер решать её. Очень просто написать компьютерную программу для поиска решений этого кажущегося простым уравнения. Разумеется, компьютер рано или поздно найдёт их, если они существуют. Большая ошибка. Здесь метод простого перебора компьютером будет бесполезен.
Читать полностью »

Гремлины и ELFийская магия: а что, если ELF-файл — это контейнер? - 1 Мы, дети 90-х, любим добавить в задания NeoQUEST что-нибудь олдскульное. В этом году нам вспомнились гремлины, и мы добавили их в легенду одного из заданий соревнования «Очной ставки» NeoQUEST-2017.

Однако, под внешне забавной легендой скрывается вполне себе реальная практическая задача: а что, если привычные ELF-файлы — не просто исполняемые файлы, а контейнеры, открыть которые нам предстоит? Для этого придется испытать довольно-таки обширные возможности objcopy и освежить в памяти организацию ELF-файла.

Чтобы вычислить подозрительные секции, необходимо представлять секционный и сегментный состав типичного ELF. Помимо этого, конечно, пригодится и опыт — например, общение с firmware embedded-систем вполне может подсказать подходящие идеи!

Думаете, готовы на 100%? Уверены, что гремлинам удастся вас удивить спрятанными архивами, попорченными таблицами символов, а также аудиофайлами, которые зазвучат только в руках умелого мастера! Под катом — исходники к заданию и прохождение, чтобы каждый читатель Хабра мог собственноручно попробовать пройти задание!
Читать полностью »

На днях завершился Яндекс.Алгоритм 2017 — наш чемпионат по спортивному программированию. В финальном раунде 25 финалистам нужно было за два с половиной часа решить шесть задач. Первое место вновь завоевал Геннадий Короткевич из питерского ИТМО — это уже четвёртая его победа после состязаний 2013, 2014 и 2015 года. Никола Йокич из Швейцарской высшей технической школы Цюриха и выпускник Университета Токио Макото Соэдзима стали вторым и третьим, повторив свои прошлогодние результаты. Вот как распределились денежные призы: победа — 300 тысяч рублей, второе место — 150 тысяч, третье — 90 тысяч.

Разбор задач финала Яндекс.Алгоритма 2017 - 1

Заявки на участие в Алгоритме 2017 подали 4840 человек. Более 60% из них — россияне. На втором месте по количеству заявок — Беларусь, далее следуют Украина, Индия и Китай. В общей сложности на чемпионат зарегистрировались жители нескольких десятков стран, включая Сингапур, Камерун, Венесуэлу и Перу.

Мы по традиции публикуем формулировки и разобранные решения задач финала.Читать полностью »

Объявление: срок приёма решений продлевается до 17 августа.

Спасибо всем, кто уже принял участие в нашем конкурсе по программированию! Мы получили 39 решений от 26 уникальных участников. Публикуем новые промежуточные результаты.
Читать полностью »

Спасибо всем, кто уже принял участие в нашем конкурсе по программированию! Приём решений ещё не окончен, но мы решили протестировать те решения, которые нам уже прислали, и опубликовать промежуточные результаты. Пока что мы получили 10 решений от 11 уникальных участников. Мы надеемся получить ещё много решений, поэтому итоговые результаты могут сильно отличаться от этих. Если нам пришлют достаточно много новых решений, проведём ещё одно промежуточное тестирование.

Читать полностью »

Несколько месяцев назад я получил от друга такое письмо:


Тема: Можешь развернуть и объяснить мне эту одну строчку кода?

Текст:Считай меня тупым, но… я не понимаю её и буду благодарен, если растолкуешь подробно. Это трассировщик лучей в 128 символах. Мне кажется, он восхитительный.

<pre id=p><script>n=setInterval("for(n+=7,i=k,P='p.\n';i-=1/k;P+=P[i%2?(i%2*j-j+n/k^j)&1:2])j=k/i;p.innerHTML=P",k=64)</script>


Эта строчка JavaScript отрисует анимацию, которая показана на изображении под катом. В браузере она запускается здесь. Скрипт написан автором www.p01.org, где вы можете найти эту и много других классных демок.
Читать полностью »

Первая часть публикации вызвала определённый интерес, пришёл ряд откликов, среди которых есть один, который хочется отметить особо: «жаль, нельзя скачать с гитхаба половину автомата и допилить под свою задачу, все надо делать самостоятельно. Если бы был некий стандарт записи автомата в какой-нибудь xml, позволяющий обмен автоматными алгоритмами, плюс некая «стандартная библиотека», возможно, все бы было иначе […] речь идёт о выдумывании какого-то «обобщенного состояния» и «обобщенного автомата», построении библиотеки таких автоматов с возможностью их комбинировать так же просто, как вызываются функции в языках». Отвечу читателю и всем, кто знаком с темой программных автоматов, но не удовлетворён нынешним положением дел (а оно в целом неудовлетворительное): мы обратимся именно к такой постановке вопроса, после того как будет достаточно очерчен предмет разговора.
Сегодняшняя статья посвящена теоретическим, идейным и психологическим аспектам автоматов. Рассмотрев их, мы снова вернёмся на прагматические позиции, которые были заявлены в начале цикла публикаций.

Читать полностью »

В этой публикации началось рассмотрение интересной задачки — отношения соседних чисел в обобщенном ряду Фибоначчи (в котором каждый следующий член оказывается равен сумме $inline$k$inline$ предыдущих.

К сожалению, задачка не была доведена до логического окончания, и брошена при неполном ответе для случаев 3 и 4.

Просто чтобы закрыть тему, рассмотрим ряд, образованный рекуррентным соотношением

$$display$$f_n= sum_{i=n-k-1}^{n-1}f_i$$display$$

Читать полностью »