Преобразование последовательности

Маскарад

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Совсем скоро в Берляндии состоится первый традиционный Всеберляндский маскарад. Правительство Берляндии в срочном порядке сформировало министерство по подготовке маскарада. Перед министерством встала сложная задача: известно, что 1 метр ткани стоит P бурлей, а на пошив костюмов членам правительства необходимо приобрести N метров ткани. Ваша задача, сколько бурлей потратит министерство на покупку ткани.

Входные данные

В первой строке входного файла записано два натуральных числа через пробел P и N (1<=P<=100, 1<=N<=100).

Выходные данные

Выведите единственное натуральное число - необходимое количество бурлей на покупку N метров ткани по P бурлей за метр.

Пример

Ввод

3 7

Вывод

Объезд королевства

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

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

Входные данные

Во входном файле содержится индекс клетки, в которой находится король (доска прономерована от 'A' до 'E' слева направо и от 1 до 5 снизу вверх).

Выходные данные

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

Пример

Ввод

Вывод

A1C2E1D3B2D1E3D5B4A2C1E2C3A4C5E4D2B1A3B5D4B3A5C4E5

Возвращение домой

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Король шахматной доски размером 8х8 находится на коне в одной из клеток своего королевства. Он очень озабочен тем, что некоторые клетки его королевства стали непригодными для путешествия верхом. Поэтому он хочет как можно быстрее добраться в свой замок (наш король всегда путешествует на коне).
Вам предстоит выяснить для него [оптимальный] маршрут или выяснить, что такого не существует.

Входные данные

Во входном файле в первой строке содержится индекс клетки, в которой находится король (доска прономерована от 'A' до 'H' слева направо и от 1 до 8 снизу вверх). Во второй строке находится индекс клетки, в которой находится замок короля. В третьей строке без пробелов перечислены клетки, по которым нельзя проехать верхом.

Выходные данные

Пример

Ввод

A1
A2
B4B3

Вывод

A1C2E1D3C1A2

Подсчет войск

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Король шахматной доски решил выяснить боеспособность своей армии. Посыльный объехал все клетки поля и сделал записи обо всех войсках, имеющихся в государстве.
Вам поручено упорядочить полученные данные для предъявления королю. Посыльный обозначал войска большими латинскими буквами P, K, S, L, F. Вы должны вывести этот список в неубывающем порядке, если P<K<S<L<F.

Входные данные

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

Выходные данные

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

Пример

Ввод

PKSLFKSSLF

Вывод

PKKSSSLLFF

Расстановка ладей

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Король шахматной доски размером 8х8 решил выяснить сколько различных способов расставить на его доске K ладей так, чтобы никакие две из них не стояли на одной горизонтали или вертикали. Вам предстоит выяснить это количество способов.

Входные данные

Во входном файле содержится K.

Выходные данные

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

Пример

Ввод

Вывод

Посадка деревьев

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

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

Входные данные

Во входном файле находится натуральное число N не больше 500.

Выходные данные

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

Пример

Ввод

Вывод

Восклицательные знаки

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Мальчик Петя хочет сосчитать количество восклицательных знаков в каждой строке текста. Помогите ему.

Входные данные

Во входном файле находится текст, состоящий не более чем из 10000 символов.

Выходные данные

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

Пример

Ввод

Я - Петя!!!!

Я люблю играть!
Очень!!!!!!! Очень-очень!!!

Вывод

4
0
1
10

Игроки

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

N мальчиков играли в карточную игру. После каждой раздачи был один выигравший и один проигравший. Они сыграли Q раздач и каждый раз записывали кто кому и сколько проиграл (в одной раздаче нельзя выиграть больше 100 очков). Теперь они хотят узнать, сколько каждый из них выиграл (или проиграл). Помогите им.

Входные данные

Во входном файле в первой строке находится натуральное число N (1<=N<=50). В следующих N строках записаны имена мальчиков игравших в игру (длина имени не длиннее 10 символов). В следующей строке записано целое число Q (0<=Q<=100). Далее идет Q строк с результатами раздач в формате "<выигравший игрок> <проигравший игрок> <сумма>".

Выходные данные

В выходной файл необходимо N строк в формате "<имя> <выигрыш>" - выигрыши всех игравших мальчиков (если мальчик проиграл, то его выигрыш отрицателен).

Пример

Ввод

3
Петя
Вася
Саша
3
Петя Саша 10
Петя Вася 20
Саша Вася 10

Вывод

Петя 30
Саша 0
Вася -30

Монеты

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Имеется N монет достоинствами P1, P2,..., PN дуриков. Мальчик Петя хочет узнать S - количество способов выбрать из этих монет Q дуриков. Монеты одинакового достоинства считаются одинаковыми.

Входные данные

Во входном файле в первой строке находятся два целых числа N и Q (1<=N<=50, 1<=Q<=5000). Во второй строке записано N целых чисел - P1, P2,..., PN (1<=Pi<=100).

Выходные данные

В выходной файл необходимо вывести S.

Пример

Ввод

5 3
1 2 1 1 2

Вывод

Треугольники

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

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

Входные данные

Во входном файле находятся 12 целых чисел X1, Y1, X2, Y2, X3, Y3, X'1, Y'1, X'2, Y'2, X'3, Y'3, разделенных пробелами и/или переводами строки - координаты углов треугольников T и T'. Все числа по модулю не превосходят 10000.

Выходные данные

В выходной файл необходимо вывести S, если S<10 или -1 во всех остальных случаях.

Пример

Ввод

0 0 3 0 0 3
1 1 1 3 3 1

Вывод

Преобразование последовательности

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Пусть A - последовательность из N целых чисел (1<=N<=100000, |Ai|<=10000). Требуется постоить последовательность B, где каждый её элемент есть среднее арифметическое чисел последовательности А, индексы которых не превосходят индекса последовательности B, т.е. Bk = (A1 + A2 +... + Ak) / k;

Входные данные

В первой строке входного файла записано N. Вторая строка содержит N чисел, разделенных пробелом - последовательность A.

Выходные данные

В выходной файл нужно вывести N чисел, разделенных пробелом - последовательность B (дробные числа следует выводить с точностью до двух знаков).

Пример

Ввод

5
1 2 5 4 3

Вывод

1.00 1.50 2.67 3.00 3.00

Интервал

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Необходимо найти количество таких целых чисел X, что A<=X<=B.

Входные данные

В первой строке записано A, во второй - B. A и B действительные (|A|, |B|<=10^9) с не более чем двумя знаками после запятой.

Выходные данные

Выведите ответ на задачу.

Пример

Ввод

-2
1.5

Вывод

Последовательность

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Мальчик Петя написал на доске N цифр (0<N<=10). Потом он взял самую маленькую цифру и вместо нее написал цифру K. Теперь он хочет узнать, какие последовательности цифр могли преобразоваться в получившуюся. Вас же он просит сосчитать их количество.

Входные данные

В первой строке записана цифра K, а во второй строке - последовательность цифр, полученная после преобразования. Цифры не разделены пробелами.

Выходные данные

Выведите ответ на задачу.

Пример

Ввод

3
1633

Вывод

Прыжки в длину

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

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

Входные данные

В первой строке записано N (0<N<=100). Далее идет N строк с описанием прыжков Пети. В каждой строке записано целое число S (0<=S<=3000) и символ P. Если P='s', то S измеряется в сантиметрах, а если P='m', то в миллиметрах. Символ P не отделен от S пробелом.

Выходные данные

Выведите в миллиметрах лучший прыжок Пети.

Пример

Ввод

3
110s
1104m
111s

Вывод

1110

Пояснение

111s = 1110m.

Умножение

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Необходимо найти количество различных пар целых чисел (X,Y) таких, что X*Y=Z.

Входные данные

В первой строке записано целое число Z (|Z|<=10^8).

Выходные данные

Выведите ответ на задачу. Если таких пар бесконечно много, то выведите -1.

Пример

Ввод

-6

Вывод

Пояснение

Искомые пары (-6,1), (-3,2), (-2,3), (-1,6), (1,-6), (2,-3), (3,-2), (6,-1).

Пересечение

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Необходимо определить количество точек пересечения двух окружностей. Окружности могут вырождаться в точки.

Входные данные

В первой строке записаны числа x1, y1, r1 - координаты и радиус первой окружности. Во второй строке записаны числа x2, y2, r2 - координаты и радиус второй окружности. Все входные данные целые, неотрицательные, не превосходящие 10000.

Выходные данные

Выведите ответ на задачу. Если пересечений бесконечно много, то выведите -1.

Пример

Ввод

0 0 3
7 0 4

Вывод

Пояснение

Окружности касаются в точке (3,0).

Раскраска квадрата

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

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

Входные данные

Во входном файле в первой строке записано N (1<=N<=50). Далее идет 3 строки по 3 символа. Символ '.' означает, что данная клетка пустая, а 'x' - что в ней стоит ладья.

Выходные данные

Выведите S.

Пример

Ввод

2
x.x
.x.
x..

Вывод

Подсчет

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

Найдите количество натуральных нечетных чисел меньших N.

Входные данные

Во входном файле записано целое число N (-1000<=N<=1000).