Задача A. Светофор

Автор:О. Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Входной файл состоит из одной строки, задающей цвет светофора — RED, YELLOW, GREEN.

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

В выходном файле должна быть одна строка - YES или NO.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
RED
NO

Задача B. Вынутый разворот

Автор:Владивостокская городская олимпиада школьников по информатике 2002/2003   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Во входном файле содержатся два целых числа A и B — номера страниц на стороне листа, в произвольном порядке

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

В выходном файле должно содержаться единственное число:

Ограничения

1 ≤ A, B ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 14
16
2
9 1
0

Задача C. Котенок Гав и сосиски

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В распоряжение котенка Гава и щенка Шарика поступила лента из N сосисок. Они договорились есть ее с разных концов до тех пор, пока не встретятся. Гав съедает VGav сосисок в секунду, а Шарик — VSharik сосисок в секунду.

Напишите программу, которая вычислит количество сосисок, целиком съеденных каждым зверем.

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

Входной файл содержит три целых числа: N — количество сосисок, VGav — скорость Гава, VSharik — скорость Шарика.

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

Выходной файл должен содержать два числа: сначала количество сосисок, целиком съеденных Гавом, а затем количество сосисок, целиком съеденных Шариком.

Ограничения

1 ≤ N ≤ 108; 1 ≤ VGav, VSharik ≤ 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 1 2
3 6
2
2 5 3
1 0
3
2 5 5
1 1

Задача D. Разные буквы

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

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

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

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

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
a
aba
zzzzzcdcd
1
2
3

Задача E. Дифтонги

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
e
ee
eee
ee
2
3
aabbee
cyydyyy
xiixiixiii
aabbee
xiixiixiii

Задача F. CamelCase

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

  1. Слова записываются друг за другом через знак подчёркивания с маленькой буквы (например my_variable).
  2. Слова записываются друг за другом подряд, при этом каждое слово начинается с большой буквы (например MyVariable).

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

Рекомендуется рассмотреть частичные решения:

  1. Имя состоит из одного слова

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

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

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

Выходной файл должен содержать имя переменной, переведённое в другой стандарт.

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
x
X
2
ATest
a_test

Задача G. Пицца

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Далее следует N различных целых чисел ai — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ ai ≤ 109

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
n
1211 ≤ n ≤ 3
2311 ≤ n ≤ 1031
3481 ≤ n ≤ 1051, 2

Получение информации о результатах окончательной проверки

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
1
2
5
8 5 6 10 3
5
3
1
1000000000
1000000000

Задача H. Чемпионат по стрельбе

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:shooting.in   Ограничение памяти:256 Мб
Выходной файл:shooting.out  

Условие

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

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

Будем считать, что участник соревнования занял k-е место, если ровно (k − 1) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

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

Система оценивания

Правильные решения для тестов, в которых n ≤ 1000, оцениваются из 50 баллов.

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

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

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

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

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

Ограничения

3 ≤ n ≤ 105

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

Входной файл (shooting.in) Выходной файл (shooting.out)
1
7
10 20 15 10 30 5 1
6
2
3
15 15 10
1
3
3
10 15 20
0

Задача I. Максимальный перепад

Автор:И. Туфанов, И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

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

Карта региона представляет собой матрицу размером N x N клеток, в каждой клетке которой содержится средняя высота определённого района над уровнем моря. Максимальным перепадом высот называется максимальная величина, на которую отличаются средние высоты двух районов, соседних на карте по горизонтали или по вертикали. Требуется по карте региона определить максимальный перепад высот в нем.

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

Входной файл содержит число N, за которым следуют N2 целых чисел — описание карты региона.

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

Выходной файл должен содержать единственное целое число — максимальный перепад высот в этом регионе.

Ограничения

1 ≤ N ≤ 100. Все высоты — целые числа от 0 до 231−1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 1
1 2 1
1 2 3
2

Задача K. Минимальный лабиринт

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Первая строка входного файла содержит два целых числа — N M.

Далее идут N строк по M символов, описывающие лабиринт:

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

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

Ограничения

1 ≤ N, M ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 7
......#
.#..#.#
....#..
......#
.#..#.#
....#..
2
3 8
##.#..##
##.#.###
...#.##.
.#.#..#.
##.#.#.#
...#.##.

Задача L. Форматирование таблицы

Автор:Зимние сборы 2005   Ограничение времени:2 сек
Входной файл:format.in   Ограничение памяти:64 Мб
Выходной файл:format.out  

Условие

Вам предлагается отформатировать таблицу, данную во входном файле.

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

Первая строка входного файла содержит несколько букв l,c,r. Их количество равно количеству столбцов в таблице. Каждая буква задает расположение текста в соответствующем столбце ( l значит, что текст сдвинут до упора влево, с — что текст расположен по середине, r — что текст сдвинут вправо). Далее следуют не менее двух и не более 100 строк данных, каждая из которых задает соответствующую строку таблицы. Каждая строка содержит несколько записей, разделенных амперсантом ('&') Количество записей в каждой строке равно количеству столбцов. Каждая запись должна располагаться в соответствующем столбце. Первая строка данных задает заголовок таблицы, а остальные — тело таблицы. Знак '&' не содержится в ячейках таблицы.

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

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

Ограничения

  1. длина любой строки входного файла не превышает 250 символов
  2. в таблице не более 100 строк
  3. в таблице не более 100 столбцов

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

Входной файл (format.in) Выходной файл (format.out)
1
lr
EXPRESSION&RESULT
2+2&4
2+2*2&6
+------------+--------+
| EXPRESSION | RESULT |
+------------+--------+
| 2+2        |      4 |
| 2+2*2      |      6 |
+------------+--------+
2
lcr
LEFT&CENTER&RIGHT
1&2&3
the&the&the
longest&longest&longest
kitten&kitten&kitten
blitz&blitz&blitz
+---------+---------+---------+
| LEFT    | CENTER  |   RIGHT |
+---------+---------+---------+
| 1       |    2    |       3 |
| the     |   the   |     the |
| longest | longest | longest |
| kitten  | kitten  |  kitten |
| blitz   |  blitz  |   blitz |
+---------+---------+---------+

Задача M. Слишком вложенные скобки

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана правильная последовательность из круглых скобок. Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более. Например, в последовательности (()((()(())())))(((()))) выделены скобки, вложенные на 3 и более уровней.

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

Первая строка входного файла содержит число N. Вторая строка содержит правильную скобочную последовательность длиной от 2 до 10000 символов.

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

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

Ограничения

1 ≤ N ≤ 5000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
()(())
()(())
2
3
(()((()(())())))(((())))
(()(()))((()))

Задача O. Хоттабыч и гирлянда

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку. Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из N цветных лампочек. Приглядевшись, Хоттабыч насчитал K различных цветов лампочек.

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

Рекомендуется рассмотреть частичные решения

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

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

В последующих N строчках содержатся цвета лампочек гирлянды.

В N+2-й строке входного файла содержится число M.

В последующих 2*M строчках содержатся запросы Хоттабыча (по две строки на запрос).

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

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

Если в запросе указан цвет, отсутствующий на гирлянде, то в качестве ответа следует вывести 1.

Если лампочки обоих цветов есть, но пару найти невозможно, следует вывести 2.

Ограничения

2 ≤ N ≤ 15000

1 ≤ M ≤ 20000

1 ≤ K ≤ 3000

Строка, задающая цвет, состоит из латинских букв, её длина не превышает 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10
Red
Green
Blue
Red
Brown
Green
Yellow
Black
Green
Red
6
Red
Green
Blue
Brown
Yellow
Green
Red
Black
Black
Blue
Orange
Green
0
1
0
1
4
-1
2
10
B
C
D
F
G
E
R
C
A
G
3
C
G
R
B
E
E
1 5 -2

Задача P. Дипломы

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:diploma.in   Ограничение памяти:64 Мб
Выходной файл:diploma.out  

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

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

Ограничения

1 ≤ W, H, N ≤ 109

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

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

Задача Q. Заколдованный аквариум

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.

Очередной понедельник выдался в НИИЧАВО (Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным. Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды, куда на прошлой неделе завезли новый аквариум. Туда и вошел Привалов в самый интересный момент беседы между Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой. Сейчас Кристобаль Хозевич в красках описывал, какие могут возникнуть повреждения всей новейшей системы безопасности, недавно установленной в институте, от всего того количества воды, которым сейчас затапливался его отдел.

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

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

 — Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!

 — Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов

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

 — Ну, раз вы все-таки запечатали отверстия, то спешки особой нет, — продолжил Амвросий Амбруазович, — на прошлой неделе мне, доставили новый большой аквариум, необычной конструкции, а если быть точным, с несколькими прямоугольными отверстиями на лицевой стороне, вот посмотрите.

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны ai метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

 — Так вот, — продолжил Выбегалло, — до появления здесь Кристобаля Хозевича мы проводили эксперимент, целью которого было определить уровень воды в этом аквариуме при заданной конфигурации отверстий.

 — А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

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

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

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

Входной файл содержит числа V M N — соответственно скорость вытекания воды (в м/с), поток втекающей воды (м3/c) и количество отверстий в лицевой стороне аквариума. Далее следует N троек чисел xi yi ai — координаты нижнего левого угла и длина стороны. отверстия номер i. Отверстия не пересекаются и не соприкасаются друг с другом.

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

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

Ограничения

0 < V, M ≤ 1000, 0 ≤ N ≤ 100, 0 ≤ xi, yi, ai ≤ 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0
2.0

Problem R. Lin-log sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Задача S. Слово из кубиков

Автор:A. Klenin   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N, задающих номера кубиков для каждой буквы слова, начиная с первой. Если решения нет, выходной файл должен содержать единственное число 0.

Ограничения

1 ≤ N, K ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
2 5 3 4

0.159s 0.007s 45