SnarkNews Winter Series-2008, Round 1
Внимание! Во всех задачах количество тестовых случаев не превосходит 40.
Задача А
Болт и гайки
Input File: bolt.in, Output File: bolt.out, Time Limit: 2 sec, Memory Limit:64Mb
Вновь созданная фирма купила заброшенные склады на окраине города. Новому заведующему складами поручили произвести учёт в короткие сроки. Всё шло хорошо, пока случайно не рассыпали контейнеры с болтами и гайками на каждом складе, после чего собрали их в общие (для болтов и гаек) контейнеры, потеряв при этом несколько деталей. Помогите оценить нанесённый ущерб на каждом складе, приняв во внимание, что, помимо потерянных деталей, болт (или гайка) считается непригодным, если он не имеет соответствующей гайки (или болта).
Входные данные:
Во входном файле в первой строке записано число n – количество складов. Далее следуют по две строки для описания положения на каждом складе. В первой строке через пробел записаны три числа: k1, l1, m1 – начальное число болтов (100<=k1<=30000, k1 кратно 100), процент потерянных деталей (0<=l1<=100) и стоимость одного болта (1<=m1<=100) соответственно. Во второй строке через пробел записаны также три числа: k2, l2, m2 – начальное число гаек (100<=k2<=30000, k2 кратно 100), процент потерянных деталей (0<=l2<=100) и стоимость одной гайки (1<=m2<=100) соответственно.
Пример входных данных:
2
1000 10 100
1200 20 90
5000 15 23
4000 17 22
Выходные данные:
В выходной файл записывается n строк, в каждой строке итоговая сумма ущерба на соответствующем складе.
Пример выходных данных:
37000
53600
SnarkNews Winter Series-2008, Round 1
Задача B
Радар
Input File:radar.in, Output File:radar.out, Time Limit: 2 sec, Memory Limit:64Mb
Радар подвергается атаке из четырех точек, являющихся вершинами квадрата, в центре которого и стоит радар. Радар укомплектован специальным щитом, позволяющим блокировать удар, но щит может защищать радар только с одной из четырех сторон, и поворот щита требует времени. Изначально щит направлен в сторону той вершины, откуда будет первая атака. Известно время запуска и скорость ракет, ведущих атаку. Требуется определить, сколько ракет удастся отбить.
Входные данные:
Первая строка входа содержит количество тестов. Первые четыре строки каждого теста содержат время запуска Tx (секунды; 0<Tx<=1000) и скорость полета Vx x-ой ракеты (метры в секунду; 0<Vx<=1000 ракеты перечисляются по часовой стрелке). Далее даны время в секундах, необходимое для поворота щита на 90 градусов Tpov (0<Tpov<=1000)
и половина диагонали квадрата D - расстояние в метрах, предстоящее каждой из ракет (0<D<1000).
Пример входных данных:
2
0 10
5 10
10 10
15 10
5 100
0 10
10 10
5 10
15 10
5 100
Выходные данные:
Для каждого теста в выходной файл выводится строка "ALIVE", если радар переживет все четыре выстрела или число успешно отраженных ракет, если попадания избежать не удастся.
Пример выходных данных:
ALIVE
1
SnarkNews Winter Series-2008, Round 1
Задача C
Шифровка
Input File: encode.in, OutputFile: encode.out, Timelimit: 2 s, Memory Limit:64Mb
Разведкой был перехвачен ряд шифровок, которые передавал Джеймс Бонд. Известно, что каждое послание зашифровано методом циклического сдвига. Суть которого в том, каждая буква заменяется на букву, отстоящую в алфавите от первой на определенном расстояние. Это расстояние называется знаменателем шифра. Так, при знаменателе шифра 2 буква D превратится в F, буква Q - в S, а Z - в B. Известно, что Бонд использует знаменатели от 0 до 25, и составляет послания исключительно из заглавных букв английского алфавита. Знаменатели в шифровках постоянно меняются, так что расшифровать содержимое послания будет не просто. После тщательного анализа удалось примерно определить предмет посланий. Теперь для каждого послания точно известно одно из входящих туда слов.
Входные данные:
Первая строка входа содержит количество тестов. Первая строка каждого теста содержит строку с перехваченным посланием; а во второй строкой - слово, которое обязательно присутствует в этом послании. Обе строки состоят только из заглавных английских букв и содержат не больше 40 символов. Гарантируется, что если шифровка может быть прочитана, то она может быть прочитана однозначно.
Пример входных данных:
3
HELLOAMERICA
KHOORDPHULFD
HELLOAMERICA
KHOORDPHULFD
KHOORDPHULFC
Выходные данные:
Для каждого теста в выходной файл выводится строка "IMPOSSIBLE", если разгадать шифровку невозможно и расшифрованный текст, если это удалось сделать.
Пример выходных данных:
HELLOAMERICA
HELLOAMERICA
IMPOSSIBLE
Пояснение: в первом случае фраза HELLOAMERICA зашифрована со сдвигом 0, во втором - со сдвигом 3; третья шифровка ни при одном знаменателе не будет содержать слово KHOORDPHULFC.
SnarkNews Winter Series-2008, Round 1
Задача D
Волейбол
Input File: volleyball.in, Output File:volleyball.out
Time Limit: 2 sec, Memory Limit:64Mb
Партия в волейболе, выигрывается командой, которая первой набирает 25 очков с преимуществом минимум в два очка. В случае равного счета 24-24, игра продолжается до достижения преимущества в 2 очка (26-24; 27-25).
Две сыгранные партии, закончившиеся с одинаковым счетом, будем считать разными, если строки, в которые вписан порядок набора очков командами, не равны.
Комитет по проведению соревнований по волейболу заинтересовало, сколько различных партий может быть, заканчивающихся со счетом 25:23, оказывается 16123801841550, далее им стало интересно, сколько же существует различных матчей в которых первая команда победила в 3 партиях со счетом 25:23 25:20 25:18, оказывается 10043105786927107686166271970998925000.
Определить, сколько существует различных матчей, заканчивающихся заданным счетом. Два матча закончившиеся одинаковым количеством партий с одинаковым счетом, считаются различными, если есть различно сыгранные партии.
Входные данные:
В первой строке указано число n - количество тестов (n<50).
Далее в каждой строке указано количество партий в матче (от 3 до 5) далее счета в каждой из сыгранных партий. Также известно, что ни одна из команд не набрала более 40 очков. Будем считать, что в 5 партии счет идет тоже до 25 очков.
Пример входных данных
2
3 25:23 25:20 25:18
4 25:23 20: 25 26:24 25:18
Выходные данные
Для каждого теста выводится одна строка, содержащая одно число - количество различных матчей, которые заканчиваются с данным счетом.
Пример выходных данных
10043105786927107686166271970998925000
323866095164273521651645790930981230216140667500000
SnarkNews Winter Series-2008, Round 1
Задача E
Вода.
Input File: water.in, Output File: water.out
Time Limit: 14 sec, Memory Limit:64Mb
Имеется три ведра, ёмкость которых известны и не равны. Самое большое ведро полное, остальные пусты. Требуется добиться, чтобы в самом большом ведре был заданный объем воды. За один шаг вода переливается из одного ведра в другое до тех пор, пока либо не закончится вода в ведре-источнике, либо не наполнится доверху вода в ведре-получателе.
Школьник Василий, чтобы занять себя, пытается решать эту задачу с разными входными данными, но не всегда находит решение. И даже если решение найдено, он хочет знать, является ли найденное решение оптимальным, а именно, используется ли минимальное количество шагов. Требуется написать программу, которая поможет Василию проверить его решение.
Входные данные:
Каждый тест приведён в отдельной строке, и содержит 4 натуральных числа, ёмкости вёдер b1, b2, b3 (1000 > b1 > b2 > b3 > 0), и требуемое количество воды в первом ведре t (b1 > t > 0). Признак окончания тестов - строка с данными b1 = b2 = b3 = t = 0, и этот тест не следует решать.
Пример входных данных:
10 8 4 4
10 8 4 5
0 0 0 0
Выходные данные:
Для каждого теста вывести либо минимальное количество переливаний, либо если задача не имеет решения, то слово IMPOSSIBLE (заглавными буквами).
Пример выходных данных:
3
IMPOSSIBLE
SnarkNews Winter Series-2008, Round 1
Задача F
Стрелок
Input File: gunner.in, Output File: gunner.out
Time Limit: 2 sec, Memory Limit:64Mb
Стрелок стоит в центре стрельбища. На стрельбище несколько мишеней. Пули стрелка пробивают мишени насквозь, не теряя скорости, и могут поразить все мишени, стоящие на одной линии.
Будем считать, что стрелок стоит в центре начала координат. Известны координаты всех мишеней (для простоты будем считать их геометрические размеры пренебрежимо малыми). Определите минимальное число выстрелов, необходимых стрелку для поражения всех мишеней. Расчеты ведутся с точностью 0,001.
Входные данные:
Первая строка входа содержит количество тестов. Первая строка каждого теста количество мишеней N(0<N<=20); далее для каждой из мишеней даны её координаты по оси X и по оси Y (-10<=X, Y<=10; X,Y - целые числа).
Пример входных данных:
2
4
2 2
-2 2
-2 -2
2 -2
6
2 2
-2 2
-2 -2
2 -2
1 1
-1 3
Выходные данные:
Для каждого теста в выходной файл выводится число выстрелов, необходимых стрелку для поражения всех мишеней.
Пример выходных данных:
4
5