Задача A. Яблоки поровну ≡

Условие

В школьной столовой на завтрак раздавали яблоки. Каждому школьнику должно было достаться по одному яблоку, но трём из них удалось незаметно набрать в карманы a₁, a₂ и a₃ яблок соответственно.

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

Например, если у первого школьника 2 яблока, у второго — 3, а у третьего — 4, то третий школьник может передать первому одно яблоко, и тогда у каждого из них будет по 3 яблока.

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

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

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

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

Выходной файл должен содержать целые положительные числа x y z — номер школьника, который отдаёт яблоки, номер школьника, которому отдаёт яблоки школьник x, и количество яблок.

Если у школьников уже одинаковое количество яблок, выведите единственное число 0.

Если решения не существует, выведите единственное число −1.

Ограничения

1 ≤ a_i ≤ 1000; 1 ≤ x, y ≤ 3

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

3 3 3

0

1 3 5

3 1 2

1 3 6

-1

Задача B. Наградные конфеты ≡

Условие

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

Например, если имеется 6 школьников и 3 сорта конфет, то можно определить такие награды из двух конфет каждая: (1, 1), (1, 2), (2, 2), (1, 3), (2, 3), (3, 3).

В то же время, если имеется 7 школьников и 3 сорта конфет, то каждому школьнику придётся выдать уже по три конфеты.

Напишите программу, которая по количеству школьников и количеству сортов конфет определяет наименьшее количество конфет в награде.

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

Входной файл целые числа N K.

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

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

Ограничения

2 ≤ N ≤ 10⁹; 2 ≤ K ≤ 1000

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

6 3

2

7 3

3

100 2

99

Задача C. Поиск баланса ≡

Условие

Назовём строку сбалансированной, если каждая из содержащихся в ней букв входит в строку одно и то же количество раз. Например, строки aaa и bcbccccbbcbb сбалансированы, а строки aab и defed — нет.

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

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит целое число N — количество тестов в файле. Следующие N строк содержат по одной входной строке каждая.

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

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

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

2
bcbccccbbcbba
www

12
3

Задача D. Башня из блоков ≡

Условие

Магистр мистических наук, Вася, только недавно стал магистром, а уже хочет похвастаться.

Чтобы продемонстрировать друзьям свои способности, он решил сделать трюк с большим блоком в форме прямоугольного параллелепипеда.

Вася выбрал три взаимно перпендикулярные грани блока и разрезал блок:

1. N − 1 раз параллельно первой грани, получив слои толщиной a₁, …, a_N,
2. M − 1 раз параллельно второй грани, получив слои толщиной b₁, …, b_M,
3. K − 1 раз параллельно третьей грани, получив слои толщиной c₁, …, c_K.

После всех разрезов блок разделился на N × M × K блоков-параллелепипедов.

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

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

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

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

Первая строка входного файла содержит три целых числа N M K

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

Третья строка содержит M целых чисел b_i — толщина слоёв, параллельных второй грани.

Четвертая строка содержит K целых чисел c_i — толщина слоёв, параллельных третей грани.

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

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

Ограничения

1 ≤ N, M, K ≤ 10⁵

1 ≤ a_i, b_i, c_i ≤ 10³

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

1 1 1
2
3
4

4

2 1 2
1 10
10
8 2

40

Задача E. Чёрная пятница ≡

Условие

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

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

Входной файл содержит целое число N  — количество магазинов. Далее следует N описаний магазинов. Описание i-го магазина состоит из целого числа m_i — количества товаров в магазине с номером i, за которым следует m_i различных чисел a_ij в порядке возрастания — коды товаров, продающихся в этом магазине.

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

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

Ограничения

1 ≤ N ≤ 10⁶; 1 ≤ m_i ≤ 1000

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

4
2 3 5
2 2 3
3 2 3 5
5 2 3 5 7 11

3

2
2 2 3
2 3 5

0

2
5 2 3 5 7 11
5 3 5 7 11 13

6