Летчик Вася и кочегар Петя

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

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

 

Экипаж ракеты: летчик Вася и кочегар Петя спрыгнули с парашютами за секунду до взрыва и куда-то упали. Местность, на которой они находятся, представляет собой равнину с небольшим круглым озером. Каждый из них умеет плавать со скоростью Vп и бегать со скоростью Vб. Они хотят как можно быстрее встретится. При этом каждый их них мог упасть как на сушу, так и в воду. Требуется определить наименьшее время, через которое два брата смогут встретиться.

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

Во входном файле записаны целые числа (по модулю не более 32768) XВ, YВ, XП, YП -- координаты точек на плоскости, в которых оказались братья, R -- радиус озера с центром в начале координат (R > 0) и скорости Vп и Vб соответственно (Vп, Vб > 0).

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

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

Пример

Ввод

Test #1
150 20 -50 -80
100
50 15

Test #2
1000 1000 1001 1000
1
1 1

Вывод

Test #1
3.4604

Test #2
0.5000

381. "Равняйсь, стройся!"

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

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

 

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

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

В первой строке входного файла содержится три целых числа A, B, C (1 <= A, B, C <= 1000).

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

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

Пример

Ввод

Test #1
2 1 3

Test #2
1 2 1

Test #3
170 216 193

Вывод

Test #1
1 2 3

Test #2
-1

Test #3
216 193 170

От заката до восхода

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

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

 

На улице Вязов, которая неожиданным образом совпадает с осью Ox и протянулась с запада на восток, находится N домов. Дома расположены последовательно, один за другим с запада на восток. Ширина каждого дома равна 100 метрам, а высоты домов - H1, H2,..., HN метров. На восходе солнце находится на востоке, то есть где-то далеко по положительному направлению оси Ox. Во время заката солнце находится далеко на западе, то есть где-то далеко со стороны отрицательного направления оси Ox. Два друга поспорили, когда красивее улица Вязов - в момент восхода или в момент заката. Они решили, что красота вида определяется количеством домов, которые освещаются солнцем, то есть, не загорожены от лучей солнца полностью предыдущими домами. Кто из друзей прав, и сколько освещенных домов он сможет наблюдать? Наблюдение с востока осуществляется на восходе, с запада - на закате.

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

В первой строке входного файла записано натуральное число N - количество домов на улице Вязов (1 <= N <= 1000). Во второй строке содержится последовательность N чисел H1, H2,..., HN, записанных через пробел. Hi обозначает высоту i-ого дома. Все Hi - натуральные числа, не превосходящие 100.

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

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

Пример

Ввод

Test #1
2
1 2

Test #2
3
3 1 2

Test #3
6
4 3 1 2 1 1

Вывод

Test #1
2
2

Test #2
1
2

Test #3
1
4

Палиндромы

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

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

 

Слово называется палиндромом, если оно одинаково читается как слева направо, так и справа налево. Например, слова KAZAK, AA, BRRB, Z - палиндромы, а слова AAB, ABAB, ABAC - нет. Клавиатура компьютера БЕРСМ4 состоит из одного ряда, в котором 62 клавиши. Сначала идут заглавные латинские буквы, затем малые латинские буквы и в конце - цифры (от 0 до 9). Буквы расположены в алфавитном порядке. Клавиши нумеруются слева направо от 1 до 62. Суммой двух символов будем называть символ, расположенный на клавише с порядковым номером, равным сумме номеров клавиш двух данных символов. Например, 'A' + 'A' = 'B' или 'S' + 'm' = '5' (19 + 39 = 58). Если сумма номеров клавиш превосходит 62, такие символы складывать нельзя.
На доске написали слово S. За один ход разрешается стереть любые два подряд идущие символа, и записать на их место сумму. Например, из слова CAAD за один ход можно получить одно из слов: DAD, CBD, CAE. Правило нельзя применять для двух символов, если их нельзя складывать. Какое наименьшее количество ходов потребуется, чтобы получить палиндром?

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

Во входном файле записана строка S. Строка состоит из латинских букв и/или цифр. Ее длина не более 250 символов. Строка S состоит хотя бы из одного символа.

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

Выведите искомое наименьшее количество ходов. Если задача не имеет решения, выведите -1.

Пример

Ввод

Test #1
CAAD

Test #2
AAZBXB

Test #3
0369630

Test #4
9A

Вывод

Test #1
1

Test #2
2

Test #3
0

Test #4
-1

Билетная касса

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

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

 

После летнего перерыва вновь начал курсировать знаменитый поезд "Берляндия". Поезд состоит из одного вагона, места в котором пронумерованы от 1 до M. N человек стоят в очереди и хотят купить по билету на поезд. Каждый из них выбрал в поезде желаемое место (возможно одно место было выбрано более чем одним человеком, а некоторые места вообще остались невыбранными). Когда очередной человек подходит к кассе, он называет номер места, на которое хочет купить билет. Если это место свободно, то ему продают билет на это место. В противном случае кассир ищет первое свободное место. Поиск осуществляется с места №1 до места №M. Если свободного места найти невозможно, то есть весь поезд занят, покупка билета не осуществляется. Ваша задача - для всех мест поезда вывести, какому человеку из очереди был продан билет на это место.

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

Входной файл состоит из K наборов входных данных. В первой строке входного файла записано натуральное число K (1 <= K <= 100). Далее идет 2K строк, по две строки на каждый набор входных данных. В первой строке каждой пары записаны два натуральных числа N, M (1 <= N <= 5000; 1 <= M <= 5000), где N - количество человек в очереди, а M - количество мест в вагоне. Во второй строке записана последовательность A1, A2,..., AN, где Ai (1 <= Ai <= M) означает номер желаемого места i-го человека. Числа в строках разделяются пробелами. Люди подходят к кассе в том порядке, как они заданы во входных данных.

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

Для каждого теста выведите ответ в отдельной строке. Выведите последовательность из M чисел P1, P2,..., PM. Число Pj означает номер человека в очереди, который купил билет на место j. Если на это место билет не был продан, Pj = 0.

Пример

Ввод

3
6 5
2 2 1 5 3 2
2 2
1 1
3 5
2 3 1

Вывод

2 1 3 5 4
1 2
3 1 2 0 0

Средний балл

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

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

 

Школьник Васечкин в течение учебного года записывал, какие оценки получал каждый ученик из его класса. В конце мая он решил посчитать средний балл каждого одноклассника. Так как Васечкин не любит делать расчеты самостоятельно (у него склонность исключительно к записи результатов), он попросил вас посчитать средние баллы. Результаты надо вывести, упорядочив имена школьников в лексикографическом порядке (по алфавиту).

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

В первой строке входного файла задано натуральное K (1 <= K <= 1000) - количество оценок, записанных Васечкиным. Далее в файле содержится 2K строк. В первой строке каждой пары записано имя получившего оценку ученика, а во второй - его оценка. Имя ученика записано заглавными латинскими буквами и не содержит пробелов. Все оценки - целые числа от 1 до 5. Длины всех имен не превосходят 8 букв.

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

Для каждого ученика выведите информацию о нем в формате "ИМЯ_УЧЕНИКА СРЕДНИЙ_БАЛЛ". Результаты надо вывести, упорядочив имена школьников в лексикографическом порядке. Выведите ровно одну запись о каждом ученике. Средний балл надо выводить в виде целого числа, округляя результат вниз.

Пример

Ввод

Test #1
2
PETYA
4
PETYA
5

Test #2
6
VASYA
4
PETYA
3
PETYA
5
SERGEY
4
PETYA
4
VASYA
2

Вывод

Test #1
PETYA
4

Test #2
PETYA 4
SERGEY 4
VASYA 3