Задача A. Ежеминутные автобусы ≡

Условие

На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Диспетчерская служба собрала данные за N минут — номера маршрутов каждого автобуса.

Требуется определить максимально возможное время ожидания для пассажира, желающего уехать определённым маршрутом. Т.е. в данной последовательности номеров маршрутов нужно найти два самых удаленных числа, равных между собой. Например, для последовательности 2, 11, 2, 2, 25, 11, 25, 11 максимальное время ожидания равно 4 — для маршрута номер 11.

Формат входного файла

Входной файл содержит число N, за которыми следует N чисел a_i — номера маршрутов.

Все числа целые. Каждый номер маршрута встречается не менее двух раз.

Формат выходного файла

Ограничения

2 ≤ i ≤ 10⁶

1 ≤ a_i ≤ 100

Примеры тестов

8
2 11 2 2 25 11 25 11

4

4
23 23 41 41

1

Задача B. Подсчёт баллов за задачу ≡

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в a_i баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

Формат входного файла

В первой содержится единственное число N.

Во второй содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

Примеры тестов

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача C. Слон на шахматной доске ≡

Условие

Слон — шахматная фигура, которая может двигаться на любое число клеток по диагонали.

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится слон. Требуется вывести шахматную доску с изображением слона и всех клеток, в которые он может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка со слоном обозначается символом 'X' (ASCII 88), клетка, в которую может походить слон обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

Формат входного файла

Входной файл содержит целые числа N X Y.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

Примеры тестов

8
3 5

#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#

3 1 2

#*#
X#.
#*#

Задача D. Судьба математика ≡

Условие

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

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1<2
3=1
3>4

12000

Задача E. Джордж ≡

Условие

У Джорджа есть текст на английском языке, в котором он упоминается в третьем лице. Джордж решил для ясности заменить в этом тексте все слова he и He на George. При этом слова hE и HE он не заменяет.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

h

h

hehehe he HE

hehehe George HE

Задача F. Сумма квадратов ≡

Условие

Дано неотрицательное целое число N. Требуется определить, существуют ли такие неотрицательные целые числа x и y, что x² + y² = N.

Формат входного файла

Во входном файле содержится единственное число N.

Формат выходного файла

Выходной файл должен содержать искомую пару целых чисел x y, или  − 1. если такой пары не существует. При наличии нескольких решений вывести любое из них.

Ограничения

0 ≤ N ≤ 1000

Примеры тестов

5

1 2

3

-1

Задача G. Шифр Юлия Цезаря ≡

Условие

Дана строка, состоящая из маленьких букв латинского алфавита. Требуется закодировать строку при помощи шифра Юлия Цезаря. Суть этого шифра такова: каждая буква сдвигается на три позиции по алфавиту, т.е. a заменяется на d, b — на e, p — на s, w — на z, x — на a, y — на b, z — на c.

Формат входного файла

Входной файл содержит строку, которую требуется закодировать.

Формат выходного файла

Выходной файл должен содержать закодированную строку. Закодированная строка должна быть такой же длины, как строка во входном файле.

Ограничения

Длина строки от 1 до 202 символов.

Примеры тестов

hello

khoor

z

c

Задача H. Цифровой секундомер ≡

Условие

Цифровой секундомер может показывать измеренное время по-разному. Например, в виде количества секунд или в формате Ч:ММ:СС.

Напишите программу, которая переводит показание секундомера из количества секунд в формат Ч:ММ:СС.

Если в записи числа минут ММ или числа секунд СС только одна цифра, то следует приписать один ноль слева к этому числу.

Формат входного файла

Входной файл содержит единственное целое число — показание секундомера в виде количества секунд.

Формат выходного файла

В выходном файле должна быть ровно одна строка. Длина этой строки должна быть 7 символов.

Выходной файл не должен содержать пробелов.

Ограничения

Целое число во входном файле находится в промежутке от 0 до 9999 включительно.

Примеры тестов

3600

1:00:00

10

0:00:10

5000

1:23:20

999

0:16:39

Задача I. Двойные тетради Чебурашки ≡

Условие

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

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

У Чебурашки есть N_S одинарных и N_D двойных тетрадей. Все одинарные тетради имеют вес W_S, а все двойные — вес W_D. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

Формат входного файла

Во входном файле содержатся числа N M N_S N_D W_S W_D. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится K_i — число уроков в i-ый день, за которым следует K_i чисел — номера предметов. Все числа во входном файле целые.

Формат выходного файла

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ W_S, W_D ≤ 10⁹

0 ≤ K₁ + K₂ + …  + K_N ≤ 15

2 × N_D + N_S = M

Примеры тестов

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

8

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

4

Задача J. Е ≡

Условие

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

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

Число е, выведенное с точностью 25 знаков равно 2.7182818284590452353602875.

Формат входного файла

Входной файл содержит число n.

Формат выходного файла

Выходной файл должен содержать число e выведенное с точностью n знаков после запятой.

Ограничения

Примеры тестов

4

2.7183

Задача K. Странный переводчик ≡

Условие

Однажды Чубакка решил перепрограммировать C-3PO так, чтобы он преобразовывал речь окружающих в речь в стиле магистра Йоды.

Для этого он использует очень простой алгоритм: он разбивает текст на предложения, в каждом предложении меняет порядок слов на обратный.

Формат входного файла

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

Формат выходного файла

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

Ограничения

Длина каждого предложения не превосходит 255. Всего предложений не больше 30.

Примеры тестов

you don't_want that_cheeseburger.
you want_to_give your_potatoes to_Yoda.

that_cheeseburger don't_want you.
to_Yoda your_potatoes want_to_give you.

Задача L. Аскии графика ≡

Условие

У всего есть свои фанаты, Звездные Войны не являются исключением.

Формат входного файла

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

Формат выходного файла

Посчитайте количество 8 в тексте.

Ограничения

Примеры тестов

    8888888888  888    88888
   88     88   88 88   88  88
    8888  88  88   88  88888
      88  88 888888888 88   88
88888888  88 88     88 88    888888

88  88  88   888    88888    888888
88  88  88  88 88   88  88  88
88 8888 88 88   88  88888    8888
 888  888 888888888 88   88     88
  88  88  88     88 88    8888888

:)

Задача M. R2D2 ≡

Условие

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

Для первого теста Энакен хочет заставить робота пройти от начальной клетки площадки до конечной всеми возможными способами, проходя через каждую клетку ровно 1 раз. Чтобы заставить робота двигаться, юному джедаю надо записать все траектории, которые следует пройти роботу, в виде последовательностей символов 'l', 'r', 'u', 'd'. Символ 'l' означает, что робот должен перейти в левую соседнюю клетку, 'r', 'u', 'd' - в правую, верхнюю, нижнюю соответственно. Энакену лень записывать таким образом все способы перемещения, и он просит вас написать программу, которая напишет их за него.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 1
1
1

1
d

2 2 
1 0
1 1

1 
dr

Задача N. Две кучки ≡

Условие

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4 1 2 3 4

0