— Черный‑3 вызывает Око.
— Око на связи, видим ваше передвижение, Черный‑3
Именно с этого и начался диалог некогда полковника Российской Империи, а после ядерного удара просто наемника и бывшего ветерана Ивана Демина. Текущее задание сулило военному огромную награду — целых 15 000 послевоенных рублей, а нужно было все‑того добраться в радиоактивном лесу до определенных координат и забрать груз. Проще простого!
Задачу упрощало то, что наниматель помогал картинкой с одного из немногих уцелевших спутников. Именно с оператором этого спутника, откликавшимся на позывной «Око», и был сейчас диалог.
— Око, я в 500 от координат, выхожу на поляну. Покажи мне локацию, — попросил военный.
— Там все чисто, Черный‑3, даю картинку, — расслабленно ответил дежурный.
Но внезапно…
— Стоп! Черный‑3, оставить выход на локацию, приготовиться к бою! Там еще один мутант, а может, и не один! Б...я, и с другой стороны! Красный код! Красный код! Танцуем, Черный‑3!
Вот и поворот сюжета — придется вести тактический бой с мутантами, наступающих с обоих флангов.
Вы — Око, и вам необходимо помочь Ивану Демину выиграть это противостояние. Нужно давать Ивану грамотные команды, имея спутниковую картинку и наблюдая как движения бойца, так и движения мутантов. Всю поляну можно поделить на условные сектора-гексы, общий размер поляны — NxN. Противоборствующие стороны будут совершать действия по очереди, занимая любой свободный сектор на поляне. Победу одержит тот, кто построит непрерывную линию соединенных секторов-гексов с одной стороны поляны на противоположную (т. е. мутанты — если объединятся, а Иван — если проложит дорогу к оружию).
Помимо этого, необходимо отработать следующие гипотезы для обогащения базы знаний о мутантах:
1. Доказать, что военный сможет выиграть при любом N.
2. Описать стратегию поведения бойца при N = 7.
3. Описать стратегию бойца для любого N.
Представьте город, окруженный бесплодной равниной, оставленный в руинах после апокалипсиса. Ветер несет облака дыма и тлеющего пепла, скрывающего улицы в бледно-оранжевом тумане. У входа в город из этого тумана появляется человек, уставший, но уверенный в себе, обернутый в лоскутную маску, чтобы защитить лицо от палящего солнца. Он останавливается, поднимает свои пилотные очки и осматривает город, через который нужно пройти. Следы произошедших событий говорят ему, что в городе нет парков, по аллеям которых было бы приятно прогуляться в выходной день. Здесь он — добыча для тех, кто поддался животным инстинктам, и если провести слишком много времени на земле, можно распрощаться с жизнью. Самый безопасный маршрут через город — по крышам.
Темный силуэт неровного горизонта города может быть представлен как ломаная линия. Пики этой линии расположены в координатах (x1, y1), (x2, y2), ..., (xN, yN), xi < xi+1, а длина крыши L = 1. Наш оставшийся в живых, Илай, добрался до своей первой крыши и стоит в точке (x1, y1). Его задача — добраться до точки (xN, yN). У Илая нет средств передвижения, кроме его рук и ног. Он должен пересечь город вдоль ломаной линии, используя пожарные лестницы, чтобы подняться по зданию с одной стороны и спуститься с другой. Единственный подручный инструмент Илая — крюк для захвата, который он может использовать для соединения двух крыш веревкой: строго от крыши до крыши.
Веревка не может пройти через здание. Длина одной веревки ограничена R. Длина катушки с веревкой — K. После каждого применения крюка использованный канат остается сзади и не может быть повторно задействован. Каково кратчайшее расстояние, которое должен пройти Илай, чтобы добраться до (xN, yN), учитывая, что порой ему придется рисковать, проходя по улице?
Входные данные
Программа получает на вход натуральное число N (2 ≤ N ≤ 64); число R (0 ≤ K ≤ 10000), которое представляет максимальную длину одной веревки; число S (R ≤ S ≤ 10000), которое представляет общую длину всех веревок, собранных вместе (длина катушки); координаты (x1, y1), (x2, y2), ..., (xN, yN). Все координаты являются действительными числами, не превышающими 10000, для всех значений i от 1 до N-1 справедливо условие xi < xi+1.
Выходные данные
Программа должна выдать число — минимальное расстояние, которое должен преодолеть Илай (с учетом улицы и крыш). Ответ должен иметь точность до 5 знаков после запятой.
Внутри одного из когда‑то офисных зданий кипела работа — группа хорошо вооруженных людей четко и скоординировано завершала подготовку к какой‑то очередной операции.
— Смотритель, посылка почти готова, куда отгружаем? — сказал в эфир один из свободных вояк, находившийся под самой крышей здания.
— Гильза, ты достал уже, спускай куда-нибудь уже эту гребаную бомбу! Все собрали? С меня спрашивают, где товар, — раздраженно ответил человек с позывным «Смотритель».
— Ну куда-нибудь мы ее точно спустим. Кардинал, Гидрант слышали, что босс говорит? Спускайте эту дуру вниз на лифте, — ответил первый.
Следующие несколько минут двое не без усилий загружали вакуумную бомбу в самую обычную тележку. Вроде все шло хорошо, но…
— Эй, Гильза, а это нормально, что она пикает и красненьким мигает? Тут еще время текущее показывает. Ой, это не текущее, кажись! 58:59 … 58:58, — смущенно выдал в эфир тот, кого назвали Гидрантом.
— Идиоты! Вы что, бомбу активировали??? Всему отряду покинуть территорию! Сворачиваемся и уходим, тут через 59 минут все в радиусе километра засосет! — заорал Смотритель.
Несмотря на экстренную ситуацию, все продолжали четко действовать согласно каким‑то своим внутренним правилам, и даже Гидрант, которого наверняка потом пристрелят свои же, помогал собирать оборудование, чтобы быстро покинуть здание. Контракт сорван — пора сматывать удочки, пока имперские вояки не нагрянули забирать товар.
В здании сейчас находится n человек. Для слаженной эвакуации требуется провести моделирование отхода всей команды из здания через первый этаж.
На каждом этаже могут работать люди, ожидающие эвакуацию. Когда очередной вояка подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван, либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, лифт могут ожидать и другие.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если несколько вызовов поступает одновременно, активным становится вызов от вояки с наивысшим рангом в иерархии и, соответственно, наименьшим порядковым номером. Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже ожидает на этом этаже, и лифт отправляется вниз на первый этаж со скоростью один этаж в секунду. При движении вниз лифт останавливается на тех этажах, с которых на момент проезда мимо этого этажа был сделан вызов. Все ожидающие лифт заходят в него, и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все выходят из лифта, а лифт ожидает следующего вызова.
Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов, активируется вызов, который поступил раньше других. Если несколько вызовов поступило одновременно, активируется вызов согласно озвученной ранее иерархии. Лифт продолжает обслуживание описанным образом, пока все эвакуируются.
Будем считать, что все входят и выходят из лифта мгновенно: вакуумная бомба — это вам не шутки. Каждую секунду сначала вояки подходят и вызывают лифт, а затем лифт выполняет свое действие (перемещается на соседний этаж, сажает или выпускает, принимает решение, на какой вызов отправиться). Требуется провести быструю симуляцию с использованием подручных компьютерных систем, которая по описанию вызовов лифта для каждого вояки определяет, в какой момент он окажется на первом этаже.
Данные для симуляции
Первая строка входных данных содержит целые числа n и m — количество вояк, вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109). Следующие n строк описывают вояк, i-я из этих строк содержит два целых числа ti и ai — секунду, в которую i-й вояка подходит к лифту, и номер этажа, на котором это происходит (1 ≤ t1 ≤ t2 ≤... ≤ tn ≤ 109, 2 ≤ ai ≤ m).
Результаты симуляции
В результатах должны содержаться n целых чисел, для каждого вояки требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
С момента последнего ядерного удара по территории Российской Империи прошло уже шестнадцать лет. Сейчас территория рядом с одним из бывших мегаполисов больше похожа на сцену из фильмов ужасов, а не на когда‑то величественный город с многомиллионным населением. Однако и сейчас в городе есть выжившие — отчаянные личности, искатели приключений, воры, разбойники, сталкеры, наемники и еще целая россыпь странных и опасных группировок, единственной целью которых является выживание в этих суровых условиях, когда за любой ресурс нужно сражаться, вырывая его из рук конкурентов.
Вы давно уже примкнули к группировке «Красная заря». В целом группировка старалась не совершать ничего совсем уж криминального — это помогало вашим лидерам вести диалог с патрулями имперских войск, которые изредка приходили сюда для зачистки территории. Патрули приходили четко каждый второй четверг.
До следующего патруля оставалось всего двадцать четыре часа — необходимо было срочно найти и доставить в базовый лагерь что‑то ценное, что поможет откупиться от патруля и таким образом прожить еще как минимум две недели. В качестве цели вы выбрали полуразрушенное здание одной некогда крупной компании.
Вход вы нашли достаточно быстро и начали изучать некогда подземные этажи. Неожиданно в свете фонарей перед вами предстала огромная сейфовая дверь. Но радоваться было рано — несмотря на общие разрушения вокруг, сейф‑то как раз был в полном порядке. Видно, что здесь ни взрывчатка, ни отмычки не помогут — придется использовать более технологичные методы.
В самом центре сейфовой двери находится большой диск, на котором проглядывают едва заметные насечки с цифрами. Часть из них, конечно, уже не рассмотреть, но похоже, что это были числа от 0 до 99, расположенные по часовой стрелке.
Пока вы изучали дверь, кто‑то из команды раскопал бетонное крошево и нашел консоль с кнопками «лево» и «право» и какими‑то древними портами для подключения к ней. Следующие минут пятнадцать вы перепаивали единственный более‑менее живой кабель, который смогли найти, чтобы подключить его к древнему компу, обнаруженному, видимо, в бывшем операционном зале. Теперь при нажатии на кнопку «право» диск на двери сейфа со скрипом вращается на R делений по часовой стрелке, при нажатии на кнопку «лево» — на L делений против часовой стрелки. Каждая операция сопровождается щелчком и занимает 1 секунду. Изначально такого рода замки устанавливают на значение по умолчанию — 0. Замок открывается при его установке на число K — ключ замка, заданный командой безопасности организации после первичной проверки механизмов.
Прежде чем начать вскрывать замок, вам надо ответить для себя на вопрос: «Можно ли утверждать, что за минуту можно гарантированно открыть замок при любом ключе K, если R = 23, L = 16?».
Пока часть команды принимает решение, у вас есть возможность проработать программу, которая рассчитывает наименьшее время открытия сейфа при заданных R, L. При этом K может указываться, может оставаться неопределенным. Возможно, это поможет вам быстрее добраться до драгоценного содержимого сейфа и вернуться на базу «Красной Зари».
Смотрящий пустошей, отец, хранитель священного бензака, Несмертный Джо поручил вам миссию: под охраной доставить бензак на Свинцовую ферму для обмена на боеприпасы, оружие и чибургеры. Воины Полураспада, верные служители Джо, хотят сами разделиться на группы, чтобы охранять в пути ценный бензак. Было решено: чтобы попасть в определенную группу охраны, у воина Полураспада обязательно должен быть в этой группе хотя бы еще один воин, с которым они могут дышать одним воздухом. Считается, что если первый воин Полураспада ладит со вторым, то и второй ладит с первым. Каждая группа поедет на отдельной боевой фуре, поэтому количество групп должно быть минимальным. Осталось только загрузить боевые фуры и составить для каждой фуры списки воинов Полураспада, которые в ней поедут. Составьте программу, которая решит эту задачу.
Входные данные
В первой строке задано два числа: N — число воинов Полураспада, M — число строк, описывающих отношения между воинами Полураспада 0≤N, M≤1000. В следующих M строках даны пары натуральных чисел 1≤a, b≤N, означающие что воин номер a выносит воина под номером b.
Выходные данные
В первой строке выведите T — число боевых фур. В следующих T строках выведите информацию о воинах Полураспада, которые едут в боевых фурах, в порядке возрастания номеров воинов Полураспада. Во второй строке укажите в квадратных скобках число воинов Полураспада и через пробел в порядке возрастания номера воинов Полураспада, которые едут в первой фуре. Если необходимо, в третьей строке — в квадратных скобках число воинов Полураспада и через пробел в порядке возрастания номера воинов Полураспада, которые едут во второй фуре, и так далее. Каждый воин Полураспада должен присутствовать в одной и только одной боевой фуре. Если возможно несколько ответов, выведите любой.На планете Плюк в галактике Кин-дза-дза население делится на две категории: чатлане и пацаки. Пацаки придумали процедуру приветствия «КУ!», которую может пройти только настоящий пацак! Эта процедура приветствия «КУ!» между двумя обитателями А и B планеты Плюк выглядит так:
1) обитатель А выбирает натуральное число х, не большее N-1, и передает обитателю В значение функции F(x), а В отвечает А числом F(x+1);
2) В выбирает натуральное число у, не большее N-1, и передает А число F(y), при этом А отвечает В числом F(y+1).
Значение функции F равно остатку от деления на N значения аргумента, возведенного в третью степень. Докажи, что ты настоящий пацак: найди х и у, если в одном из приветствий обитателей планеты Плюк последовательно наблюдались числа: 5713, 5783, 7821 и 7870. Число N выбрано так, что значение аргумента определяется по значению функции F однозначно.
В недалеком будущем общество, зависящее от поставок топлива, стало результатом падения гражданского права. Цивилизации настал конец. Люди перестали верить в героев. Остались только психопаты и дорожные патрули полиции. Офицер Основного силового патруля по прозвищу Безумный Макс, потеряв свою семью и друзей, стремится защитить мирных жителей и спасти как можно больше жизней.
На дороге Макс встречает пятерых человек. Двое из них — бандиты-психопаты, двое — мирные люди, один — офицер патруля. Макс пытается понять, кто есть кто. Он знает, что психи всегда врут, а офицеры и мирные люди врать не могут. Бандиты явно знают друг друга. Офицер, скорее всего, знает, кто бандиты, а кто нет. Мирные люди знают только про себя и никому не верят. Макс выслушивает по очереди каждого, кто заговорит:
А: «Я знаю, кто Б».
Б: «Я знаю, кто офицер».
В: «Я знаю, кто Б».
Г: «Я знаю, кто Д».
Помогите Максу понять, кто есть кто.
В зоне отчуждения на севере столицы Фосантье проходят регулярные зачистки от бандитов и расплодившихся в стоках канализации рутпангеров. Рутпангеры слабы, но их изъеденные радиацией, мутировавшие тела источают вещество Таймконф, способное с периодичностью в один час вызывать адские ожоги.
Во время очередной зачистки один солдат из отряда выживших был заражен рутпангером. При контакте с ядом рутпангера тело жертвы подвергается интоксикации. Каждый час, начиная с ближайшей полуночи, жертва лишь испытывает легкое недомогание. Но ровно через час каждый орган, каждую клеточку тела охватывает невыносимая боль, сравнимая лишь с ударом мизинца о ножку тумбочки. Связано это с тем, что в каждый последующий час биологические часы жертвы искажены и работают по правилам иного измерения: минутная стрелка идет со скоростью часовой, а часовая — со скоростью минутной.
После часа страданий все симптомы ослабевают и биологическое время снова начинает протекать согласно нашему измерению. У жертвы есть лишь час для изготовления антидота, ведь уже через час аномалия снова возьмет верх. И так будет продолжаться весь день, по истечении которого жертва начнет безвозвратно мутировать в рутпангера.
Антидот болезненный, но простой: необходимо царапать на руке жертвы когтем рутпангера те моменты времени (кроме первого часа), которые совпадали бы с реальным биологическим временем.
Некоторых наших бойцов в очередной вылазке за едой и водой покусали зомби. Все бойцы пока находятся в общей камере карантина. Сегодня вечером каждого из них переведут в отдельный бокс, и роботы карантинной зоны начнут отводить бойцов по одному (не обязательно последовательно) в комнату с лампой облучения — эта терапия запустит процесс выздоровления.
Лампа включится, когда в комнату зайдет первый боец. Уходя из комнаты, каждый может оставить лампу как включенной, так и выключенной.
Роботы в карантинной зоне старые — их программа ограничивается всего парой действий. Если в какой‑то момент кто‑то из бойцов скажет, что все уже побывали в комнате, и будет прав, то роботы прекратят облучение и выпустят всех бойцов из зоны карантина. Если сказанное окажется неправдой — зомби-заразу не вылечат и все погибнут. Если же бойцы будут молчать, роботы продолжат водить их в комнату с лампой облучения: все побывают в комнате, и ни для кого никакое посещение комнаты не станет последним.
Придумайте стратегию, гарантирующую бойцам выздоровление.
