Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Третья командная олимпиада"

Задача A. Спичрайтер Йоды

(Время: 1 сек. Память: 16 Мб)

У каждого общественного деятеля есть собственный спичрайтер – некто, помогающий в подготовке публичной речи, тот, кто делает ее более выразительной и интересной.

Это относится и к главе Ордена джедаев магистру Йоде, известному нам своими подвигами в «Звездных войнах». На первый взгляд может показаться, что спичрайтеру Йоды приходится тяжелее других: все-таки речь магистра своеобразна и ее изучение требует серьезных усилий. На самом деле все несколько проще. Спичрайтеру Йоды достаточно сначала придумать речь для обычного человека, после чего поменять порядок слов в каждом предложении на обратный. В силу того, что алгоритм преобразования обычной речи в речь магистра Йоды достаточно однообразен, спичрайтер решил автоматизировать этот процесс и попросил Вас написать программу, которая будет преобразовывать речь, составленную им для обычного человека в речь для Йоды.

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

В единственной строке входного файла INPUT.TXT задана речь, составленная спичрайтером. Речь состоит из предложений, отделенных друг от друга точками (точка ставится сразу после последнего слова в предложении). Каждое предложение состоит из слов. Предложение содержит, по крайней мере, одно слово. Соседние слова разделены ровно одним пробелом. Слово – непустая последовательность строчных латинских букв. Строка не содержит лишних пробелов. Гарантируется, что строка не пуста и ее длина не превосходит 20000 символов.

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

В выходной файл OUTPUT.TXT выведите преобразованную для Йоды речь в соответствии с форматом входных данных. Следует строго соблюдать формат вывода речи, описанный во входных данных.

Пример

INPUT.TXTOUTPUT.TXT
1you should solve this problem. its easy.problem this solve should you. easy its.

Система оценки

Решения для предложений, состоящих из одного слова, оцениваются в 10 баллов. Решения для одного предложения оцениваются в 40 баллов.


Задача B. Пирамиды

(Время: 1 сек. Память: 16 Мб)

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам рёбер пирамиды найти её объём.

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

Входной файл INPUT.TXT содержит 6 чисел через пробел – длины рёбер пирамиды ABCD. Длины рёбер – целые положительные числа, не превосходящие 1000. Порядок рёбер: AB, AC, AD, BC, BD, CD.

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

В выходной файл OUTPUT.TXT выведите одно вещественное число с четырьмя знаками после запятой – объём пирамиды.

Примеры

INPUT.TXTOUTPUT.TXT
11 1 1 1 1 10.1179
21000 1000 1000 3 4 51999.9937

Задача C. Дробь

(Время: 1 сек. Память: 16 Мб)

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

Рациональные числа вводятся и выводятся в следующем формате. Если число отрицательно, сначала записывается символ «-» (без кавычек). Затем записывается неотрицательное целое число – числитель дроби. Затем, если знаменатель дроби не равен 1, записывается символ «/» (без кавычек) и натуральное число – знаменатель дроби.

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

Первая строка входного файла INPUT.TXT содержит одно рациональное число – первый операнд. Во второй строке записан знак операции – символ «+», «-», «*» или «/». В третьей строке располагается рациональное число – второй операнд. Числители и знаменатели обоих операндов не превосходят 109. Знаменатель не равен нулю.

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

В выходной файл OUTPUT.TXT выведите рациональное число, являющееся результатом операции.

Примеры

INPUT.TXTOUTPUT.TXT
11/2
+
1/3
5/6
21
+
2
3
31/2
-
1/3
1/6

Задача D. Пирамида

(Время: 3 сек. Память: 32 Мб)

После победы в великой битве Король Ягуар хочет построить пирамиду, которая будет одновременно монументом в честь победы и гробницей для погибших солдат. Пирамида будет построена на поле боя. Она должна иметь прямоугольное основание, состоящее из a столбцов и b строк. Для сохранения останков и оружия павших солдат внутри основания пирамиды будет располагаться небольшая прямоугольная комната, состоящая из c столбцов и d строк.

Архитекторы Короля представили поле боя в виде прямоугольной сетки. Эта сетка состоит из квадратных клеток единичной площади и имеет m столбцов и n строк. Для каждой клетки они измерили ее высоту и получили некоторое целое число.

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

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

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

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

Первая строка входного файла INPUT.TXT содержит шесть целых чисел: m, n, a, b, c и d (3 ≤ m,n ≤ 1000, 3 ≤ a ≤ m, 3 ≤ b ≤ n, 1 ≤ c ≤ a-2, 1 ≤ d ≤ b-2). Далее идет описание поля боя, состоящее из n строк, каждая из которых содержит m целых чисел от 1 до 100, разделенных пробелами. Эти числа соответствуют высотам клеток в одной строке сетки. Первая из этих строк соответствует верхней строке (строке 1) сетки, а последняя – нижней строке (строке n). При этом m чисел в каждой строке соответствуют высотам клеток этой строки, начиная со столбца 1.

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

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

Пример

INPUT.TXTOUTPUT.TXT
18 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2
70

Задача E. Мафия в городе

(Время: 1 сек. Память: 16 Мб)

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

В городе находятся n базовых телефонных станций, некоторые пары которых соединены двусторонними каналами связи. Для удобства, занумеруем базовые станции целыми числами от 1 до n, канал связи в этом случае задается парой чисел (u, v) – номерами станций, которые он соединяет.

Будем говорить, что канал связи (u, v) – контролируется мафией, если захвачена, либо станция u, либо станция v (либо обе).

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: n и m (2 ≤ n ≤ 18, 0 ≤ m). Каждая из последующих m строк описывает один канал связи и содержит по два целых числа: u и v (1 ≤ u, v ≤ n, u ≠ v) – номера базовых станций, соединенных этим каналом связи. Любая пара станций соединена не более, чем одним каналом.

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

В первой строке выходного файла OUTPUT.TXT выведите два числа: k и c – соответственно, минимальное количество базовых станций, которые необходимо захватить для того, чтобы контролировать все каналы связи, и число способов захватить такое количество станций так, чтобы контролировать все каналы связи.

Во второй строке выведите k чисел – номера базовых станций, соответствующих одному из способов захвата.

Примеры

INPUT.TXTOUTPUT.TXT
13 3
1 2
2 3
3 1
2 3
1 2
25 4
1 2
1 3
1 4
1 5
1 1
1

Пояснение

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


Задача F. Юпитер

(Время: 1 сек. Память: 64 Мб)

На поверхности Юпитера приземлился летающий робот, его задачей является исследование поверхности планеты. Поверхность Юпитера представляет собой прямоугольное поле из N×M клеток, каждая из которых представляет лаву или твердую поверхность различной высоты. Для снятия проб грунта роботу необходимо переместиться из клетки с координатами (1,1) в клетку с координатами (X,Y). Для передвижения робот может использовать два типа действий - это переезд и перелет.

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

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

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

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

Первая строка входного файла INPUT.TXT содержит размеры поля N, M (1<=N,M<=100), разделенные пробелом. Во второй строке идут координаты клетки, куда необходимо найти путь X,Y (1<=X<=N, 1<=Y<=M). На третьей строке через пробел указаны целые K и D (0<=K<=10, 0<=D<=100). Далее в M строках идут по N чисел через пробел – высотные отметки участка Юпитера, высота каждой клетки - целое число, лежащее в диапазоне от 0 до 10000 включительно. Высота 0 (ноль) обозначает лаву, на которой останавливаться нельзя, но можно пролететь над ней.

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

В выходной файл OUTPUT.TXT выведите целое число - минимальное количество действий, необходимых для достижения заданной клетки. Если добраться до заданной клетки нельзя, то необходимо вывести в строке слово IMPOSSIBLE.

Примеры

INPUT.TXTOUTPUT.TXT
15 4
5 3
1 6
2 1 4 2 1
1 2 4 2 1
4 4 6 2 1
2 2 2 2 1
5
24 4
4 2
1 3
2 0 0 3
3 0 4 3
4 0 5 2
4 5 5 1
3
33 3
3 3
10 10
1 0 0
1 0 0
0 1 1
IMPOSSIBLE

Задача G. Длина числа

(Время: 1 сек. Память: 16 Мб)

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

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

Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 109).

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

В выходной файл OUTPUT.TXT выведите длину числа N.

Пример

INPUT.TXTOUTPUT.TXT
1122

Задача H. Любимая строка

(Время: 1 сек. Память: 32 Мб)

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

Помогите Васе собрать его любимую строку!

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M (N ≤ 106, M ≤ 20 000) – длина строки и количество кусков соответственно. Во второй строке задана S – любимая строка Васи, состоящая из N строчных букв латинского алфавита. Следующие M строк содержат куски исходной строки, по одному на каждой строке. Гарантируется, что N делится на M, все куски имеют одинаковую длину и из них можно составить строку S.

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

В выходной файл OUTPUT.TXT выведите M различных целых чисел ai – последовательность номеров кусков, в которой их следует склеивать, чтобы получить исходную строку. Если решений несколько, выведите любое.

Пример

INPUT.TXTOUTPUT.TXT
112 3
cabacaqwerty
erty
caba
caqw
2 3 1


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483