А вот и Новогодний релиз от самой известной игровой компании в мире "Тиро Гамес", разработчиков популярного шутера Балорант. Выходит новая игра - Метровый Бегунчик.
Геймплей игры до ужаса прост: игровой мир представляет собой некоторый участок метро, являющийся двумя раздельными рельсовыми путями одинаковой длины, на которых неподвижно стоят поезда (игра всё ещё находится в бета версии, но в честь Нового Года дизайнер успел тематически оформить метро). Игроку предстоит убегать от Метрового Защитника и уворачиваться от поездов, чтобы добежать до финиша.
Схематично игру можно представить символами = - рельсовое полотно и # - поезд. Будем считать, что один символ = представляет собой один метр пути, а # - препятствие в виде вагона длиной 1 метр. Движение Бегунчика и Защитника можно представить пошагово - сначала совершает движение Бегунчик, потом Защитник.
На старте Бегунчик находится на первом метре пути, когда как Защитник на нулевом (за границами карты).
Игра считается выигранной, если Бегунчик сумел добраться до финиша (финишем считается любая клетка за пределом игровой карты, т.е. если длина пути составляет n метров, то достижением финиша считается передвижение на n + 1-ый и дальнейшие метры). Игра считается проигранной, если Бегунчика ловит Защитник.
Антон - ярый поклонник Балоранта, и узнав, что выходит новинка с героями из его любимой игры, тут же принял участие в бета тестировании игры.
Выбрав персонажа Даон в качестве Бегунчика и Метрового Защитника Руйо, Антон погрузился в игру. Даон очень подвижный персонаж, поэтому у неё в арсенале есть несколько способов передвижения —
пробежать 1 метр вперёд; пробежать 1 метр назад; перепрыгнуть на соседний рельс, оказавшись на s метров впереди (относительно начальной позиции). Метровый Защитник Руйо тоже обладает некоторой особенность — он умеет резать измерения, поэтому может передвигаться вперёд на 1 метр каждый ход, не взирая на препятствия.
Также, оказавшись на том же метре рельс, что и Бегунчик, или перегоняя его, Руйо ловит его в пространственную ловушку, на каком бы рельсе не находился игрок (т.е если Руйо сейчас находится на k-ом метре, то он может поймать Бегунчика на любой позиции рельс от 1 до k включительно).
Поиграв немного, Антон начал что-то подозревать — то ли случайная генерация игровой карты кривая
и не позволяет пройти уровень, то ли он просто плохо играет.
Помогите Антону написать программу, которая проверяет, можно ли пройти игру.
На вход в программу подаётся описанное ранее схематичное представление игрового мира, на выходе программа должна вывести "YES", если можно победить в игре, и "NO", если нельзя добраться до конца или Защитнику удаётся поймать Бегунчика.
Формат входных данных
В первой строке подаются целые числа n, s(1≤ n,s≤ 1000) - длина рельс и скорость Даон.
Далее следует 2 строки, каждая длиной n символов. Каждая строка состоит из символов "=" и "#", обозначающих рельсы или препятствие.
Формат выходных данных
Выведите "YES", если Антон сможет пройти игру. В противном случае выведите "NO".
Ограничения
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
n
s
1
10
1 ≤ n ≤ 10
1 ≤ s ≤ 10
2
35
1 ≤ n ≤ 100
1 ≤ s ≤ 100
3
55
1 ≤ n ≤ 1000
1 ≤ s ≤ 1000
Пояснение к примерам
В примере Даон перепрыгивает на вторые пути, пробегает 1 метр вперёд и обратно прыгает на первые пути.
От туда она может добежать или допрыгать до финиша.
Новый год время чудес! Они происходят всюду, даже в мире чисел! Назовем число k-чудесным, если его можно представить в виде произведения k простых чисел. Вам дано число n. На какое минимальное натуральное число надо его поделить, чтобы оно стало k-чудесным, и можно ли это вообще сделать?
Формат входных данных
Единственная строка содержит числа n и k - число и степень чудесности.
Формат выходных данных
Если нельзя подобрать натуральное число, при делении на которое оно станет k-чудесным, выведите No. Иначе в первой строчке выведите Yes, во второй — ответ на задачу.
Ограничения
2 ≤ n ≤ 109, 1 ≤ k ≤ 100
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
"Не трогать! Это на Новый Год!" - грозно сказала мама Свете, убирая n крабовых палочек в холодильник. Света очень любит крабовые палочки, но еще больше она любит их в салатах. Она с нетерпением ждала, когда мама закончит их готовить. В этом году мама готовит салаты по определенной схеме. Кладет крабовые палочки в каждый последующий салат так, что в нем оказывается сумма палочек из двух предыдущих салатов. Она назвала это Салаты Фибоначчи. Вот бы Свете выяснить, какая это по счету партия крабовых палочек лежит в холодильнике.
Числа Фибоначчи — это последовательность чисел, которые задаются по определённому правилу. Оно звучит так: каждое следующее число равно сумме двух предыдущих. Первые два числа заданы сразу и равны 0 и 1. Последовательность Фибоначчи выглядит следующим образом 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ... , ∞
Формат входных данных
Первая строка входного файла содержит натуральное число q - количество чисел Фибоначчи. Во второй и последующих строках указаны числа из последовательности Фибоначчи (одна строка - одно число) .
Формат выходных данных
Выведите порядковый номер, начинающийся с 0, для каждый строки (одна строка - один порядковый номер, соотвествующего числа Фибоначчи). PS: В случае числа 1, когда невозможно точно определить место в последовательности, необходимо вывести текст unknown.
Ограничения
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
n
q
1
10
0 ≤ n ≤ 109
1 ≤ q ≤ 80
2
35
0 ≤ n ≤ 10126
1 ≤ q ≤ 160
3
55
0 ≤ n ≤ 101254
1 ≤ q ≤ 200
Пояснение к примерам
Для первого примера: 0 является начальным числом
Для второго примера: для 1 невозможно определить место, поэтому unknown
Для третьего примера: число 13 является 7-ым числом, а 233 13-ым числом (считая с нуля) в последовательности Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Дежавю — феномен, при котором у человека возникает ощущение, что он уже испытывал определенную последовательность событий в прошлом. Часто вы можете ощущать подобное в преддверии крупных семейных праздников, например Нового Года.
В течении предновогоднего дня с Анжеликой произошло какое-то количество событий (для удобства будем нумеровать события от 1 до 106, то есть существует 106 различных событий). После каких-то событий Анжелика испытала чувство дежавю, то есть, Анжелика думает, что последовательность из последних K событий уже встречалась среди событий, которые были раньше последних K событий. Для каждого раза сообщите, ложное ли это чувство или нет.
Формат входных данных
В первой строке вводится натуральное число K.
Во всех следующих строках вводится по одному из трех запросов следующего вида:
e X — произошло событие под номером X (1 ≤ X ≤ 106)
dejavu — Анжелика испытала чувство дежавю. Для каждого такого запроса надо вывести false, если чувство ложное, иначе выведите true. Гарантируется, что получая данный запрос, произошло хотя бы 2K событий.
stop — самый последний запрос, который показывает, что день закончился. После этого запроса ничего больше не происходит.
Гарантируется, что общее количество запросов Q не превзойдет 105.
Формат выходных данных
Для каждого запроса второго вида на новой строке выведите false, если чувство ложное, иначе выведите true.
Ограничения
1 ≤ K ≤ 104, 1 ≤ X ≤ 106
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
1
10
1 ≤ Q ≤ 103
2
35
1 ≤ Q ≤ 104
2
55
1 ≤ Q ≤ 105
Пояснение к примеру
Первый эффект дежавю. Последовательность событий: (1, 2, 1, 2). Последние 2 события: (1, 2). Оставшиеся события: (1, 2). Последовательность (1, 2) встречается в последовательности (1, 2).
Второй эффект дежавю. Последовательность событий: (1, 2, 1, 2, 2). Последние 2 события: (2, 2). Оставшиеся события: (1, 2, 1). Последовательность (2, 2) не встречается в последовательности (1, 2, 1).
Третий эффект дежавю. Последовательность событий: (1, 2, 1, 2, 2, 2). Последние 2 события: (2, 2). Оставшиеся события: (1, 2, 1, 2). Последовательность (2, 2) не встречается в последовательности (1, 2, 1, 2).
Примеры тестов
№
Стандартный вход
Стандартный выход
1
2
e 1
e 2
e 1
e 2
dejavu
e 2
dejavu
e 2
dejavu
stop
Ежегодный новогодний турнир по кибер-шахматам идет полным ходом, но турнир не по стандартным правилам, а с определенными условиями.
На бесконечной шахматной доске на поле с координатами (x, y) находится одинокая шахматная ладья. Два игрока поочередно перемещают её вниз или влево на любое расстояние от 1 до d. Побеждает игрок, первым достигший поля (1, 1). Кто победит при правильной игре обоих игроков — игрок, который ходит первым или вторым?
Формат входных данных
Первая строка входного файла содержит натуральное число d. Во второй строке через пробел указаны два натуральных числа — координаты ладьи.
Формат выходных данных
Выведите First или Second — ответ на вопрос задачи.
Ограничения
1 ≤ x, y, d ≤ 1018, 2 ≤ x + y.
2 ≤ x + y
Система оценки и описание подзадач
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
x, y, d
1
10
2 ≤ x, y, d ≤ 103
2
35
2 ≤ k ≤ n ≤ 109
3
55
2 ≤ k ≤ n ≤ 1018
Пояснение к примеру
Смотри рисунок. В примере дана ладья, способная перемещаться не более, чем на 3 поля. Первый игрок переместит фигуру вниз на поле (5, 1). Второй игрок теперь может перемещать ладью только влево. Независимо от его хода, первый игрок следующим ходом сможет поставить ладью в левое нижнее поле и добиться победы.
Снегурочка помогает Деду Морозу упаковывать подарки на Новый год. Кто-то попросил у Деда Мороза фантастически большую доску высотой n и длиной m. У Снегурочки есть бесконечное количество полосок обёрточной бумаги ширины 1 и длины k. Сможет ли Снегурочка полностью обернуть(покрыть с одной стороны не пересекающимися полосами) доску, используя только эти полоски?
Формат входных данных
Единственная строка содержит числа n, m и k - высота доски, ширина доски и длина полоски соответственно.
Формат выходных данных
Если вы не сможете уложить доску полосками, выведите No. Иначе выведите Yes.
Ограничения
2 ≤ n, m, k ≤ 1018
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Недавно VK выпустили новогодний альбом, в котором каждый трек поют 2 человека - звезда 2010-ых годов и звезда 2020-ых годов.
Вы — продюссер альбома, который будет самым громким альбомом года! Для этого вы позвали 2n исполнителей, у i-ого исполнителя пик популярности был в yi-ом году. В альбоме будет n треков, каждый трек будут исполнять 2 человека (каждый исполнитель исполняет ровно один трек). Пусть трек исполняют i-ый и j-ый исполнитель, тогда громкость этого трека будет равна |yi − yj|. А громкость альбома равна сумме громкостей всех треков в этом альбоме.
Какой максимальной громкости альбома вы сможете добиться?
Формат входных данных
В первой строке вводится натуральное число n — количество треков в альбоме. Во второй строке вводится 2n натуральных чисел, где i-ое число показывает год пика популярности i-ого артиста.
Формат выходных данных
Выведите ответ на задачу.
Ограничения
2 ≤ n, yi ≤ 105
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Все вновь не так как должно бы быть... Похоже Денис опять опаздывает на турнир по спортивному программированию...
Но как хорошо, что в городе Хабаровске площадью 2 * 105 на 2 * 105 построили метро!(представим, что Хабаровск квадратный).
Правда, построили пока одну ветку, и поезд движется по ней прямолинейно лишь в одном направлении со скоростью v.
Ветка расположена в центре города (в координате 0,0) и простирается до окраины (в координате 105).
Также известно, что на этой ветке есть n станций.
Метро строили люди креативные, а поэтому станции названы согласно их порядковым номерам в ветке (Нулевая, Первая и т.п.).
Денис живёт в центре города и ему было легко добраться до Нулевой станции.
Уже сидя в вагоне и подъезжая к Первой станции, Денис призадумался — когда ему нужно выходить,
чтобы добраться до площадки с координатами x,y и не опоздать?
Также Денис хорошо знает возможности своего тела, а именно, что он может ходить со скоростью u.
Формат входных данных
В первой строке даны три целых числа n, v, u(2 ≤ n ≤ 100, 1 ≤ v,u ≤ 1000) -
количество остановок метро, скорость метро и скорость Дениса.
Во второй строке подаются n целых чисел в порядке возрастания - координаты месторасположения станции xi(0 ≤ xi ≤ 105).
В третьей строке даны целые числа x,y( − 105≤ x,y ≤ 105) - координаты площадки.
Формат выходных данных
Выведите номер станции, на которой Денису следует выйти, чтобы успеть на турнир по спортивному программированию как можно быстрее.
Ограничения
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Новогодние каникулы — отличное время для отдыха и, как оказалось, для изучения математики. Дед Мороз решил разобраться в комбинаторике и столкнулся с формулой Cnk. Он представил, что у него есть n подарков и мешок, вмещающий ровно k вещей, и количество вариантов заполнения мешка выражается этой формулой.
Дед Мороз поделился своим открытием с детьми, и те в ответ рассказали ему о системах счисления. Заинтригованный Дед Мороз решил вычислить количество способов заполнить мешок и представить число в d-ичной системе счисления, где d — количество детей на празднике.
Однако, когда Дед Мороз заканчивал запись числа на снегу, он обнаружил много нулей в конце и запутался. Помогите ему разобраться! Скажите, сколько нулей должно быть в конце записи числа, чтобы все было правильно.
Формат входных данных
Единственная строка содержит числа n, k и d - количество подарков, вместимость мешка и количество детей на празднике.
Формат выходных данных
Выведите количество нулей в конце записи числа Cnk в d-ичной системе счисления.
Ограничения
2 ≤ n, k, d ≤ 109.
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Последняя учебная неделя перед Новогодними каникулами. В классе прошла очень сложная и решающая полугодовую оценку контрольная по информатике, по которой Женя получил оценку 2, потому что списывал. Теперь Женя очень грустный, ведь он не получит обещанный игровой компьютер для учебы в качестве подарка. Он хочет пойти домой самым длинным путем, чтобы погрустить.
Школа находится на остановке под номером 1, дом Жени — на остановке под номером N. Все остальные остановки нумеруются целыми числами от 2 до N − 1. Женя не очень хорошо знает город, поэтому умеет ходить только между какими-то парами остановок. Таких пар K штук. Женя от остановки под номером Ai до остановки под номером Bi будет идти Ti минут (но не факт, что Женя осмелится пойти по обратному пути, то есть не факт, что Женя может ходить от Bi до Ai). Кстати, Женя всегда может дойти от школы до дома, возможно через промежуточные остановки.
Если вдруг Женя придет на остановку, на которой он живет (неважно, случайно или специально), то его тут же забирает мама и ведет домой, чтобы проводить воспитательную беседу. Больше Женя никуда не пойдет.
Помогите Жене! Сообщите, сколько минут он сможет ходить по городу, прежде чем дойдет до дома!
Формат входных данных
В первой строке вводятся натуральные числа N и K
В следующих K строках вводятся числа Ai, Bi и Ti.
Формат выходных данных
Выведите число, которое показывает, сколько минут он сможет ходить по городу, прежде чем дойдет до дома. Если Женя может бесконечно долго гулять по городу, выведите − 1.
Ограничения
1 ≤ N, K ≤ 104
1 ≤ Ai, Bi ≤ N
1 ≤ Ti ≤ 105
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
