Звонит будильник. Вы медленно открываете глаза.
На ваших ручных электронных часах 9:45; идёт шестьсот восемьдесят третий сóл экспедиции на Эрузум — далекую безжизненную планету, находящуюся в двойной системе на краю седьмой галактики. Вы встаете с кровати после глубокого сна, содержание которого, впрочем, уже забылось. Подойдя к иллюминатору и вглядевшись вдаль, вы замечаете слабое фиолетовое свечение. «Должно быть, мы приближаемся к туманности Цхеори», — думаете вы.
Выйдя в узкий длинный коридор из уютной каюты, вы видите, что кто-то снял с пола алюминиевую плитку, раньше его покрывавшую, и разбросал вокруг. «Наверняка хотят установить новые электросистемы, — предполагаете вы, — вроде бы Григорий жаловался на перебои в питании освещения несколько сóлов назад... Надо будет узнать». Вы аккуратно проходите по краю коридора, чтобы не задеть провода, и добираетесь до кухни. Весёлые Илья и Виктор играют в какую-то увлекательную игру.
Подойдя к столу поближе и поздоровавшись с товарищами, вы начинаете внимательно наблюдать за игрой: на столе лежат несколько кучек из талафановых хлопьев, размер которых идеально подходит для быстрого визуального пересчета. Игроки по очереди берут из одной кучки сколько-то хлопьев и убирают их со стола. Количество, по всей видимости, определяется каждым игроком самостоятельно, но пропускать ход нельзя.
– Витя, напомни, кто побеждает? — говорит забывчивый и неуверенный Илья.
– Тот, кто не сможет сделать ни одного хода, — отвечает Виктор.
«Ага!», — с энтузиазмом произносит ваш внутренний голос. — «Теперь я точно смогу предугадать, кто из них выиграет и как — не зря же я изучал теорию игр на 18-ом курсе!» Достав карманный лэптоп, вы запускаете CLion и выбираете C++ 317-ого стандарта. Со времен первых версий языка утекло много воды, и теперь в нем отсутствуют операторы new и delete, любые управляющие конструкции — if, else, for, while, do, switch, goto, — нет директивы препроцессора define, доступны только литералы -1, 0, 1, true, false и типы ssize_t, size_t и bool. Кроме того, размер файла с кодом не должен превышать 5Кб, иначе компилятор откажется его компилировать: недавно представители зеленой фракции в сенате предложили новый законопроект по защите природы и космоса, включающий в себя пакт о регулировании расхода вычислительных ресурсов. По этой же причине любой язык программирования, позволяющий писать исполняемые (а не compile-time) программы, оказался вне закона.
Вы с легкостью составляете программу из нескольких шаблонных структур, их специализаций и перегрузок. Достав запрещенную runtime-карту, вы вставляете ее в лэптоп. Программа исполняется на входных данных, состоящих из размеров кучек на столе.
– Илья, кажется, побеждаешь! Забирай из третьей кучки десять хлопьев. Не прогадаешь, — с довольной ухмылкой заявляете вы и выходите в коридор.
«Ладно, надо бы добраться до капитанского мостика и обсудить с Григорием плитку. Может, предложить ему какой-нибудь экзотический способ замостить ею коридор? Кстати, а сколькими способами это вообще можно сделать?» Любопытство берёт верх над целеустремлённостью, вы вновь достаёте лэптоп. Изучаете некоторое время плитку, которая есть на корабле, и пишете программу, вычисляющую число способов замостить коридор N на M плитками 1 на 2 метра; при этом известно, что ширина коридора меньше шести метров, а длина меньше ста. Попытавшись запустить программу, вы обнаруживаете, что это гигантское число не может быть вычислено в compile-time, поэтому решаете найти ответ по модулю 1000000007 . Утолив любопытство, вы идёте дальше к капитанскому мостику.
Преодолев массивные шлюзовые двери, вы попадаете в большое круглое помещение. В центре — капитанское кресло, за которым, как всегда, — Григорий. Почему-то сейчас он чем-то озадачен.
– Гриша, привет! О чем задумался? — вежливо спрашиваете вы.
– И тебе здравствуй. Как всегда, решаю важные вопросы, – отвечает Григорий.
– Я видел плитку в коридоре. Опять перебои с электричеством?
– Уже прекратились: рано утром техники сняли плитку и поставили новые аттракторы из композита иридия. Теперь напряжение стабильное. Они бы с удовольствием положили плитку на место, но я попросил помочь мне с другой проблемой.
– Что случилось?
Григорий махнул головой в сторону голографической карты местной группы звёздных систем, у которой столпился техперсонал.
– При составлении маршрута ученые не учли область повышенной концентрации темной материи — у нас не выйдет пройти мимо Тау Алифии и достичь Дзеты Кетара по текущему маршруту. Фиолетовое свечение за иллюминатором усиливается, темная материя реагирует на кварк-глюонное поле корабля и выделяет свободные фотоны. Придётся искать новый путь.
– Так в чем проблема? У нас же есть подробная карта. Давай уберем лишние отрезки, соединяющие звезды, и составим новый путь.
– Отрезки мы уже убрали, а с путём проблема: программа вычисления маршрута попала в санкционный список, пришлось деактивировать.
Вы насупились, однако, немного подумав, достали лэптоп и заявили Григорию, ухмыляясь: «Не зря же я у нас в команде единственный плюсовик!» Тот наклонил голову от удивления, свёл брови и стал наблюдать за тем, как вы пишете стоя.
Спустя несколько часов работы вам удаётся создать идеальную программу для вычисления подходящего маршрута. Эта задача оказалась существенно труднее, чем предыдущие — вы даже использовали в паре мест запрещенные тернарные операторы, без них было бы совсем тяжко. С чувством выполненного долга вы оставляете лэптоп с кодом и новым построенным маршрутом удивленному Григорию и идёте завтракать.
Пока вы работали, персонал уже разложил в коридоре плитку. С удовольствием пройдя по ровному полу коридора, вы заходите на кухню. В ту же секунду радостный Илья восклицает: «Ура!» и выпрыгивает из-за стола.
– Ну что, выиграл?
– Спасибо, я и не думал, что твой совет действительно поможет! — радостно говорит он.
– Требую реванш! Вы пользовались подсказками, – возмущенно гаркает в его сторону Виктор.
– Как-нибудь в другой раз. Давайте позавтракаем? Сегодня я готовлю.
Илья встаёт и принимается варить хлопья. Вы садитесь за стол и утешаете растерянного и разбитого Виктора.
Через несколько минут Илья ставит на стол приборы и три тарелки с ароматной талафановой кашей, предварительно включив национальный гимн седьмой галактики, который по традиции слушают все жители этого чудестного места перед трапезой и сном. Вы задумываетесь о своём утреннем сне. Кажется, вы его вспомнили...
Прежде чем приступать к решению, рекомендую посмотреть видео по этой задаче на моем YT-канале по ссылке.
Задача представлена в треx вариантаx. Стоимости: 3, 5, 7 баллов соответственно.
На решение задачи у вас 7 дней.
Решения сданные позже 23:59:59 20 Ноября 2020 года не принимаются.