Лучшее - детям. Знак качества
Краевое государственное общеобразовательное автономное учреждение
Центр образования "Эврика"
  • :
  • :
Первоапрельский контест. Разбор задач.

Первоапрельский контест. Разбор задач.

Дата проведения:
01 апреля 2020 года
Место проведения:
В домашних условиях.


Турнир завершен, спасибо всем за участие!

Краткая статистика: приняло участие 33 программиста, решили хотя бы одну задачу — 18, все задачи — 8.

Турнирная таблица:

Приятной неожиданностью стало участие в турнире Геннадия Короткевича, многократного победителя международных и всероссийских чемпионатов и турниров по спортивному программированию. Международному Гроссмейстеру (по версии codeforces) хватило полтора часа, чтобы закрыть все мишени. Я попросил Геннадия дать краткий feedback, он не отказал в любезности.

Краткий разбор задач:

При решении всех задач следует иметь в виду, что школьного курса математики / информатики совершенно достаточно для их решения. Кроме того, автор заинтересован в том, чтобы задачи были решены, поэтому следовало внимательно искать подсказки в тексте условия. Вся необходимая информация была участникам предоставлена. Впрочем, брутфорс тоже никто не отменял.

A) Безусловная задача. Что же это за функция (известная даже школьникам, которую можно полностью восстановить по трём точкам)? Точно не линейная и не показательная, как могло показаться на первый взгляд. По трём точкам можно восстановить проходящую через них окружность (и вывести соответствующую формулу, но тогда для некоторых значений x не будет никакого значения y или будет сразу 2 значения). График какой ещё функции можно восстановить по трем точкам? Квадратичной!

Получаем систему из трех уравнений:

При x = 3, y = 8: a * 3^2 + b * 3 + c = 8

При x = 4, y = 16: a * 4^2 + b * 4 + c = 16

При x = 5, y = 32: a * 5^2 + b * 5 + c = 32

После несложных арифметических преобразований получаем, что a = 4, b = -20, c = 32. Восстанавливаем квадратичную функцию: y = 4 * x * x — 20 * x + 32.

Геннадий Короткевич: A — не слишком интуитивно, но логика есть. Понял только после того, как подобрал ответы на 1, 2, 6 и 8.

B) Иррациональная задача. Да, системы счисления с иррациональными основаниями действительно существуют и применяются на практике. В рамках школьного курса они не изучаются, но догадаться, что натуральное число при переводе в систему счисления с таким основанием не должно иметь других цифр кроме нуля на всех местах, соответствующих нечетным степеням основания – достаточно легко. В данном примере достаточно перевести число в двоичную систему счисления и вставить нули между каждой парой цифр в получившейся записи.

Геннадий Короткевич: B — простая задача, которая имела бы больше всего шансов попасть в обычный контест.

C) Схематичная задача. Зашифрованы преобразования с битами двоичной записи исходной записи натурального число. Пространства для маневра мало, где спряталась какая логическая функция – многие догадались с первого раза.

Геннадий Короткевич: C — хорошая обучающая задача для школьников, чтобы погуглили и разобрались в схемах.

D) Сладкая задача. Простая проблема для любого, кто знаком с теорией игр (изучается на уроках информатики). В данном примере работает принцип чётности – у Тимофея имеется единственная возможность не проиграть: забрать первым ходом целиком всю третью кучу, а потом просто зеркально повторять ходы папы. Любая другая стратегия приведет к его поражению, а при указанном подходе Тимофей победит и неизбежно соберет a + b конфет. А плюс Б, где-то я уже это встречал…

Геннадий Короткевич: D — неплохая задача-шутка про игры.

E) Беспримерная задача. Приведенная в условии единственная фраза на первый взгляд совершенно не нужна и информационно бессмысленна. Стоит приглядеться к ней! Если взять первые буквы всех её слов, получится «тетрафобия» — боязнь цифры 4. Дальше – просто, если в приведенном числе есть такая цифра – выводим YES, иначе – NO.

Геннадий Короткевич: E — не нашёл в условии подсказок, за 10 сабмитов выяснил все тесты и ответы на них, постфактум понял принцип (но мог и не понимать, а задачу всё равно сдать).

F) Первоапрельская задача. Здесь подсказка в названии задачи. Было задумано вполне себе первоапрельское число 1,04. Большинство решивших использовало брутфорс, но были и те, кто догадался.

Геннадий Короткевич: F — позабавила больше всего :) долго не мог понять, что надо не верить своим глазам и примеру.


Ещё раз спасибо всем! Надеюсь собраться с силами и организовать еще один Первоапрельских контест через год!


Краткий разбор задач пробного тура:

В первой задаче подсказка заключалась в названии: Маски фонетически схожи с ASCII. Определяем коды букв, входящих в данное слово и суммируем их.

Во второй задаче подсказка заключалась во фразе про 10 типов людей. Переводим входные двоичные числа в 10-ю систему счисления и видим, что число в выводе соответствует его длине.

В третьей задаче подсказка заключалась в первом примере. Строка qwerty примечательна тем, что расположена на одном горизонтальном ряду стандартной клавиатуры. Все остальные примеры — тоже.


Первоапрельский контест – несерьёзное соревнование по спортивному программированию, где догадаться, чего от Вас хочет автор задачи, как правило, гораздо сложнее, чем написать код решения.

Такие контесты стали уже традиционными на codeforces.ru (их там прошло уже 8, список внизу, возможно виртуальное участие), программисты всего мира с удовольствием ломают головы над неполными условиями, загадочными картинками и примерами тестов, в которых, на первый взгляд, нет никакой логики.

Попробуем сыграть в подобный контест и мы ;-)

Вам предлагается потренироваться на трех задачах пробного тура. Сроки проведения этого турнира – весь март. Основной тур состоится первого апреля (а Вы как думали?), в течение 24 часов Вам будет предложено 6 (а может и больше) задач.

Что нужно иметь в виду… Автор задач заинтересован в том, чтобы Вы решили задачу, поэтому ищите подсказки в условиях, названии и примерах тестов задачи. Кроме того, понимая, что этот турнир ориентирован в первую очередь на школьников, для решения задачи не нужно применять высшую математику. Автор совершенно не возражает, если Вам будут помогать мама с папой, учителя физики и физической культуры, а также Google с Яндексом.

Вместе с тем, автор совершенно не заинтересован, чтобы задача была решена с первой попытки (хотя это не исключено).

Удачи, успехов и уверенности в завтрашнем дне дурака!

Кстати, у Вас вся спина #ffffff…


Карабанов Антон Викторович.

Вопросы и проклятья после 101-й неудачной попытки сдачи задачи можно присылать сюда: akar_@mail.ru

Спортивное программирование в Камчатском крае.


Список первоапрельских турниров на codeforces.ru:

https://codeforces.com/contest/171

https://codeforces.com/contest/290

https://codeforces.com/contest/409

https://codeforces.com/contest/656

https://codeforces.com/contest/784

https://codeforces.com/contest/952

https://codeforces.com/contest/1145

http://codeforces.com/contest/1331

10:45
3322

Нет комментариев. Ваш будет первым!