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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

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

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

Problem B. Count Squares ≡

Author:B. Vasilyev, A. Klenin   Time limit:3 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Given a set of points with integer coordinates xi, yi, i = 1… N, your program must find all the squares having each of four vertices in one of these points.

Input file format

Input file contains integer N followed by N pairs of integers xi yi.

Output file format

Output file must contain a single integer — number of squares found.

Constraints

−104 ≤ xi, yi ≤ 104, 1 ≤ N ≤ 2000. All points in the input are different.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
4 0 0 4 3 -3 4 1 7
 
1
2 
9
1 1  1 2  1 3  
2 1  2 2  2 3  
3 1  3 2  3 3
 
6

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

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

Условие

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

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

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

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

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

Первая строка входного файла содержит число N. Далее следует последовательность из N описаний листков. В первой строке каждого описания содержится число рыбок Ki, в последующих Ki строках — названия рыбок.

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

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

Ограничения

1 ≤ N, Ki ≤ 50, длина названий не превосходит 255 символов.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
2
Carassius auratus
Poecilia reticulata
 
2
2 
3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead

8

Задача D. Имена файлов ≡

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

Условие

I wish we had some way to handle it sanely, but I don't think a sane solution to case-insensitivity exists.

Linus Torvalds

На компьютере под управлением операционной системы Linux имеется каталог, содержащий N файлов. Пользователю требуется скопировать эти файлы на компьютер, работающий под управлением ОС Windows. К сожалению, файловая система Windows имеет странное свойство. Несмотря на то, что она сохраняет большие и малые буквы в именах файлов, имена, отличающиеся только регистром букв, считаются одинаковыми. Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании на файловую систему Windows попадут в один и тот же файл.

Чтобы избежать потери данных, предлагается при копировании переименовывать файлы по следующим правилам:

  1. Файлы копируются в порядке перечисления в исходном каталоге.
  2. Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
  3. Если при копировании очередного файла выяснилось, что файл с таким именем уже был скопирован, то к имени текущего файла добавляется суффикс "1".
  4. Если имя, полученное после присоединения суффикса, также уже встречалось, то перебираются суффиксы "2", "3", ..., "10", "11", ... до тех пор, пока не найдётся суффикс, дающий уникальное имя.

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

Входной файл содержит количество имён N, за которым следует N строк с именами. Имена состоят из латинских букв и цифр и имеют длину от 1 до M символов.

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

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

Ограничения

1 ≤ N ≤ 10000, 1 ≤ M ≤ 255

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4
aA
Aa
aa
AA1
 
aA
Aa1
aa2
AA11

Задача E. Укорачивание текста ≡

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

По заданному тексту длины N и образцу длины K определить длину минимальной подстроки в тексте, которая удовлетворяет данному образцу. Текст состоит только из маленьких латинских букв. Образец содержит маленькие латинские буквы и символ '*', заменяющий любое множество любых символов(в том числе пустое).

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

В первой строке входного файла находятся два числа K и N, в следующих двух строках находятся соответственно образец и строка.

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

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

Ограничения

1 ≤ N ≤ 1000000, 1 ≤ K ≤ 100

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 4
a*b
abab

2
0.166s 0.014s 19