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

На данный момент задачи доступны в формате DOC (135 килобайт).

Архив задач в формате MS-WORD: Скачать [31045 байт, архив WinRar].

Архив всех подходов и тестов задач Жюри: Скачать [5777 килобайт, архив Rar].  

ЗАДАЧИ:

Задача A. .
Время работы на одном тесте: 1 секунд
Имя входного файла: simple.in
Имя выходного файла: simple.out
Лимит времени: 1 секунда.

В одном малоизвестном до текущего момента артиллеристском полку служит рядовой Пупкин. Во время караула у рядового появляется огромное количество времени для осмысления вселенского мировоззрения. И в один из таких моментов он задумался над обычными натуральными числами: какие из них сложные или трудные (также именуемые "крутые"), а какие числа попроще, или просто простые (также именуемые "отстойными").

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

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

Во входном файле написано одно натуральное число N (2 ≤ N ≤ 2*10⁹).

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

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

• 1 - если число "крутое",
• 0 - если число "отстойное".

Примеры:

100

1

101

0

Задача B. .
Время работы на одном тесте: 1 секунд
Имя входного файла: unreal.in
Имя выходного файла: unreal.out
Лимит времени: 1 секунда.

Однажды два артиллеристских полка назначили друг другу дипломатическую встречу. Но, очевидно, что кровопролития никто не хотел, поэтому они решили померяться силами в Unreal Tournament. Для этого каждый из них целых полгода придерживал свой отгул. Наконец наступил тот день, когда все солдаты в двух полках уехали на выходные по домам.

Но вот случилась новая проблема: все артиллеристы живут далеко друг от друга, некоторые даже в разных городах, а чтоб "встреча" прошла хорошо, нужно чтобы пинг (т.е. время отклика) сервера до всех артиллеристов был поменьше. И начали артиллеристы решать новую задачу - выбор сервера. Критерием "хорошести" сервера решили считать сумму пингов от сервера до всех артиллеристов. Понятно, что критерий тем лучше, чем сумма пингов меньше.

Помогите артиллеристам оперативно выбрать сервер для увеличения времени "встречи".

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

Во входном файле на первой строке написано общее количество человек в двух полках N (1≤ N ≤ 100). Далее N строк, в каждой из которых написаны через пробел (N - 1) число - пинги от данного артиллериста до всех остальных артиллеристов.

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

В выходной файл надо вывести одно число - номер артиллериста с наименьшим пингом (нумерация идет с 1 до N).

Примеры:

5
30 30 300 3000
15 15 2000 10
40 56 134 13
12 12 56 78
10 10 50 10

5

Задача C. Артиллерийская бухгалтерия.
Время работы на одном тесте: 1 секунд
Имя входного файла: money.in
Имя выходного файла: money.out
Лимит времени: 1 секунда.

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

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

Записанное в строку выражение (числа неотрицательные и не превосходят 100). Длина строки не превосходит 100.

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

Одно число - ответ (не превосходит 10⁹).

Примеры:

a

b

Задача D. 33 зуб.
Время работы на одном тесте: 1 секунд
Имя входного файла: teeth.in
Имя выходного файла: teeth.out
Лимит времени: 1 секунда.

Однажды по просьбе лейтенанта Пупкина в артиллеристский полк приехал новый зубной врач, который сразу же занялся коммерцией. Всего у человека, как известно, 33-1 (то есть 32) зуба, и на удаление каждого из них у стоматолога был собственный прейскурант. Хитрый стоматолог был еще и программистом, поэтому учет удаленных зубов он делал тоже по-хитрому. Зубы каждого артиллериста он хранил в отдельном числе, где i-ый бит отвечал за i-ый зуб, то есть, если зуб был удален, то там находилась единица, если зуб стоматолог не удалял, там был ноль. Хорошо, что хоть количество клиентов он записал по-человечески.

Теперь лейтенанту Пупкину надо проверить, не берет ли стоматолог лишнего, и поэтому он попросил Вас помочь посчитать суммарный доход стоматолога по его учетной книжке.

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

Во входном файле на первой строке написаны 32 целых числа - стоимость удаления каждого из 32 зубов (каждое число неотрицательно и не превышает 1000). На следующей строке находится количество артиллеристов N (1 ≤ N ≤ 1000), которых принимал стоматолог. Затем идут N целых чисел - кодированные стоматологом челюсти каждого из N артиллеристов.

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

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

Примеры:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7
1
2
4
8
16
32
64

7

Подсказка:

Выражение (X & 1) в языке Си и выражение (X and 1) в языке Паскаль возвращает нулевой бит числа X

Задача E. Солнечный удар.
Время работы на одном тесте: 1 секунд
Имя входного файла: sun.in
Имя выходного файла: sun.out
Лимит времени: 1 секунда.

Капитан Иван Тугодум, командир батареи, сделал заказ на изготовление солнечных часов в СовНаноПрибор. Этот сверхсекретный проект под кодовым названием "Солнечный удар" возглавил подполковник Вася Пупкин. Его команда разработчиков является на сегодняшний день одной из лучших, и Васю Пупкина не смутило даже странное место дислокации батареи. Дело в том, что роту Тугодума отослали на планету Еопов. Эта планета, как ни странно, является центром Вселенной, и не она вращается вокруг двух ближайших к ней звезд, а они около нее, причем, по-странному (так, как показано на рисунке). Батарея Тугодума находится в месте, где обе звезды отбрасывают тень. Прибор оснащен передовыми нанодатчиками, которые позволяют определить скорость вращения и угол поворота каждого из солнц относительно их положения вначале года. Известно, что звезды сходятся в одном месте только один раз в году - в начале года, а также, известно, сколько дней в году и сколько часов в сутках. Требуется определить количество часов, которое осталось до Нового Года.

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

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

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

Выходные данные состоят из одного числа - количество часов с точностью до 2 знаков после запятой.

Примеры:

0.749926829268292680 0.467 214 330

410.00

Задача F. Папироса.
Время работы на одном тесте: 1 секунд
Имя входного файла: papiros.in
Имя выходного файла: papiros.out
Лимит времени: 1 секунда.

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

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

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

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

Выходные данные состоят из одного числа - количество возвратов папиросы Васи Пупкина.

Примеры:

12
Vasiliy Pupkin
Fedor Mint
Vasiliy Pupkin
Anatoly Ugandy
Vasiliy Pupkin
Barak Abama
Alexey Terentiev
Vasiliy Pupkin
Ivan Tugodum
Petr Petrov
George Bush
Vasiliy Pupkin

4

Задача G. Отпуск.
Время работы на одном тесте: 1 секунд
Имя входного файла: holiday.in
Имя выходного файла: holiday.out
Лимит времени: 1 секунда.

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

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

В строку записана эта самая последовательность: результаты факторов T - правда (хорошо), F - ложь (плохо), и операции между ними | (или) или & (и). Длина строки не более 1000.

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

Одно слово, YES, если боец получит отпуск, NO, если нет.

Примечание:

Приоритет операции & выше приоритета операции |.

Примеры:

F|T&T

YES

Задача H. Новая артиллерийская пушка.
Время работы на одном тесте: 1 секунд
Имя входного файла: airgun.in
Имя выходного файла: airgun.out
Лимит времени: 1 секунда.

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

Испытания проходят так: самолет летит по прямой, в сторону цели, на определенной высоте H метров, со скоростью V м/с² и в точке X производит выстрел вертикально вниз. Координата цели - X₀. Артиллерийская пушка, согласно инструкции, выстреливает снарядом со скоростью U м/с², а радиус поражения стандартного снаряда - R метров.

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

В первой строке записаны через пробел значения H, U, V, X, X₀, R (0 ≤ H,U,V,X,X₀,R ≤ 1000).

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

В выходном файле должно быть записано:YES - если снаряд поразил цель, NO - в обратном случае.

Примечание:

Если цель находится на границе зоны поражения, то она не разрушается. Ускорение свободного падения считать равным 9.8 м/с². Единица координатной оси Ох (по которой производится вычисление координат) - метр.

Примеры:

100 50 70 120 250 15

YES

Задача I. Вещь-мешок.
Время работы на одном тесте: 1 секунд
Имя входного файла: stuffbag.in
Имя выходного файла: stuffbag.out
Лимит времени: 1 секунда.

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

• Носки - NOSKI
• Шлем - SHLEM
• Автомат - AVTOMAT
• Щетка - SCHETKA
• Нож - NOGH
• Аптечка - APTECHKA
• Портянки - PORTIANKI

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

На первой строке файла находится количество вещей артиллеристов N (1≤N≤2*10⁶). Далее находится список наименований вещей, где каждая вещь - одна из вещь-мешка, записанная английскими буквами.

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

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

Примеры:

10
NOGH
SCHETKA
NOSKI
AVTOMAT
SHLEM
NOSKI
AVTOMAT
NOGH
NOGH
NOGH

AVTOMAT
AVTOMAT
NOGH
NOGH
NOGH
NOGH
NOSKI
NOSKI
SCHETKA
SHLEM

Задача J. Всепоглощающее пламя.
Время работы на одном тесте: 1 секунд
Имя входного файла: flame.in
Имя выходного файла: flame.out
Лимит времени: 1 секунда.

Разведка сообщает, что недалеко от воинской части враги-диверсанты подожгли территорию. Для принятия взвешенного решения о срочной эвакуации начальнику части полковнику Василию Ивановичу Пупкину требуется знать, через какое время огонь настигнет его часть. Вся территория представляет собой граф, вершины которого являются контрольными точками. Каждая из точек соединена с другими через поле или через лес. Поле и лес характеризуются скоростью распространения огня. Таким образом, от одной контрольной точки до другой пламя движется со скоростью, соответствующей данному типу местности.

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

В первой строчке входных данных содержится два вещественных числа и два целых: скорость распространения огня по полю и по лесу, количество контрольных точек (N) и количество связей между контрольными точками (M). В следующей строке записаны координаты воинской части, далее - координаты точки поджога. Далее идут N - 2 строк с парами вещественных чисел: координатами контрольных точек. Следующие M строк содержат 2 числа: номера связываемых контрольных точек в порядке появления их в условии (нумеруются с нуля) и идентификатор местности связи (FOREST или FIELD)
1 < M < 100
1 < N < 10
Максимальная длина пути не превышает 10¹⁰.

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

Выходные данные состоят из одного числа: времени движения огня до базы.

Примеры:

0.410000 84.670000 8 7
-2.126957 8.009308
3.962401 -1.708548
2.604816 3.840052
3.943449 -3.891903
1.534959 2.501419
-4.015412 -1.005127
-1.547960 -4.597064
-3.101382 -3.687155
1 2 FOREST
2 3 FIELD
3 4 FIELD
4 5 FOREST
5 6 FOREST
6 7 FOREST
7 0 FIELD

45.28

Задача K. Шифрованное послание.
Время работы на одном тесте: 1 секунд
Имя входного файла: code.in
Имя выходного файла: code.out
Лимит времени: 1 секунда.

Связист Василий Пупкин из 5-й батареи 8-ого артиллерийского полка 30-й пехотной дивизии по секретным каналам связи получил шифрованное послание, содержащее координаты вражеских укреплений. Для массированного удара из орудий батареи нужно дешифровать сообщение. Сообщение шифруется следующим образом: из каждого символа берется первый бит, затем каждые четыре символа образуют число от 0 до 15.

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

Входные данные состоят из шифрованного сообщения. Оно кодируется заглавными и малыми буквами латинского алфавита, цифрами, круглыми и квадратными скобками. Также, сообщение всегда заканчивается символом '!'.

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

Выходные данные должны состоять из цифр в шестнадцатеричной системе счисления (запись цифр содержит цифры 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, A, B, C, D, E, F).

Примеры:

Thistargetisinpositionwithcoordinate[(1)(1)]!

35B9DB395B7

Задача L. Мухобойка Пупкина.
Время работы на одном тесте: 1 секунд
Имя входного файла: flyfear.in
Имя выходного файла: flyfear.out
Лимит времени: 1 секунда.

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

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

В первой строке записан радиус мухоловки R(1 ≤ R ≤ 20). Во второй - координаты удара x_p, y_p, z_p (0 ≤ x_p, y_p, z_p ≤ 100). В третьей - количество мух на стене - N (0 ≤ N ≤ 1000). И в последующих N строках записаны координаты мух x_i, y_i, z_i (0 ≤ x_i, y_i, z_i ≤ 100).

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

Единственное число - количество убитых мух.

Примечание:

Муха, находящаяся в момент удара на границе зоны поражения мухобойки сносится потоком воздуха, но остается живой.

Примеры:

5
20 30 40
3
20 30 40
80 80 80
21 28 42

2