Задача A. Хоттаб-share/2 ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.

В распоряжении шушанчиков имеется один компьютер, подключённый к интернету. Им требуется скачать N файлов, i-й файл размером s_i мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.

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

Во входном файле содержится число N — количество файлов, за которым следуют N чисел s_i — размеры файлов в мегабайтах.

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

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

Ограничения

1 ≤ N ≤ 1000

1 ≤ s_i ≤ 1000

Все числа во входном файле целые

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

2
13 17

13

5
13 19 17 14 19

63

Задача B. Океанариум ≡

Условие

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

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

Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.

Рекомендуется рассмотреть частичные решения

• N = 1,
• каждый листок содержит ровно одно название рыбки.

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

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

Ограничения

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

1
2
Carassius auratus
Poecilia reticulata

2

3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead

8

Задача C. Частые подстроки ≡

Условие

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

Например, в строке "ABC ABDC ABCC A" наиболее часто встречающаяся подстрока из двух символов — "AB", а наиболее часто встречающаяся подстрока из трёх символов — "C A".

В случае, если несколько подстрок встречаются с одинаковой частотой, следует вывести первую в лексикографическом порядке.

Рекомендуется рассмотреть частичные решения

• K = 1
• N ≤ 100

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

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

Ограничения

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

sample text
1

e

AABBBBAA
2

BB

sample
6

sample

Задача D. Текст ≡

Условие

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

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

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

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

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

Первая строка входного файла содержит натуральное число k — максимально допустимая длина строки.

Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов "," (запятая), "." (точка), "!" (восклицательный знак) и "?" (вопросительный знак).

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

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

Ограничения

1 ≤ k ≤ 100. Размер входного файла не превышает 50000 байтов.

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

22
This     is a sample text!

This is a sample text!

12
This     is a sample text!

This is a
sample text!