Задача 1. Стремление к нулю ≡

Условие

Дано число N и массив из S целых чисел A_i.

За одну операцию можно заменять число N на любое из чисел N + A_i, N − A_i, N × A_i, N / A_i.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

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

Первая строка входных данных содержит целое число N.

Вторая — целое число S.

Третья — S целых чисел, массив A.

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

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

Ограничения

0 ≤ N, A_i ≤ 2 * 10⁹

1 ≤ S ≤ 100

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

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

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

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

100
6
4 7 10 5 25 11

2

Задача 2. Визитки ≡

Условие

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

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

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

Входные данные содержат строку из трёх элементов, разделённых пробелами: 1 элемент — строка из латинских букв языка без пробелов, 2 и 3 элементы — два целых числа A B.

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

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

Ограничения

1 ≤ Длина строки ≤ 10⁵

1 ≤ A * B < 300

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

abaaba 3 2

aba
aba

kekkekkek 3 4

NO

Задача 3. Типичная вечеринка с бассейнами ≡

Условие

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

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

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

Первая строка входных данных содержит целые числа N К, где N — общее количество бассейнов, K — количество бассейнов, наполненных водой.

Вторая строка входных данных содержит строку S, состоящую из N символов 0 и 1. S_i = 1, если бассейн на позиции i наполнен, S_i = 0 в противном случае.

Гарантируется, что S содержит ровно K единиц.

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

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

Ограничения

1 ≤ K ≤ N ≤ 1000000

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

Решение оценивается пропорционально количеству успешно пройденных тестов.

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

10 3
0010001010
    

4
    

10 2
0000011000
    

0
    

Задача 4. Подстрока с уникальными символами по краям ≡

Условие

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

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

Входные данные содержат одну строку s.

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

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

Ограничения

2 ≤ |s| ≤ 10⁶

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

В первом примере ответом могут быть подстроки abc и bcb. Во втором — bacab.

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

aabcb

3

abacaba

5