Задача A. Конфеты ≡

Условие

Денис очень любит конфеты. Однажды его мама принесла домой пакет с n конфетами, и Денис хочет выкрасть k из них. На это у него есть m дней. Каждый день он может красть любое количество конфет (меньше или равное k). Независимо от того, сколько конфет Денис украл, каждый вечер мама берет w конфет из пакета. Более того мама может заметить украденные конфеты с вероятностью P_i = x_i / n_i, где x_i — это количество украденных в этот день конфет, а n_i это количество конфет утром этого дня.

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

К вечеру m-го дня Денис в сумме должен выкрасть k конфет.

Формат входных данных

В одной строке n, k, m, w — целые положительные числа, разделенные пробелом. k,w ≤ n.

n,k,m,w < 10⁵

Формат выходных данных

Первым числом выведите n, количество дней, в которые Денис должен красть конфеты.

Затем n строк, в каждой по 2 числа: номер дня и количество конфет в этот день.

Строки должна быть упорядочена по дням.

Примеры тестов

5 2 2 1

1
1 2

Задача B. Неуловимый Джо ≡

Условие

За Неуловимым Джо началась жесткая погоня, из-за чего ему пришлось убегать от преследователей по крышам домов! Дома пронумерованы от 1 до n, i-й дом имеет высоту, равную h_i метрам. Джо последовательно бежит от дома к дому в порядке номеров, то есть от первого ко второму, от второго к третьему и так далее до того момента, как он прыгнет на самый последний дом и спрячется в свое укрытие, которое находится в n-м доме.

Неуловимый Джо умеет перемещаться с одной высоты на другую высоту только в том случае, когда разность высот не превосходит l метров, в противном случае ему придется использовать специальный трос (таких тросов у Джо ровно k штук, каждый трос можно использовать только один раз). Обратите внимание, что если высота дома, с которого Джо хочет спрыгнуть, выше l метров, то Джо для этого обязан использовать трос.

Также Джо может прыгать с крыши домов на землю (для простоты будем считать, что земля имеет высоту 0). Однако Джо не может ходить по земле — так его с легкостью поймают. Поэтому, если Джо спрыгнул с (i − 1)-го дома, то он пройдет только вдоль i-го дома, а затем запрыгнет на (i + 1)-й дом (использовав трос, если высота дома больше l метров). В самом начале погони Джо может выбрать, где он будет стартовать — на крыше первого дома или на земле около первого дома.

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

Формат входных данных

В первой строке вводятся натуральные числа n, k, l — количество домов, количество тросов и максимальная высота прыжка соответственно (1 ≤ n ≤ 10⁶, 0 ≤ k ≤ n, 1 ≤ l ≤ 10⁹).

В следующей строке вводится последовательность натуральных чисел h₁, h₂, ..., h_n — высоты домов (1 ≤ h_i ≤ 10⁹).

Формат выходных данных

Если Джо сможет добежать до укрытия, выведите YES, иначе выведите NO.

Примечание

В первом примере Джо будет действовать следующим образом:

1. Изначально Джо запрыгнет на крышу первого дома;
2. С крыши первого дома Джо прыгнет на землю около второго дома;
3. С земли около второго дома Джо поднимется на крышу третьего дома;
4. С крыши третьего дома Джо спрыгнет на землю около четвертого дома;
5. С земли около четвертого дома Джо прыгнет на крышу пятого дома.

Во втором примере Джо будет стартовать с земли около первого дома, а затем запрыгнет на крышу второго дома.

Примеры тестов

5 1 3
3 7 2 6 3

YES

2 0 3
6 2

YES

Задача C. Начинающий разработчик ≡

Условие

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

• Пароль считается средним, если:
• в нём более 10 символов,
• среди символов есть латинские буквы в одном из регистров и цифры.
• Пароль считается сильным, если:
• в нём более 14 символов,
• среди символов есть латинские буквы каждого из регистров и цифры.
• Пароль считается очень сильным, если:
• в нём более 16 символов,
• среди символов есть латинские буквы каждого из регистров, цифры и специальные символы (!, @, #, %, и т. д.).
• Если пароль не удовлетворяет ни одному из условий, то пароль считается слабым.

Напишите программу, которая по заданному паролю определяет его силу.

Формат входных данных

В первой и единственной строке входных данных дается строка пароля длиной от 1 до 50 символов.

Формат выходных данных

Необходимо вывести строку, представляющая силу пароля: «weak», «medium», «strong» или «very strong».

Примеры тестов

Ayr6TY8@1!hSdhsjDKDJ819

very strong

FHDgdhshddyHF

weak

Задача D. Трискайдекафобия ≡

Условие

Трискайдекафобия — болезненная боязнь числа 13. Наличие фобии заставляет человека испытывать повышенную тревожность при контакте с любым объектом, в описании или названии которого есть 13. Это влияет на поведение, решения и общее состояние человека с данным расстройством. В результате в некоторых зданиях этажи нумеруются так, чтобы не нервировать трискаидекафобов: после 12-го этажа может сразу следовать 14-й. Иногда это также относится к номерам домов и помещений. В современной "Формуле-1" нет болида под номером 13.

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

Трискайдекафобией страдал австрийский композитор Арнольд Шёнберг. Он родился 13-го числа, что он всю жизнь считал дурным предзнаменованием. Однажды он наотрез отказался взять в аренду дом под номером 13. Композитор боялся того дня, когда ему исполнится 76, потому что в сумме эти цифры составляют пресловутое число 13. Более того, эта дата пришлась на пятницу 13 июля 1951 года. По слухам, тогда он весь день пролежал в постели, готовясь к предполагаемой смерти. Жена пыталась уговорить мужа встать и "прекратить эти глупости", и каково же было её потрясение, когда тот лишь вымолвил слово "гармония" и умер за 13 минут до полуночи.

Арнольд считает число хорошим, если в нём нет ни одной подстроки "13". Сколько хороших чисел среди всех n-значных?

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 18

Пояснение к примеру

В первом примере нужно найти хорошие числа среди всех двузначных. В диапазоне от 10 до 99 есть только одно нехорошее число 13.

Примеры тестов

2

89

4

8721

Задача E. Чокопай ≡

Условие

На дурацкую олимпиаду по программированию пришло n команд, в каждой команде по 3 человека. Как и на всех дурацких олимпиадах, организаторы решили раздать командам чокопай! У них есть m различных видов чокопая, i-го вида чокопая у организаторов a_i штук.

Организаторы хотят раздать чокопай каждой команде таким образом, чтобы никто в команде между собой не поссорился и чтобы каждому участнику команды досталось то же самое множество чокопаев, что и его сокомандникам (более формально, для любого i-го вида у каждого участника команды должно быть одинаковое количество чокопаев i-го вида). Но при этом организаторы не следят за тем, чтобы у каких-либо двух команд был одинаковый набор чокопаек (к примеру, организаторы могут хоть все угощения отдать одной команде и оставить все остальные команды с пустыми руками, могут раздать всем командам чокопай, а могут вообще никому ничего не давать).

Помогите организаторам! Сообщите количество способов раздать чокопай таким образом, чтобы никакие два сокомандника не поссорились между собой.

Формат входных данных

В первой строке вводятся натуральные числа n и m — количество команд и количество видов чокопая (1 ≤ n, m ≤ 10⁵). Во второй строке вводятся последовательность целых чисел a_i (0 ≤ a_i ≤ 10⁵).

Формат выходных данных

Выведите ответ на задачу по модулю 10⁹ + 7.

Примечание

В первом примере раздать чокопай можно следующими способами:

1. Первой команде 3 чокопайки 1-го вида и 3 чокопайки 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
2. Первой команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида;
3. Первой команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида, второй команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида;
4. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 3 чокопайки 1-го вида и 3 чокопайки 2-го вида;
5. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
6. Первой команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
7. Первой команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
8. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида;
9. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида.

Примеры тестов

2 2
3 3

9

Задача F. Честные грабители ≡

Условие

Некая группировка, состоящая из K человек, собралась ограбить банк. Банк представляет собой прямую, на которой расположено N комнат с золотыми слитками. В i-й комнате находится a_i слитков золота. Грабители могут забрать содержимое любого непрерывного отрезка комнат. Однако, так как грабители честные, они не могут допустить неравноценного разделения добычи. Поэтому суммарное количество украденных золотых слитков обязательно должно нацело делиться на количество участников группировки K.

От вас требуется определить максимальное количество золотых слитков, которые они смогут украсть так, чтобы их можно было разделить поровну на всех участников группировки.

Формат входных данных

В первой строке даны числа N (N ≤ 10⁵) — количество комнат в банке, и K (K ≤ 10⁵) — количество грабителей в группировке.

Во второй строке даны N чисел a_i (a_i ≤ 10⁹) — количество слитков в i-й комнате.

Формат выходных данных

Требуется вывести одно число — максимальное количество слитков, которые могут украсть члены группировки из непрерывного отрезка комнат.

Примеры тестов

5 3
1 3 2 3 5

9

7 11
12 54 3 10 71 99 64

99

Задача G. Два числа ≡

Условие

Тимофей смастерил очень странное устройство с индикатором и двумя кнопками. Нажатие на первую кнопку увеличивает число на индикаторе на 1, а нажатие на вторую кнопку изменяет число на противоположное. Прямо сейчас на индикаторе горит число a. Какое наименьшее количество нажатий требуется осуществить, чтобы там появилось число b?

Формат входных данных

В двух строках входного файла содержатся два различных целых числа a и b.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

 − 10⁹ ≤ a, b ≤ 10⁹

Пояснение к примеру

Чтобы из числа 5 получить число -6, достаточно сначала нажать первую кнопку, потом — вторую.

Примеры тестов

5
-6

2

Задача H. Мастер гирлянд ≡

Условие

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

Красивая последовательность лампочек представляет собой строку из латинских букв длины l.

Красивую последовательность можно добавить к гирлянде только тогда, когда гирлянда пуста или начало красивой последовательности совпадает с окончанием уже получившийся гирлянды: abab + abab + aber→ ababab + abe→ abababer.

Формат входных данных

Первая строка содержит два натуральных числа: N и L — количество красивых последовательностей и желаемая длина гирлянды. 1 ≤ N ≤ 300, 1 ≤ L ≤ 10000

Следующие N строк содержат длину красивой последовательности l_i и саму последовательность s_i. l_i ≤ 2000.

Каждая красивая последовательность лампочек не является подстрокой любой другой в этом наборе последовательностей. Так hello и hell не могут быть в одном наборе.

Формат выходных данных

Если возможно собрать гирлянду длины L из данных красивых последовательностей, то первая строка должна содержать целое число — количество красивых последовательностей лампочек в гирлянде и следующая за числом гирлянда.

Иначе вывести  − 1.

Если существует несколько решений выведите то, в котором наибольшее количество красивых последовательностей лампочек.

Примеры тестов

3 5
3 ror
2 er
3 rro

3
error

Задача I. Реализация ≡

Условие

Очки в регби присуждаются за совершение результативных действий, одним из которых является реализация. Один из игроков команды пробивает по неподвижному мячу по воротам соперника. Реализация считается успешной, если мяч прошёл между двумя штангами над перекладиной (смотри рисунок, зона удачной реализации залита синим цветом). Определение того, была ли реализация успешной — непростая техническая задача. В отличии от футбола, система автоматического определения голов в регби пока ещё только внедряется.

Тимофей участвует в разработке системы GoalControl и отвечает за определение правильности реализации по фронтальному изображению размером n × m, которое содержит каркас Н-образных ворот толщиной в один пиксель и одного мяча, обозначаемых символами "#" (ASCII-код 35). Поскольку систему планируют внедрить не только в Регби-15, но и в других схожих видах спорта, размеры ворот могут быть произвольными, но иметь одинаковые по высоте штанги, параллельные границам изображения. Перекладина ворот располагается строго ниже верхнего уровня штанги и выше нижнего уровня штанги. Фон рисунка заполнен символами "." (ASCII-код 46).

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

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m. В следующих n строках расположены строки длиной m, состоящие из символов "#" и ".". Гарантируется корректность входных данных.

Формат выходных данных

Выведите Yes или No — ответ на вопрос задачи.

Ограничения

5 ≤ n, m ≤ 100

Примеры тестов

7 8
....#...
.#....#.
.#....#.
.######.
.#....#.
.#....#.
........

Yes

9 8
........
##....#.
.#....#.
.######.
.#....#.
.#....#.
.#....#.
.#....#.
........

No

8 8
..#.....
..#...#.
..#####.
..#...#.
..#...#.
..#...#.
..#...#.
..#...#.

No

Задача J. Хейтеры единицы ≡

Условие

Настя обожает математику, а сильнее всего Настя любит натуральное число n. Еще у Насти есть q друзей, i-й друг любит натуральное число x_i (причем Настя и ее друзья ненавидят число 1, поэтому n, x ≥ 2).

Настя очень добрый человек, поэтому для i-го друга Настя найдет сумму x_i + x_i² + ...x_iⁿ. Также Настя очень ленивый математик, поэтому каждому другу она будет говорить остаток от деления суммы на 10⁹ + 7.

Помогите Насте! Сообщите для каждого друга его остаток от деления суммы!

Формат входных данных

В первой строке вводятся натуральные числа n и q — любимое число Насти и количество друзей Насти соответственно (2 ≤ n ≤ 10¹⁸, 1 ≤ q ≤ 10⁵).

Во второй строке вводится q натуральных чисел, i-е число равно x_i — любимое число i-го друга (2 ≤ x_i ≤ 10¹⁸).

Формат выходных данных

Выведите q чисел, где i-е число показывает остаток от деления суммы i-го друга на 10⁹ + 7.

Обратите внимание, что каждое из q чисел лежит на промежутке от 0 до 10⁹ + 6.

Примеры тестов

3 4
2 3 5 235235

14 39 155 816225021 

Задача K. Равнозначный перекресток ≡

Условие

В Графоляндии вся транспортная сеть представлена в виде неориентированного графа на n вершинах, пронумерованных от 1 до n. В Графоляндии есть k дорог, i-я дорога соединяет u_i-ю и v_i-ю вершины и имеет покрытие под номером c_i.

В Графоляндии существует определение перекрестка. Перекресток — набор из i-й вершины и всех входящих в нее дорог, причем количество дорог должно быть больше 2. Равнозначный перекресток — перекресток, все дороги которого имеют одинаковые покрытия.

Определите количество равнозначных перекрестков в Графоляндии.

Формат входных данных

В первой строке вводятся числа n и k — количество вершин и дорог соответственно (2 ≤ n ≤ 10⁵, 1 ≤ k ≤ 5 * 10⁵).

Далее вводится k строк, в i-й строке вводятся числа u_i, v_i и c_i — вершины, которые соединяет дорога, и вид покрытия дороги (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ c_i ≤ 10⁹).

Формат выходных данных

Выведите натуральное число — количество равнозначных перекрестков в Графоляндии.

Примеры тестов

7 7
1 2 6
2 3 6
2 4 6
3 5 5
4 5 5
5 6 5
5 7 5

2

Задача L. WYSI ≡

Условие

У Криса и его друзей есть игра под названием «WYSI». Когда кто-то из группы друзей замечает где-либо комбинацию символов «727» (будь то на автомобильном номере, на плакате, в интернете, и т.д.), он должен крикнуть «WYSI!» (что означает «When You See It!») и показать остальным, где он это увидел. Формально говоря, если в какой-либо строке есть подстрока «727», то это является поводом крикнуть «WYSI!». Если же кто-то кричит «WYSI!», увидя при этом строку, в которой можно получить «727» путем удаления из строки одного или больше элементов, то остальные неодобрительно мотают головой, потому что это не так интересно, как если бы они увидели строку, в которой не нужно ничего удалять.

Однажды, гуляя по Москве, Крис с друзьями наткнулись на n строк длины m, и им стало интересно найти в них подстроку «727». Поскольку до сих пор они искали их любимую комбинацию символов лишь в одной строке, они допускают ее получение путем удаления одного или нескольких символов. Также, чтобы сделать задачу еще более интересной, они решили учитывать строки по вертикали!

Но, так как символов оказалось очень много, им требуется Ваша помощь!Помогите Крису и друзьям посчитать минимальное количество символов, которые нужно удалить, чтобы по вертикали или горизонтали оказалась комбинация символов «727»!

Формат входных данных

В первой строке содержатся числа n  — количество строк и m  — длина каждой строки (1 ≤ n,m ≤ 3000).

Далее идут n строк длины m, содержащие цифры и буквы латинского алфавита (строчные и заглавные).

Формат выходных данных

Выведите единственное число - минимальное количество символов, которые нужно удалить, чтобы получить «727».Если это сделать невозможно, вывести -1.

Примечание

• В первом примере по горизонтали уже есть подстрока «727»;
• Во втором примере ни по горизонтали, ни по вертикали нельзя сделать подстроку «727»;
• В третьем примере можно убрать первые два символа из первой и третьей строк, тогда в первом столбце по вертикали получится «727».

Примеры тестов

1 3
727

0

2 3
7ff
2Q7

-1

3 3
007
2Jk
127

4