Командная олимпиада по программированию

Командная олимпиада по программированию

A. Башня степеней

Имя входного файла:	input. txt
Имя выходного файла:	output. txt
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 мегабайта

В выражении вида a^b^c^d^…^g, где ^ обозначает возведение в степень, важен порядок выполнения операций. Например, (2^(3^2))=2^9=512, а ((2^3)^2)=8^2=64. Чтобы полностью задать порядок операций для n возведений в степень, требуется n пар скобок. Петя написал на доске выражение и правильно расставил в нем скобки. Хулиган Вася стер все закрывающие скобки. Помогите Пете восстановить выражение.

Формат входных данных

Входной файл содержит последовательность длины L <  состоящую из открывающих скобок, строчных латинских букв и символов возведения в степень. Последовательность начинается с «(», так как внешние скобки считаются обязательными.

Формат выходных данных

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

Примеры

input. txt	output. txt
((p^(q^a^(b^c	((p^(q^a))^(b^c))
(v^(e^((r^y^((l^(o^n^g	(v^(e^((r^y)^((l^(o^n))^g))))

B. Ближайшее число

Имя входного файла:	input. txt
Имя выходного файла:	output. txt
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 килобайта

Дан массив А из N неотрицательных чисел. Расстояние между двумя элементами ai и aj массива определено как |i – j|. Напишите программу, которая заменяет каждый нулевой элемент массива на ближайший ненулевой элемент. Если два ненулевых элемента находятся на одинаковом ближайшем расстоянии, то значение элемента массива остается равным нулю.

Формат входных данных

В первой строке входного файла содержится одно целое число N (0 ≤ N ≤ 100). В следующей строке через пробел записаны N целых неотрицательных чисел массива А (0 ≤ ai ≤ 1000000).

Формат выходных данных

Выходной файл содержит N чисел – преобразованный массив.

Пример

input. txt	output. txt
6

C. Треугольник в прямоугольнике

Имя входного файла:	input. txt
Имя выходного файла:	output. txt
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 килобайта

Точки (х1, у1), (х2, у2), (х3, у3), (х4, у4) – вершины прямоугольника, а точки (х5, у5),
(х6, у6), (х7, у7) – треугольника. Верно ли, что треугольник целиком содержится в прямоугольнике, и, если да, определить площадь области, принадлежащей прямоугольнику, но не принадлежащей треугольнику.

Формат входных данных

В первой строке входного файла записаны через пробел четыре пары чисел – координаты прямоугольника, а во второй строке, соответственно, три пары чисел – координаты треугольника (-100 ≤ хi, уi ≤ 100). Координаты фигур задаются в порядке обхода по часовой стрелке.

Формат выходных данных

Выходной файл содержит либо слово «YES» в первой строке и искомую площадь (с точностью до 3 знаков после запятой) – во второй, либо слово «NO». Слова «YES» или «NO» записываются прописными буквами.

Примеры

input. txt	output. txt
	YES 18.000
4 5	NO

D. Фальшивые монеты

Имя входного файла:	input. txt
Имя выходного файла:	output. txt
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 килобайта

Чему равно наибольшее число An монет одинакового достоинства, из которых при помощи n взвешиваний на рычажных весах без гирь можно выделить фальшивую монету и определить, тяжелее она или легче настоящих? Известно, что фальшивая монета одна.

Формат входных данных

Во входном файле записано одно число n (n £ 20).

Формат выходных данных

В выходной файл вывести одно число – An.

E. Делимость

Имя входного файла:	input. txt
Имя выходного файла:	output. txt
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 килобайта

Дана последовательность N (N < 10) цифр от 0 до 9. Получить все N-значные числа, составленные из элементов данной последовательности, которые делятся на 2009: если таковых нет, вывести соответствующее сообщение.

Формат входных данных

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

Формат выходных данных

Выходной файл должен содержать полученные числа по одному в каждой строке (в порядке возрастания), или же сообщение об их отсутствии (слово «NO», записанное прописными буквами).

Пример

input. txt	output. txt
5	NO
6	204918 421890 982401

F. Шифротекст

Имя входного файла:	input. txt
Имя выходного файла:	output. txt
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 килобайта

Дан зашифрованный текст (шифротекст). Написать программу расшифровки текста, если известно, что он зашифрован с помощью шифра Цезаря с ключевыми элементами при использовании русского алфавита с 33 буквами.

Алгоритм шифра Цезаря с ключевыми элементами: берется ключевое число (k) и ключевое слово, из которого удаляются повторы букв. Затем, начиная с k-той позиции, записывают это ключевое слово под буквами исходного алфавита, а далее записывают оставшиеся буквы алфавита в естественном порядке. Шифровку получают, заменяя буквы шифруемого текста на соответствующие буквы нового алфавита.

Пример шифровки:

Необходимо зашифровать слово «ШИФРОВАНИЕ», если известно, что k = 15, ключевое слово «КЛЮЧ».

Новый алфавит при заданных ключевых элементах примет вид:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

Исходный алфавит

А

Б

В

Г

Д

Е

Ё

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

Новый алфавит

Р

С

Т

У

Ф

Х

Ц

Ш

Щ

Ъ

Ы

Ь

Э

Я

К

Л

Ю

Ч

А

Б

В

Г

Д

Е

Ё

Ж

З

И

Й

М

Н

О

П

Шифротекст: ЖЪГЧЛТРКЪХ

Формат входных данных

Входной файл содержит в первой строке ключевое число k (1<=k<=33), во второй строке – ключевое слово, в третьей строке – шифротекст, который может состоять из нескольких слов, разделенных знаками препинания и пробелами. Длины ключевого слова и шифротекста не превышают 255 символов.

Формат выходных данных

Выходной файл должен содержать исходное сообщение.

Пример

input. txt	output. txt
15 КЛЮЧ ЖЪГЧЛТРКЪХ	ШИФРОВАНИЕ