Сегодня в Убежище №2022 большое событие: после 100 лет изоляции открылась главная дверь! К сожалению, сильный оползень завалил камнями путь на волю.
Смотритель Убежища решил поручить разбор завала жителю по имени Чемпион. Ему поручено перетаскать в опустевшие кладовые Убежища все мешающие проходу n камней.
Чемпион обладает силой s. Она позволяет ему за один день перетащить s2 камней. Проработав весь день, Чемпион устает и переносит в течение следующего дня на s камней меньше, чем в предыдущий. Однако, он может устроить выходной (в этот день он не носит камни) и на следующий день опять перетащить s2 камней.
Помогите Смотрителю рассчитать, через сколько дней можно будет покинуть опостылевшее Убежище.
Формат входных данных
Входной файл содержит два натуральных числа, записанных через пробел: s — сила Чемпиона и n — количество камней.
Формат выходных данных
Выведите одно натуральное число — наименьшее количество дней, за которые Чемпион расчистит завал.
Ограничения
Система оценки и описание подзадач
1 ≤ s ≤ 10.
1 ≤ n ≤ 1000.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
В первом примере Чемпион в первый день перетаскивает 9 камней, во второй день 6, в третий — последние 3. Есть и другое подходящее расписание: перетащить в первый день 9 камней, отдохнуть во второй день и перетащить в третий день последние 9 камней.
Во втором примере Чемпион перетащит все камни за один день.
В третьем примере Чемпион вынужден работать через день, перетаскивая по одному камню.
Курьер №6 медленно восстанавливается после тяжелого ранения в голову в городке Гудспрингс. Чтобы не скучать и заработать немного крышек, он предложил жителям городка свои услуги.
В городке осталось ровно n домов, расположенных вдоль одной стороны единственной улицы. Курьер поселился у дока Митчелла, который живет в доме №1. Все остальные дома пронумерованы от 2 до n. Когда какому-нибудь жителю городка нужно передать письмо или пакет жителю другого дома, он вызывает нашего героя.
Сегодня у дока Митчелла день рождения! Естественно, каждая семья городка приготовила для него подарок, доставить который нужно Курьеру. Он выходил из дома №1, доходил до дома очередного клиента, забирал коробочку с подарком и возвращался назад. По совету доктора, проверяя свое восприятие, он, проходя мимо каждого дома, записывал его номер.
Так, если в городе 3 дома, Курьер запишет следующие числа:
1 (Курьер и сам приготовил подарок для своего друга — отлично сохранившийся номер журнала "Терапевт сегодня");
1 2 1 (подарок из дома №2 — модуль для автодока);
1 2 3 2 1 (подарок из дома №3 — неповрежденный садовый гном).
К удивлению Курьера, вечером, когда все посылки были доставлены, док без ошибок назвал сумму всех записанных чисел. Поскольку у Курьера всё ещё сильно болит голова, напишите программу, проверяющую расчеты доктора.
Формат входных данных
Входной файл содержит единственное натуральное число n — количество домов в городке.
Формат выходных данных
Найдите сумму всех записанных Курьером чисел. Поскольку число может оказаться очень большим, выведите его последнюю цифру.
Ограничения
1 ≤ n ≤ 1018.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
Для n = 3 сумма получившихся чисел будет равна: 1 + 1 + 2 + 1 + 1 + 2 + 3 + 2 + 1 = 14. Последняя цифра 4.
"Я наконец-то вышел за пределы Убежища №76. Дверь за спиной закрылась с металлическим лязгом. Было слышно, как внизу остановились генераторы. Теперь здесь делать нечего — родное Убежище навсегда закрыто, нужно догонять Смотрительницу и вас, моих друзей...
Рёв слева заставил меня подпрыгнуть и резко повернуться. Волосы на голове зашевелились, рука потянулась к пистолету на ремне и только ноги приняли единственно правильное решение — бежать, бежать прочь от невиданного ранее чудовища! Вот когда пригодились высокие показатели выносливости — моя скорость оказалась выше скорости Смертельного Когтя. Скоро нашлась и стратегия боя — нужно было отбежать подальше, тщательно прицелиться и выстрелить в монстра, опять отбежать, пока он не успел догнать, и снова выстрелить, и так далее...
Через пару часов все было кончено. Огромная туша не подавала признаков жизни, а я, тяжело дыша, пытался понять, куда это меня занесло? и как теперь вернуться назад?"
На самом деле в рассказе Резидента некоторые детали, мягко говоря, приукрашены... По состоянию обоймы было видно, что Смертельному Когтю хватило ровно двух выстрелов (видимо, он был старым и больным), да и сам рассказчик не выглядел особенно уставшим... Помогите слушателям узнать, на какое минимальное расстояние нужно было удалиться от Убежища Резиденту, чтобы справиться с врагом?
Формализуем условие: Резидент находится на числовой оси в точке 0. В точке -1 находится Смертельный Коготь. Персонажи ходят по очереди, первым ходит Резидент. В его распоряжении r очков действий. Он может потратить их на перемещение (1 очко действия на перемещение вправо на 1 позицию по числовой оси), на выстрел (каждый выстрел требует g очков действий) или не тратить (полностью или частично). Сэкономленные очки на следующий ход не переносятся. Вторым ходит монстр. В его распоряжении d очков действий. Он их тратит только на перемещение (1 очко действия на перемещение вправо на 1 позицию по числовой оси), и если в какой-то момент чудовище оказывается в той же точке, что и человек, оно его съедает. Если Резидент успевает сделать второй выстрел до того момента, как его настиг Смертельный Коготь, он выжил. Определите наименьшую координату точки, в которую придется переместиться человеку, чтобы выжить.
Формат входных данных
В единственной строке входного файла содержится три натуральных числа: d — очки действий Смертельного когтя за ход, r — очки действий Резидента за ход и g — очки действий на один выстрел.
Формат выходных данных
В единственной строке выведите неотрицательное целое число — минимальное расстояние, на которое придется удалиться Резиденту от Убежища, чтобы справиться с врагом. Гарантируется, что ответ не превысит 1018.
Ограничения
1 ≤ d, g < r ≤ 109.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ r ≤ 100, получат не менее 40 баллов.
Пояснения к примерам
В первом примере события развиваются так:
Первый раунд: Резидент перемещается в точку 11, Коготь — в точку 6.
Второй раунд: Резидент перемещается в точку 14 и стреляет первый раз. Два очка действия не используются. Коготь идет в точку 13.
Последний раунд: Резидент стреляет второй раз. Погоня окончена в точке 14.
Во втором примере Резидент успевает выстрелить дважды в течении первого раунда.
В Убежище №13 скоро выборы! Старый смотритель ушел на покой и теперь любой житель может зарегистрироваться в кандидаты на ответственную должность. После этого все остальные избиратели оценивают кандидата и после выборов либо назначают его новым смотрителем, либо нет (в этом случае выдвигается другой кандидат). В отличие от других Убежищ Волт-Тек, здесь выбирают исключительно харизматичных лидеров.
Харизматичность — категория непростая... Она делится на три составляющих, а они, в свою очередь, на три параметра каждая (схема ниже на рисунке). Каждый житель Убежища либо обладает определенным параметром, либо нет, соответственно, харизматичность каждого жителя можно описать девятизначным двоичным числом.
Каждый житель убежища имеет свои представления о харизматичности (она не обязана совпадать с его внешним видом). Кому-то по душе строгий довоенный костюм, а кому-то — родной комбинезон убежища с числом 13 на спине. Кто-то считает, что будущий смотритель должен быть серьезным, а кто-то — весёлым. Одни считают, что без хорошей прически лидер — не лидер, а другие — что "шрамы украшают мужчин". Что поделать, сколько людей — столько и мнений... Важно только то, что во время выборов каждый житель оценивает харизматичность кандидата, и если все параметры ему нравятся, кандидат получает голос "За", а если хотя бы один параметр отличается — "Против". Если голосов "За" окажется больше определенного заранее числа — кандидат становится новым смотрителем.
Один из жителей убежища (назовем его Джон) решил подойти к выборам серьезно. Он побеседовал с каждым избирателем и записал его представления об идеальном смотрителе сначала в виде девятизначного двоичного числа, а потом перевел его в более привычное десятичное представление. Свою внешность Джон тоже записал с помощью такого представления, после чего почесал в затылке. Полных совпадений было маловато...
К счастью, Джон скопил немного крышек и в состоянии изменить в своей харизматичности до трех параметров (например, купить новый костюм, удалить авто-доком татуировки и оплатить услуги Тома-Весельчака для вставки в предвыборную речь удачных шуток). Подскажите, какие параметры следуют изменить Джону, чтобы как можно большее количество жителей убежища проголосовало за него? Сколько голосов удастся набрать Джону прежде чем новый смотритель отправит его за в Пустошь за водяным чипом?
Формат входных данных
Первая строка входного файла содержит два неотрицательных целых числа, записанных через пробел: n — количество избирателей и d — харизматичность Джона. Во второй строке через пробел записаны n чисел ai в порядке неубывания — представления об идеальном смотрителе всех избирателей.
Формат выходных данных
В единственной строке выведите одно неотрицательное целое число — наибольшее количество голосов "За", которые сможет набрать Джон, изменив в своей харизматичности не более трех параметров.
Ограничения
1 ≤ n ≤ 100000.
0 ≤ d, ai ≤ 511.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 10, получат не менее 20 баллов.
Решения, верно работающие при 1 ≤ n ≤ 1000, получат не менее 60 баллов.
Пояснения к примерам
В первом примере Джон (его харизматичность соответствует двоичной записи 000000100) может изменить два параметра и будет соответствовать идеальным представлениям трех избирателей (4410 = 0001011002). Получить четыре голоса (9710 = 0011000012) он не сможет — необходимо менять четыре параметра.
Во втором примере никакие ухищрения Джона (9710 = 1111111112) не позволят ему набрать даже один голос.
Для проникновения в Институт Вам нужно пройти проверку на интеллект. Ученые Института для проверки мыслительных способностей испытуемых используют проверенные временем психодиагностические методики XX века.
Куб Линка — это методика оценки интеллектуальных процессов и когнитивных функций. Много лет назад она входила в арсенал детских развивающих игр под названием «Уникуб». Ниже на рисунке вы видите собранную головоломку красного цвета.
Испытуемому нужно построить из 27 маленьких кубиков один большой куб, все грани которого были бы одного определенного (например, красного, жёлтого или какого-то другого) цвета. В наборе 8 кубиков имеют три стороны (с одной общей вершиной) определенного цвета, 12 — две смежные стороны, 6 — одну сторону и 1 — ни одной стороны заданного цвета.
Итак, перед Вами набор из 27 маленьких кубиков. Докажите ученым Института, что в своем развитии Вы превзошли супермутантов и для решения головоломки можете даже не знать определенный цвет.
Формат входных данных
Входной файл содержит 27 строк. В каждой строке записана шести-символьная строка из маленьких латинских букв — описание одного кубика. Ученые Института используют для Куба Линка только 6 цветов: белый цвет (white) кодируется символом "w", желтый (yellow) — "y", красный (red) — "r", зеленый (green) — "g", синий (blue) — "b", оранжевый (orange) — "o". В строке записаны первые буквы цветов граней кубика в произвольном порядке. Гарантируется, что грани кубика окрашены не менее, чем двумя цветами, каждый цвет используется для окраски не более трех граней кубика. Если из шести граней кубика три имеют одинаковый цвет, то эти грани имеют общую вершину.
Формат выходных данных
В первой строке выходного файла запишите название цвета получившегося у вас большого куба. В следующих 27 строках укажите в какое место большого куба следует положить данный вам по порядку кубик — выведите одно из четырех слов: corner (угол), edge (ребро), side (середина грани) или center (центральный кубик). Обратите внимание: вам не нужно указывать ориентацию граней маленького кубика, только его место. Гарантируется, что из предложенных вам кубиков можно сложить куб 3:3:3, окрашенный снаружи одним цветом. Собрать куб, окрашенный снаружи другим цветом невозможно.
red
corner
side
edge
side
side
side
side
corner
edge
side
edge
edge
edge
edge
corner
corner
edge
center
edge
corner
edge
corner
edge
corner
corner
edge
edge
Когда-то давно Кюри была роботом и работала в Убежище №81. Но, благодаря Выжившему и доктору Амари, теперь она — женщина (пусть и синтетическая) и ей нужно срочно научиться выглядеть и действовать так, чтобы не вызывать подозрений.
Сегодня Кюри учится заплетать косу. Все волосы она разделила на три пряди и ловко переплетает их в поисках наиболее красивого варианта (под переплетением будем понимать обмен положений двух соседних прядей). Вскоре Кюри заметила, что её действия являются практической реализацией известной математической теории кос, записанной ей в память при изготовлении на заводе РобКо Индастриз.
Так, исходное положение трех прядей можно записать в виде строки 123. Каждое переплетение меняет местами в этой строке две соседние цифры. Понятно, что сделав достаточное число переплетений, можно получить любую перестановку исходной строки. Но если нам известно число переплетений и интересующая перестановка, как определить, достижима ли она? Кюри быстро нашла ответ на этот вопрос. Очередь за вами.
Формат входных данных
Единственная строка входного файла содержит два натуральных числа, записанных через пробел: n — количество переплетений и p — перестановка исходной строки 123.
Формат выходных данных
В единственной строке выведите 'YES' (без кавычек), если ровно за n переплетений из исходной строки 123 можно получить строку p. Выведете 'NO' в противном случае.
Ограничения
1 ≤ n ≤ 1014.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 10, получат не менее 40 баллов.
Решения, верно работающие при 1 ≤ n ≤ 1000, получат не менее 80 баллов.
Пояснения к примерам
Один из вариантов решения первого примера на рисунке внизу (для удобства коса нарисована горизонтально).
Во втором примере получить перестановку 321 из исходной за одно переплетение невозможно.
Поиздержавшись в дороге, Избранный испытывает удачу в казино "Десперадо". Правила игры за столом чрезвычайно просты — каждый из игроков выбрасывает n обычных игральных кубиков с нанесёнными на их стороны числами от 1 до 6 (их принято располагать так, что сумма чисел на противоположных сторонах равняется 7). Кто выбросит большую сумму очков на верхних гранях, тот и победил.
Также у Избранного есть показатель удачливости m, благодаря которому он (незаметно для окружающих) ровно m раз переворачивает кубики на противоположную грань, стараясь максимально улучшить свой результат (можно переворачивать один и тот же кубик или разные). Предскажите результат Избранного.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — количество кубиков и m — количество переворотов. Во второй строке через пробел записаны n чисел ai — выпавшие значения на верхних гранях кубиков.
Формат выходных данных
Выведите одно натуральное число — наибольшую сумму выпавших очков после m переворотов.
Ограничения
1 ≤ m ≤ n ≤ 100000.
1 ≤ ai ≤ 6.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при m = 1 и 1 ≤ n ≤ 10, получат не менее 20 баллов.
Решения, верно работающие при 1 ≤ m ≤ 10 и 1 ≤ n ≤ 250, получат не менее 60 баллов.
Пояснения к примерам
В первом примере Избранный выбросил пятерку на единственном кубике и переворачивает его один раз на противоположную сторону — двойку. Увы, результат лишь ухудшился...
Во втором примере Избранный поменяет единицу на шестерку на втором кубике и два раза перевернет первый кубик, оставив на нём исходную тройку. Это даст ему максимально возможные для данного начального расположения 14 очков.
