matherials (hidden) ≡

• Book: link
• haskell video course: link
• haskell-adv. video course: link
• stepik course: link
• book (ru)

• seg-tree: link

Задача A1. Hello, world! ≡

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)

Задача A2. Произведение двух чисел ≡

Условие

Вам даны два целых числа a и b. Выведите их произведение.

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

В первой и единственной строке входных данных содержатся два целых числа a и b

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

Выведите единственное целое число — произведение a ⋅ b.

Ограничения

10^− 9 ≤ a, b ≤ 10⁹

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

3 4

12

-10 2

-20

Задача A3. Сумма ≡

Условие

Заданы два целых числа: a и b. Требуется написать программу, которая вычисляет их сумму.

Формат входного файла

Входной файл содержит разделенные пробелом целые числа a и b.

Формат выходного файла

Выходной файл должен содержать одно число — сумму чисел a и b.

Ограничения

1 ≤ a ≤ b ≤ 10⁹

Система оценки и описание подзадач

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

Получение информации о результатах окончательной проверки

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

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

2 3

5

Задача A4. FizzBuzz ≡

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

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

23

25

Buzz

30

FizzBuzz

Задача A5. Электронная почта ≡

Условие

В ДВФУ у каждого студента и сотрудника есть персональный адрес электронной почты в домене dvfu.ru.

Требуется написать программу, которая по заданным фамилии, имени и роли пользователя создает адрес его электронной почты в формате [фамилия].[имя]@[роль].dvfu.ru

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

Входные данные содержат три слова в разных строках.

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

Выходные данные должны содержать одну строку — электронный адрес в описанном формате.

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

sporyshev
ms
students

sporyshev.ms@students.dvfu.ru

Задача B1. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

Формат входного файла

Входной файл содержит текущее время — часы и минуты.

Формат выходного файла

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

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача B2. Марфа Геннадьевна и angry birds ≡

Условие

Недавно Марфа Геннадьевна увидела у внука на компьютере игру Angry birds и тоже захотела сыграть в такую игру. Она взяла кур, свиней и решила стрелять курами в свиней из рогатки. Марфа Геннадьевна задумалась: может, не стоит мучить бедных животных и сделать то же самое не с животными, а с математической моделью?

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

Тело имеет массу m кг, начальная скорость равна v₀ м/с и направлена под углом α градусов к горизонту. Ускорение свободного падения принять равным g = 9.8 м/с². Сила сопротивления воздуха равна .

Требуется определить время и дальность полёта курицы.

Формат входного файла

Входной файл содержит вещественные числа m v₀α k.

Формат выходного файла

Требуется вывести в выходной файл вещественные числа T L — время и дальность полёта соответственно с как минимум 2-мя точными знаками после запятой.

Ограничения

0.1 ≤ m ≤ 10

0.1 ≤ v₀ ≤ 20

1 ≤ α  ≤ 90

0 ≤ k ≤ 10

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

1 10 45 0

1.443 10.204

1 10 45 1

1.206 4.955

Задача B3. Новогодний код ≡

Условие

Деду Морозу из Нью-Васюков пишут не стихи, а проги. Дед Мороз любит, когда код программы похож на его бороду, то есть длины строк кода {a_i}Ni = 1 удовлетворяют условию

a₁ < a₂ > a₃ < a₄ > …    ∧   a₁ > a₂ < a₃ > a₄ < ….

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

Напишите программу, которая по указанным длинам строк кода a_i определяет новый набор длин b_i, в котором:

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

Формат входного файла

Входной файл содержит целое число N за которым следует N чисел a_i — длины строк.

Формат выходного файла

Входной файл должен содержать N целых чисел b_i — новые длины строк. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15

Задача B4. Робот, налево! ≡

Условие

В Центре робототехники изобрели робота, который ходит только налево. На вопрос "зачем?" он затрудняется ответить.

Робот занимает одну клеточку и действует по следующему алгоритму.

1. Развернуться влево.
2. Если следующая клеточка не была посещена ранее, то пойти прямо (1). Иначе развернуться вправо и пойти прямо (2).

За шаг вида (1) робот получает 1 очко, за шаг вида (2) — 0 очков. Сколько очков получит робот, сделав N шагов?

Формат входного файла

Входной файл содержит целое число N.

Формат выходного файла

Выходной файл должен содержать число очков.

Ограничения

1 ≤ N ≤ 10⁹

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

1

1

3

3

15

7

Задача B5. Марфа Геннадьевна ест яйца ≡

Условие

У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой. В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.

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

Напишите программу, принимающую на вход список номеров дней, в которые Марфа Геннадьевна съедала яйца, и определяющую, съедала ли она хоть раз более двух яиц в неделю.

Формат входного файла

Входной файл содержит целое число N.

Далее следуют N целых чисел a_i — номера дней, в которые Марфа Геннадьевна съедала яйцо.

Формат выходного файла

Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Ограничения

1 ≤ N ≤ 100

1 ≤ a₁ < a₂ < …  < a_N ≤ 1000

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

3
1 7 8

GOOD

5
1 7 9 12 17

BAD

Задача B6. Числовые ребусы ≡

Условие

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

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

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

Во 2-м примере должно быть написано 2014 + ГОД = СОЧИ, но из-за того, что русские буквы в примерах не отображаются, они были заменены на другие буквы.

Формат входного файла

Входной файл содержит 3 строки, представляющие собой числа, в которых некоторые цифры заменены на не цифровые символы с ASCII-кодом больше 32.

Формат выходного файла

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

Выводить следует те ответы, в которых нет незначащих нулей в начале чисел.

Ограничения

Количество символов в каждом числе во входном файле не превосходит 9.

Общее количество не цифровых символов во всех числах находится в пределах от 1 до 6.

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

drama
drama
teatr

18969
18969
37938

2014
AOB
CODE

2014
789
2803

2014
891
2905

2014
893
2907

2014
896
2910

OXOXO
AXAXA
AXAXAX

90909
10101
101010

2A14
AAB
AODE

2214
221
2435

2214
225
2439

Задача C1. Марфа Геннадьевна и документы ≡

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 1 до N и уже привыкла к тому, что у неё в первом файле лежит первый документ, во втором файле — второй и т.д.

Однажды к Марфе Геннадьевне пришёл в гости внук и стал рассматривать её документы. Разумеется, после этого документы оказались не на своих местах.

Теперь Марфа Геннадьевна хочет переложить документы в правильном порядке так, чтобы минимизировать количество выкладываний и вкладываний документов. Также требуется, чтобы при перекладываниях каждый раз вне папки находилось не более двух документов (чтобы не потерять документы).

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i, где число a_i означает, что в i-м файле лежит документ с номером a_i.

Формат выходного файла

Выходной файл должен содержать целое число K — количество выкладываний и вкладываний документов.

Далее должны следовать K пар целых чисел. Пара  − j i означает выкладывание документа с номером j, находящегося в i-м файле. Пара j i означает вкладывание документа с номером j в i-й файл. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ N. Все числа a_i различны.

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

3
1 3 2

4
-3 2
-2 3
3 3
2 2

4
1 4 2 3

6
-4 2
-3 4
4 4
-2 3
3 3
2 2

3
1 2 3

0

Задача C2. Косточки для собак ≡

Условие

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

Сколько существует способов распределить косточки между собаками, чтобы каждая собака получила хотя бы одну кость?

Например, если собак 2, а косточек 4, то существует 2 способа: либо младшей 1 кость, а старшей 3, либо младшей и старшей по 2 кости.

Формат входного файла

Входной файл содержит целые числа N M.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — искомое число способов.

Ограничения

1 ≤ N ≤ M ≤ 50.

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

2 4

2

3 6

3

Задача C3. В пределе ≡

Условие

Здесь вы можете нарисовать звездочку.

Пусть числа R, r фиксированы. Площадь фигуры, ограниченной звездой с n лучами, обозначим через S_n. Положим S = limn ↦ ∞S_n.

Формат входного файла

Входной файл содержит вещественные числа R r.

Формат выходного файла

Выходной файл должен содержать число S с точностью не менее 3 знаков после десятичной точки.

Ограничения

0 < r ≤ R ≤ 100

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

1 0.4

1.25664

Задача C4. Принтер - 2 ≡

Условие

Аполлинарий Матвеевич недавно купил новый принтер и решил распечатать на нём одну главу из своей любимой книги по микроэлектронике.

Входной и выходной лотки принтера горизонтальные. Принтер работает так: стопка бумаги загружается во входной лоток, принтер берёт по очереди листы от верхнего до нижнего и печатает на них страницы от последней до первой. Принтер печатает на той стороне листа, которая находится сверху во входном лотке, и в выходном лотке эта сторона листа тоже будет сверху. Таким образом, если положить в лоток 3 чистых листа бумаги и распечатать страницы с 1-й по 3-ю, то в выходном лотке страницы будут в таком порядке: 1, 2, 3.

Чтобы использовать меньше бумаги и чтобы распечатки было легче переплести, Аполлинарий Матвеевич предпочитает двустороннюю печать. Такой способ печати обычно вызывает у Аполлинария Матвеевича головную боль, если рядом нет внука-программиста, — текст распечатывается не так, как нужно.

Возможные дефекты:

1. При перелистывании распечатки может оказаться, что страницы расположены в неправильном порядке: 2, 1, 4, 3, ... вместо 1, 2, 3, 4, из-за чего приходится переворачивать каждый лист.
2. Первый лист может оказаться пустым с одной стороны, и Аполлинарий Матвеевич хочет, чтобы пустота была только на последнем листе.

Напишите программу, принимающую на вход диапазон страниц a… b и выводящую минимальную по длине последовательность инструкций для Аполлинария Матвеевича. В начальный момент времени во входном лотке лежит достаточно много чистых листов бумаги.

Коды инструкций:

• 1 — распечатать только нечётные страницы;
• 2 — распечатать только чётные страницы;
• 0 — положить чистый лист сверху стопки, лежащей на столе;
•  − 1 — достать стопку из выходного лотка и положить на стол;
•  − 2 — положить стопку со стола во входной лоток;
• 3 — перевернуть стопку, лежащую на столе.
• 100 — стопка бумаги лежит на столе, и при перелистывании будут просмотрены страницы a,a + 1,…,b. Пойти выпить чаю и съесть французских булок.

Формат входного файла

Входной файл содержит целые числа a b.

Формат выходного файла

Выходной файл должен содержать последовательность инструкций, разделённых пробелами.

Ограничения

1 ≤ a ≤ b ≤ 1000.

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

1 1

1 -1 100

1 10

2 -1 3 -2 1 -1 100

Задача C5. Посейдон ≡

Условие

На этапе автоматизации технического обслуживания прачечной создатели сервиса управления расписанием стирки "Посейдон" (poseidon.dvfu.ru) столкнулись с алгоритмической проблемой.

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

Сервис "Посейдон+" (для персонала) должен вывести алгоритм перемещения поломанной машинки в заданное место с координатами (N, M), на котором машинка не стоит.

Задача разработчиков системы "Посейдон+" — реализовать алгоритм, который найдет оптимальный способ такого перемещения. "Оптимальный" — значит за минимальное число элементарных операций. Элементарная операция — это перемещение любой стиральной машины на свободное место, соседнее с ней по горизонтали или вертикали.

Формат входного файла

N, M ∈ N.

Способ представления стандартный.

Формат выходного файла

x ∈ N₀ — решение задачи оптимизации — минимальное количество перемещений (указания персоналу выводить не нужно).

Способ представления стандартный.

Ограничения

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

2 2

5

5 3

23

3 7

35

Задача C6. Куб со спицами ≡

Условие

Возьмём N³ одинаковых кубиков. Раскрасим кубики в N цветов так, чтобы в каждый цвет было раскрашено ровно N² кубиков. Сложим из всех кубиков один большой куб. Начнём протыкать этот куб спицами параллельно его рёбрам. Любая спица пройдёт сквозь ровно N кубиков.

Требуется сложить куб так, чтобы любая спица проходила сквозь кубики всех N цветов.

Формат входного файла

Во входном файле содержится единственное натуральное число N.

Формат выходного файла

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

Ограничения

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

2

1 2
2 1
2 1
1 2

Задача C7. Две пешки и слон ≡

Условие

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

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

Формат входного файла

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

Формат выходного файла

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача D1. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача D2. Жадная последовательность ≡

Условие

Дана последовательность из N целых чисел a_i. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.

Формат входного файла

Первая строка входного файла содержит целые числа N и M — количество элементов последовательности и количество операций.

Вторая строка входного файла содержит N целых чисел a_i — элементы последовательности.

Формат выходного файла

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 10⁵

 − 10⁴ ≤ a_i ≤ 10⁴

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

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

4 1
1 2 3 4

3 4 3

4 2
3 2 1 1

3 4

Задача D3. Золотая середина ≡

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).

Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа.

Формат входного файла

Входной файла содержит количество чисел n, за которым следуют n целых чисел a_i в порядке их добавления в набор.

Формат выходного файла

Выходной файл должен содержать n целых чисел — значения центрального элемента после каждого добавления.

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

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

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2

Задача E1. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел a_i.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

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

3
1 1 2

1 2 3

2
2 5

-1

Задача E2. Чемпионат по боксу ≡

Условие

В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства p_i (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает c_i. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.

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

Формат входного файла

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел p_i, w_i  — описание боксёров из команды Пахома. Далее N пар чисел p_i, w_i  — описание команды соперников.

Формат выходного файла

Выходной файл должен содержать одно число  — максимальная разница очков которую может получить команда Пахома.

Ограничения

1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 300, 1 ≤ с_i ≤ M; 1 ≤ p_i ≤ 10⁹.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

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

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

-9

8 1
9 1
4 1 
1 1 
16 1 
6 1
14 1
11 1
15 1
12 1
5 1
10 1
2 1
8 1
3 1
13 1
7 1

12

3 3
5 1
10 2
15 3
6 1
11 2
16 3

-1

Задача E3. Очередь в поликлинике ≡

Условие

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

За отдельно взятые сутки была собрана статистика, состоящая из моментов времени t_i, указанных в талоне каждого i-го пациента, и времени m_i, которое было затрачено на его прием.
Требуется определить максимальную длину очереди, которая имела место за текущие сутки, а также время окончания приема последнего пациента.

При решении задачи следует полагать, что все t_i и m_i указывают время в минутах и могут принимать только целочисленные значения. Число минут в сутках полагается равным t_max.

Также известно, что пациентам, которые не успели пройти прием в течение суток, очередь автоматически продлевается на следующий день.
В качестве окончания приема для всех таких пациентов указывается максимально допустимое время t = t_max.

Формат входного файла

В начале входного файла "input.txt" содержится пара натуральных чисел t_max и n, за которыми следует ровно n записей, представленных в виде пар положительных целых чисел t_i и m_i. При этом полагается, что все они упорядочены по возрастанию t_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать два значения: максимальную длину очереди и время завершения последнего приема.

Ограничения

0 < t_max ≤ 10⁶, 0 < (t_i, m_i) ≤ t_max, t_i < t_i + 1

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

1440 10
1 1
2 1
3 2
54 2
349 1
720 2
1024 2
1175 2
1193 1
1205 3

0 1208

1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3

2 1210

Задача F1. Как понять, сколько селёдок? ≡

Условие

Витя, Петя и Олег решили сходить на рыбалку за селёдками. В море селёдок много и каждая из них весит строго целое количество килограмм. Олег провёл классификацию рыбы и выяснил, что массы селёдок образуют последовательность, заданную следующим образом: x_i = x_i − 1 + i. Минимальный вес селёдки составляет один килограмм. Мальчики взяли с собой по ведру, в которое помещается V, P, O килограмм рыбы соответственно. Разумеется, они хотели бы вернуться домой с полными ведрами селёдок.

Так как рыбачить умеет только Витя, а Олег уже свою часть работы закрыл исследованием, то Петя вызвался посчитать, какое минимальное количество селёдок Вите требуется поймать, пока Петя и Олег будут греться у костра.

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

В первом примере в ведро Вити оптимально будет поймать селедку в три килограмма, в Петино две селёдки по килограмму, а в ведро Олега одну селёдку весом в один килограмм. Всего четыре селёдки.

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

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

Входной файл содержит три числа V, P, O — вместимость каждого из вёдер в килограммах.

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

В выходной файл выведите число — минимальное число селёдок, которое следует поймать.

Ограничения

0 ≤ V, P, O ≤ 5 * 10¹¹

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

3 2 1

4

5 0 0

3

Problem F2. Compression research ≡

Statement

Many compression algorithms are based on finding frequently repeating substrings in the input data. Since it is often impractical to search the whole input for repetitions, only a limited compression window is considered on each step.

While researching a new compression algorithm, young computer scientist Vasya encountered the following problem.

Given input string of N bits, let the compression window be any substring of M bits. Inside each compression window, find the maximum number of occurrences of any substring of length L (L ≤ M).

In the sample input 1 below, compression window length is equal to string length, so there is only a single window. Most frequent substring of length 2 is 01, which occurs 5 times.

Input file format

First line of input file contains integers L M. Second line input file contains a string of length N, each character either 0 or 1.

Output file format

Output file must contain N − M + 1 integers — maximum substring frequencies for each compression window.

Constraints

1 ≤ M ≤ N ≤ 2 × 10⁵, 1 ≤ L ≤ 100

Sample tests

2 10
0101010101

5

1 3
1110000

3 2 2 3 3 

Задача Z. Дополнительные баллы ≡