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

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

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

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

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

Входной файл содержит целые числа a1 a2 a3.

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 3
0
2
1 3 5
3 1 2
3
1 3 6
-1

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

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 109; 2 ≤ K ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 3
2
2
7 3
3
3
100 2
99

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

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

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

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

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

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
bcbccccbbcbba
www
12
3

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

Автор:Д. Попов, М. Спорышев
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

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

  1. N − 1 раз параллельно первой грани, получив слои толщиной a1, …, aN,
  2. M − 1 раз параллельно второй грани, получив слои толщиной b1, …, bM,
  3. K − 1 раз параллельно третьей грани, получив слои толщиной c1, …, cK.

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M, K ≤ 105

1 ≤ ai, bi, ci ≤ 103

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 1
2
3
4
4
2
2 1 2
1 10
10
8 2
40

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

Автор:И. Блинов, А. Кленин
Входной файл: input.txt   Ограничение времени:3 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

Компания запланировала маркетинговую акцию: "Купите товар A и получите товар B в подарок". Осталось определить, какие именно товары A и B выбрать для акции.

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

Напишите программу, которая подсчитает количество вариантов акции, то есть различных пар кодов товаров (A, B), удовлетворяющих перечисленным условиям.

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

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

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

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

Ограничения

1 ≤ N ≤ 106; 1 ≤ mi ≤ 1000

1 ≤ ni=1mi ≤ 106; 1 ≤ aij ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 5
2 2 3
3 2 3 5
5 2 3 5 7 11
3
2
2
2 2 3
2 3 5
0
3
2
5 2 3 5 7 11
5 3 5 7 11 13
6

0.065s 0.004s 19