Problem A. Bucket sort

Author:StdAlg   Time limit:3 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of words and sorts it in lexicographical order. Linear order on characters is given by ASCII codes.

Input file format

First line of input file contains integer N — the sequence length. Following N lines contain one word per line. Each word is exactly three letters long.

Output file format

Output file must consist of N lines, each containing one word from sorted sequence.

Constraints

0 ≤ N ≤ 1000000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
KVN
ACM
FSB
GGG
ACM
FSB
GGG
KVN

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

Автор:И. Бураго   Ограничение времени: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

Задача C. Свинья-копилка

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

Условие

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

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

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

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Ci Wi. Все числа во входном файле — целые.

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

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

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1

Задача D. Неполное решение

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

Условие

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

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

Помимо вышеперечисленного известно, что:

  1. Количество операндов равно N.
  2. Операции в примере выполняются слева направо, т.е. 1+2/3*4 означает ((1+2)/3)*4.
  3. При решении Вася использовал четыре операции: сложение ('+'), вычитание ('-'), умножение ('*') и деление нацело — ('/').
  4. На любом этапе вычислений промежуточный результат по модулю не превосходит 1000

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

Во входном файле содержится целые числа a1 a2… aN — операнды. За которыми следует ответ R.

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

В выходном файле должна содержатся строка из N − 1 символа — знаки операций, которые следует подставить в решение, чтобы получить ответ R. Если решений несколько, выведите любое из них, если решений не существует, выведите IMPOSSIBLE.

Ограничения

2 ≤ N ≤ 1000, |ai| ≤ 1000, |R| ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
2
+
2
1
2
2
1
+-
3
10
7
1
/

0.221s 0.047s 19