Около десятка лет группа учёных СГАУ работала над секретным правительственным проектом, целью которого был полёт русских космонавтов на Марс. Полёт совершенно случайно должен был состояться 12-го апреля 2011 года, но сроки уже подходили, а проект так и не был проработан полностью, хотя оставалось решить не так уж много вопросов.

Главной проблемой был вид топлива, который будет использован для приведения космического корабля в движение. Профессор X (очень известный сотрудник СГАУ) уже давно настаивал на изобретённом им «водородном черпаке», а его коллега профессор Y предлагал для верности использовать пару «керосин-кислород». Чтобы полёт не сорвался из-за этого спора, как это было с полётом на Луну, коллеги решили сыграть в игру, исход которой и должен был решить топливный вопрос.

Чтобы быть честными с собой, они поймали в коридоре первого попавшегося студента и попросили его сочинить им правила игры, в которую ещё никто не играл. Тот, немного подумав, высыпал из кармана на стоявшую неподалёку парту довольно большую кучу печенек и предложил немного упрощённую схему известной игры Ним.

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

Профессор X взглянул на кучу и мгновенно подсчитал количество печенек в ней. Он занимался математикой достаточно долго, чтобы не испытывать трудностей с устным счётом. Ему известно, что профессор Y очень умён и будет играть оптимально. Теперь и он хотел бы оценить свои шансы и придумать оптимальную для себя стратегию.

Профессор Y очень расстроился, програв профессору X в игру с печеньками, и захотел взять реванш. Профессор X согласился.

— Но где же мы возьмем печеньки? — спросил профессор X.

— Не беда, — ответил профессор Y, — мы их приготовим.

Сказано-сделано. Два профессора пошли в магазин и купили несколько килограммов теста. Придя в лабораторию, они раскатали тесто по столу и стали думать, какой же формы испечь печеньки.

В лаборатории нашлось 2 вида формочек для печенек: треугольная (подставка под призму) со сторонами $$$a$$$, $$$b$$$ и $$$c$$$ и круглая (оправа от линзы) с радиусом $$$r$$$. После того как печеньки были приготовлены, профессор Y предложил профессору X занимательную задачу: определить, пролезет ли круглая печенька в треугольную формочку и наоборот, пролезет ли треугольная печенька в круглую формочку. Печеньки были очень тонкими, и можно было пытаться протолкнуть их в формочки, как угодно поворачивая в пространстве.

Профессор X не был готов к такой задаче — еще бы, ведь он всю ночь готовился к игре, придуманной студентом! Поэтому он попросил Вас ответить на вопрос профессора Y.

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

Таким образом, чтобы получить возможность рулить космическим кораблём, космонавт, как и Юрий Гагарин в своё время, должен будет решить несложную логическую задачку. Эта задачка была придумана лично профессором X. Он сделал её посложнее, чтобы у космонавтов отпало желание вручную управлять кораблём, если только не произойдёт что-то действительно серьёзное. Компьютер случайно выдавал космонавту натуральное число $$$n$$$. Тот должен был на листочке быстро построить квадрат размером $$$n \times n$$$ клеток и вписать в клетки натуральные числа от $$$1$$$ до $$$n^2$$$ так, чтобы суммы чисел по столбцам, строкам и диагоналям квадрата были равны одному и тому же числу $$$m$$$. Далее, чтобы не тратить время на перерисовывание всего квадрата, он должен был ответить компьютеру получившееся число $$$m$$$. Теперь профессор X сам хотел бы узнать решение этой магической задачи, потому что ему надо написать программу, которая бы проверяла решение космонавта.

Космический корабль «Запад-1» был оснащён лазерной пушкой. Разумеется, вся команда учёных, работавшая над проектом полёта на Марс, была уверена, что космос — самое мирное место на свете, никаких злобных марсиан, сбивающих зонды, не существует, НЛО — просто старая разработка советских учёных, и вообще была против оружия в космосе. Но случаи бывают разные, так что рисковать не стали.

Перед полётом нужно было проверить программу, которой был оснащён модуль наведения. Модулю на вход подавались координаты и радиус некоторого сферического звездолёта в вакууме. Координаты были в некоторой универсальной трёхмерной системе, не привязанной к чему-то конкретному. Модуль наведения выдавал координаты некоторой точки, в которую следовало стрелять. Во время выстрела лазерная пушка образует луч между кораблём (его для простоты можно считать точкой) и указанной точкой. Луч начинается в точке дислокации корабля и распространяется в одну сторону приблизительно до бесконечности (во всяком случае, модуль наведения рассчитывает на это). Теперь нужно написать программу, проверяющую работу модуля наведения. Вражеский сферический звездолёт в вакууме считается поражённым, если лазерный луч пересёк его или хотя бы коснулся.

Поскольку постройка космического корабля для полёта на Марс контролировалась вышестоящими инстанциями, в его устройстве не обошлось без нанотехнологий и прочих инноваций. Корабль был снабжён $$$n$$$ ремонтными нанороботами размером с молекулу. Эти роботы находились во всех внутренних деталях корабля и невидимым образом чинили любые поломки. Казалось, будто поломка корабля затягивается сама собой, словно рана на теле живого существа.

На деле это работало вполне научно. Каждый из $$$n$$$ нанороботов мог за одну секунду либо починить одно наноповреждение (очень маленькое неделимое повреждение), либо построить из подручных средств копию себя (реплицироваться). Чтобы правильно распределить работу, нанороботы связывались с бортовым компьютером для координации действий. Но пока что необходимой программы на нём не было, и роботы занимались тем, что им приходило в голову.

Профессор X решил всё же написать такую программу, потому что начальство очень хотело, чтобы нанороботы непременно использовались. Суть программы в том, чтобы давать приказы отдельным роботам строить себе подобных или чинить корабль, в зависимости от числа имеющихся наноповреждений. Это число оценивается специальными датчиками жизнеобеспечения и передаётся программе. Естественно, нужно починить все повреждения как можно быстрее. Отдельной проблемой является то, что количество нанороботов и наноповреждений может быть очень большим.

Профессор X был обеспокоен состоянием энергогенераторов космического корабля «Запад-1». Затея питаться от энергии двигателей ему не очень нравилась, потому что до Марса путь совсем неблизкий, и может случиться всё, что угодно. Что, если на обратном пути топливо кончится? Космонавтам же придётся лететь всю дорогу до Земли без света, а это очень грустно и тоскливо: ни телевизор посмотреть, ни почитать книжку, ни послушать музыку.

Чтобы решить эту сложную проблему, профессор решил запитать всё электрооборудование космолёта от независимой системы генераторов, закупленных с запада (отечественные были слишком тяжёлые, как и всё отечественное). В документации к этим генераторам было указано, что $$$n$$$ генераторов за $$$m$$$ минут генерируют ровно $$$k$$$ Джоулей электроэнергии. Профессор знает, что для правильной работы всех бортовых устройств нужно, чтобы за $$$p$$$ минут было получено хотя бы $$$q$$$ Джоулей энергии. Теперь он хочет узнать наименьшее количество генераторов, которое ему нужно вмонтировать в космический корабль, чтобы это условие выполнялось.

Пока учёные готовили полёт на Марс, правительства уже начали делить территории на красной планете. Особенно русских исследователей волновала одна богатая на интересные места локация размерами $$$n \times m$$$ километров, разделённая на квадраты со стороной в 1 километр. Некоторые квадраты этой локации были очень важны российскому правительству, потому что в них по предположениям некоторых учёных могли быть нефтяные месторождения, залежи урана, секретные города марсиан и прочие интересные вещи. Эти квадраты при разделе территории непременно должны были отойти Российской Федерации.

Однако, мировое сообщество поставило условие: российское правительство может заявить за собой только некоторый прямоугольник, охватывающий некоторое количество квадратов, причём это не может быть вся локация целиком. Более того, это возможно только при условии, что в течение часа дипломаты смогут ответить на вопрос, сколько всего существует таких прямоугольных территорий, включающих все интересные квадраты. Теперь один важный человек из правительства позвонил на сотовый профессору X, чтобы тот помог ему ответить на этот вопрос и не дал отечественным дипломатам опозориться перед мировым сообществом.

Профессор X очень много курил. Он уже подумывал избавиться от этой вредной привычки, но никак не находил времени и желания. А с этим полётом на Марс он от волнения стал выкуривать по две пачки сигарет в сутки. При этом профессор по старинке пользовался спичками вместо зажигалки: он любил запах сгоревшей серы, ему казалось, это придаёт некоторый особый шарм процессу курения.

В последнее время спички стали кончаться почти так же быстро, как и сигареты. При этом профессор X очень рассеянный, поэтому постоянно забывает, в каком кармане у него лежит коробок, и лезет в один из двух карманов наугад. Кармана всего два, но всё равно неприятно каждый раз залезать в карман и обнаруживать его пустым. Чтобы этого избежать, как-то утром профессор купил два новых коробка по $$$n$$$ спичек в каждом и положил по коробку в каждый карман. Теперь возможность ошибиться карманом на время исключалась.

Тем не менее, не прошло и пары дней, как в самый ответственный момент профессор вытащил из кармана пустой коробок. Досада сразу же прошла, когда профессор задумался, сколько в среднем спичек может быть сейчас в коробке, который лежит в другом кармане.

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

Профессор, не долго думая, набросал на листочке несколько числовых ребусов, которые обычно дают решать детям на уроках математики, и хотел предложить их космонавтам. Но он столкнулся с проблемой, что сам не мог с ходу найти решения некоторых из них. Для ускорения процесса профессор X решил написать программу, которая будет решить ребусы за него.

Все ребусы профессора представляли собой задачи вида «a+b=c», где $$$a$$$, $$$b$$$ и $$$c$$$ — некоторые слова. Каждая буква слова может быть заменена на какую-либо цифру, причём в рамках одной задачи одна и та же буква обозначает одну и ту же цифру, а разные буквы — несовпадающие цифры. Решить задачу — значит подобрать такую замену всех букв на цифры, которое удовлетворяло бы названному условию и обеспечивало заданное равенство. Разумеется, найти нужно все решения. Получившиеся в результате замены числа могут содержать ведущие нули.

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

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

Работает эта система следующим образом: сначала наногенератор создаст $$$n$$$ цепей из сверхпрочных плазменных колец, которые в дальнейшем соединятся в единую цепь и пристыкуются к кораблю «Запад-1». Чтобы соединить 2 цепи между собой, должен сначала активироваться вскрыватель, который вскрывает какое-нибудь кольцо на какой-либо цепи и отсоединяет его от этой цепи. Затем в дело вступает соединитель, который притягивает два конца каких-либо цепей в только что открытое кольцо. А потом закрыватель закрывает вскрытое кольцо.

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

Уже ближе к концу приготовлений к полёту на Марс было решено переустановить операционную систему на бортовых компьютерах космического корабля «Запад-1». Дело в том, что на нём стояла операционная система Doors, которая предназначалась для домашних компьютеров и поэтому была сделана не на совесть. Центр управления полётами СГАУ уже потерял два спутника: один упал и не поднялся, а другой и вовсе завис на орбите вопреки всяким физическим законам. Предположительно это связано именно с операционной системой.

На компьютеры было решено поставить операционную систему Lin OS X, но систему Doors тоже было решено оставить для надёжности, к тому же за неё уже были уплачены немалые деньги. Чтобы система Lin OS X работала лучше, было решено удалить всё ПО, которое установлено в системе Doors. Однако это оказалось не так-то просто, потому что для удаления одной программы было необходимо наличие другой программы, а то и не одной. Это была особенность системы Doors.

Профессор X с коллегами долго мучился над удалением программ, ведь работа системного администратора не была для них родной. В конце концов он решил подойти к проблеме с научной точки зрения. Он занумеровал программы, провёл тщательное исследование зависимостей и для каждой программы установил набор программ необходимый, чтобы её удалить. Осталось только определить, в каком порядке нужно удалять программы, чтобы без сожаления удалить их все. Если ничего не выйдет, оставался вариант с форматированием жёсткого диска, но у профессора X на бортовом компьютере хранились фотографии с последней поездки в Санкт-Петербург, и он не хотел их потерять.

Незадолго до вылета на Марс учёные вспомнили, что ещё не настроен модуль, обеспечивающий канал связи с Землёй. Без этого модуля космонавты не смогут передавать информацию о состоянии корабля и сидеть в Интернете, так что модуль нужно было срочно настроить.

Модуль был сконструирован полвека назад, ещё к первому вылету в космос, так что для его настройки использовались результаты, выдаваемые функцией на каком-то старом языке программирования очень высокого уровня, синтаксис которого никто не знал, а компилятора никогда не видел. Готовая реализация этой функции была только для ЭВМ «Урал-1», но в музее вычислительной техники признались, что потеряли куда-то все внутренности этой машины, поэтому выглядит она хорошо, но вычислять уже ничего не может. Однако профессору X удалось раздобыть исходный код этой функции. Он выглядел так:

функция фуу(а: целое; б: целое): логическое;
переменные
    в: целое;
начало
    в := б;
    пока в > 0 делай начало
        в := в - а;
    конец;
    верни (б == 1) или
          (а < б) и (не (а == 1) и (в == 0) или фуу(2 * а, б) или фуу(2 * а + 1, б));
конец;

Учёных интересовал результат работы этой функции при а = 1 и б = ($$$k$$$ + 33931086844518982011982560935885732032396635556994207701963662088123265 31417633033625453597120718116969886858499194160778011107392823626119960 4691797570505851011072000000000000000000000000000) (это одно число, просто оно не поместилось на одной строчке), где $$$k$$$ принимает целые значения из определённого интервала. Учёные знают, что неизвестный язык программирования был настолько высокого уровня, что целочисленного переполнения в нём не было.

Обычный полёт на Марс с использованием топливных двигателей занял бы несколько лет. Понятно, что учёным не хотелось бы ждать так долго, поэтому у них был план. Не так давно астрономами СГАУ был открыт принципиально новый способ перемещения, основанный на пространственных разломах. В определённых областях необъятной Вселенной имеются так называемые провалы в пространстве, позволяющие вопреки законам теории относительности перемещаться на огромные расстояния за пренебрежимо малое время. Такие области учёные назвали кротовыми норами. Две кротовые норы могут быть не соединены вообще, соединены гиперпространственным переходом, либо соединены нуль-переходом, причём такие соединения могут быть односторонними. В любом случае, добравшись до одной из кротовых нор, космический корабль сможет перемещаться между ними, затрачивая малое количество энергии. Если из одной норы в другую ведёт гиперпространственный переход, то переместиться между ними в заданном направлении космический корабль сможет за один античас. На корабле это перемещение действительно займёт примерно час. Если же из одной кротовой норы в другую ведёт нуль-переход, то корабль и вовсе может переместиться по нему без временных затрат: происходит мгновенный обмен участками пространства с другой норой.

Всего учёным известно положение $$$n$$$ кротовых нор и связи между ними. Все норы занумерованы. По плану космический корабль «Запад-1» доберётся до кротовой норы номер $$$1$$$, которая ближе всего находится к Земле, а дальше, перемещаясь по ним, будет стремиться попасть в нору номер $$$n$$$, которая находится ближе всего к Марсу. Теперь учёные хотели бы проложить маршрут перемещения между этими норами, чтобы время, потраченное космонавтами на перемещение, было минимальным. При этом учёные считают маршрут заведомо плохим, если корабль посещает одну и ту же нору дважды.