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

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

Условие

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

Задача B. Дискретный логарифм ≡

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

Условие

Даны целые положительные числа b, a1, a2, ..., aN. Требуется вычислить значения floor(logba1), …, floor(logbaN), где floor(x) — наибольшее целое, не превосходящее x.

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

Входной файл содержит числа N b a1 a2 ... aN по одному числу в строке.

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

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

Ограничения

1 ≤ N ≤ 1000, 2 ≤ b ≤ 100, 1 ≤ ai < 101000 (т.е. числа содержат до 1000 цифр).

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
2
1023
 
9

Задача C. Симметрия ≡

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

Условие

Прямая задана координатами двух своих различных точек плоскости. На этой же плоскости своими коодинатами заданы еще N точек. Для каждой из них требуется определить, есть ли для нее симметричная относительно данной прямой.

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

Входной файл содержит в первой строке разделенные пробелами координаты двух различных точек прямой: x1,y1,x2,y2. Во второй строке находится число N. Далее следует N пар чисел x,y, разделенных пробелами и/или переводами строк.

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

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

Ограничения

1 ≤ N ≤ 2000 Все коодинаты - целые числа, не превышающие по модулю 10^4.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
0 0 1 1
4
0 2
-1 -1 
2 0
3 4
 
1 1 1 0
0.029s 0.005s 11