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

Задачи в формате DOC (MS-Word)

Временные ограничения ко всем задачам 1 секунда.

ЗАДАЧИ:

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

Во время удара хулигана Сережи, Коля распался на Машу и бозоны Хигса. Увидев такую физику, Сережа потерял сознание. Коля бы отомстил, но Маша была добрая и простила хулигана. Также она знала, что мусорить не хорошо, и, собрав все бозоны, положила их дома.

Поступив в 30-ку, Маша узнала, что такое бозоны Хигса, и решила помочь мировой физике. Проблема в том, что хранились они в Мега-кубе: устройстве останавливающем время и материю. Так они избежали распада.

Мега кубы плотно прижимаются друг к другу, и создают Гиперкуб. Некоторые мега-кубы не имеют выходы, некоторые имеют односторонние проходы в соседние кубы.

Нужно узнать, за какое минимальное количество переходов Маша может добраться до бозонов, или -1, если невозможно доказать Теорию Большого Взрыва.

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

В первых двух строках координаты двух мега кубов, начала и конца пути. Любая координата -1≤x,y,z≤100. Затем число n строк описывающих проходы, состоящие из координат куба и латинская буква обозначающая направление (Forward, Backward, Up, Down, Left, Right)
Ось Х направлена направо
Ось Y направлена вверх
Ось Z направлена назад
Мега-кубы имеют сторону 1

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

Число - минимальное количество переходов до цели, -1, если достичь нельзя.

Примеры:

0 0 0
1 1 1
4
0 0 0 B
0 0 0 U
0 0 1 U
0 1 1 R

3

0 0 0
1 1 1
1
2 3 4 U

-1

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

Вася Пупкин поступил в ФМЛ №30 и самостоятельно решил отслеживать свои успехи обучения. Вася решил вести журнал своих успехов таким образом: если он в течение дня получил хорошую оценку или узнал для себя что-то новое, в своем журнале он писал единицу, если же наоборот, чего-то не понял или получил плохую оценку, то ноль. За один день в журнале ученика могла появиться большая запись или вовсе ничего. Вскоре у Пупкина появилась проблема - места на компьютере стало не хватать и, поскольку учится он в Тридцатке недавно, он еще не знал нормальных алгоритмов сжатия. Поэтому Вася решил сделать так: раз запись за день состояла только из единиц и нулей, то их можно представить в виде бит и записать в файл целым количеством байтов. Но Васе еще не хватает опыта написать самому программу, которая бы переводила его текстовые файлы в бинарные. Начинающему программисту нужна ваша помощь.

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

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

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

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

Примеры:

010000010100001001000011

ABC

Замечание: Для собственной проверки, полученный файл просматривайте в виде шестнадцатеричных кодов.

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

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

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

Каждая строка состоит из числителя n, знаменателя m, и операции o.
Выполнение операций идет до тех пор пока не встретится операция '='.
Числа целые -200 < m,n < 200, m ≠ 0
Операции '+', '-', '*', '/' и выполняются последовательно.
Гарантируется возможность решения без применения длинной арифметики.

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

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

Примеры:

1 3 +
3 5 +
2 5 =

4 3

5 17 +
7 20 *
0 6 +
1 3 =

1 3

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

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

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

Во входном файле находятся 4 вещественных числа: h - высота, с которой производился бросок, b - расстояние до точки, где кончается аномальная зона, c - расстояние до товарища и v - скорость банки.

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

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

Примеры:

1.5 3 5 4

YES

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

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

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

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

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

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

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

Примеры:

1232
2132

132

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

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

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

Во входном файле содержится число E (1 ≤ E ≤ 7) и число N (1 ≤ N ≤ 100), далее идут две строки одинаковой длины N, состоящие из строчных первых Е букв английского алфавита. Первая строка не шифрована, вторая получена шифрованием шифра.

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

В выходной файл требуется вывести по одной букве шифра на каждую строку файла или -1 если шифра не существует.

Примеры:

3 3
abc
aaa

-1

3 3
abc
abc

A
b
c

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

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

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

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

Во входном файле находится количество задач N (1 ≤ N ≤ 5000), время в секундах t (0 ≤ t ≤ 30000) оставшееся до начала занятий и время в секундах на каждую задачу ti (0 ≤ Σti ≤ 30000).

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

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

Примеры:

5 10 1 4 3 9 8

3

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

Вася Пупкин решил ограбить банк. В банк (кубической формы, окна располагаются на всех 6 гранях, каждое окно занимает всю грань) можно забраться только через окно. Но для успешного ограбления Васе необходимо понять, сколько окон увидит камера, наблюдающая за банком. Камера смотрит в центр куба, являющийся началом координат. Сторона куба равна 2 единицам. Помогите Васе написать программу, решающую эту задачу.

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

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

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

Количество сторон куба, которые видит камера.

Примеры:

-2.434 2.3432 1.234

3

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

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

Ваша задача помочь Васе.

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

Во входном файле содержится целое число N (3 ≤ N ≤ 100) количество палаток, далее находятся N вещественные чисел, координаты палаток x, y (-4000 ≤ x,y ≤ 4000), причем любые три палатки образуют треугольник с ненулевой площадью. Координаты каждой палатки заданы на отдельной строке.

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

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

Примеры:

3
0.0 0.0
1.0 0.0
0.0 1.0

3

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

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

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

Во входном файле содержится целое число N (1 ≤ N ≤ 44) длина строки и целое число K (K ≥ 1).

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

В выходной файл требуется вывести K-ую в лексикографическом порядке Пупкинскую строку длины N. Гарантируется, что такая строка существует.

Примечание: если две строки s₁ и s₂ имеют равную длину и s₁ ≠ s₂, то s₁ лексикографически меньше чем s₂ тогда и только тогда, когда в первом (считая от начала) несовпадающем символе этих строк символ строки s₁ будет меньше символа строки s₂.

Примеры:

3 3

010