Задача A. Предусмотрительное жюри

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

Условие

Из правил проведения студенческого командного чемпионата мира по программированию ACM:

Когда команда считает, что она решила задачу, она может послать свое решение на проверку. Решение проверяется на наборе секретных тестов. Если хотя бы один из тестов не проходит, команде сообщается причина (неверный ответ, превышение предела времени и т.д.). Такое решение считается неверным и на результат команды никак не влияет.

Если же решение проходит все тесты, то данная задача считается решенной, и команде начисляется некоторое количество штрафного времени. Штрафное время — это время в минутах от начала тура до момента посылки правильного решения этой задачи на проверку плюс по 20 штрафных минут за каждую неверную попытку по этой задаче (до тех пор, пока решение не прошло все тесты, никакого штрафного времени за задачу не начисляется).

Команды ранжируются по числу решенных задач, а при одинаковом их числе — по штрафному времени (чем штрафное время меньше, тем лучше).

Задача:

Жюри точно уверено, что команда "Super solvers", известная своей непобедимостью, все равно за тур успеет решить все задачи, и, скорее всего, каждую из задач — с первой же попытки (то есть штрафное время за каждую задачу будет равно времени от начала тура до момента ее посылки на проверку). Конечно, жюри может попытаться усложнить задачи, однако оно не хочет этого делать, так как опасается, что в этом случае из остальных команд вообще никто ничего не решит.

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

Среди членов жюри есть тренер этой команды. Он прознал про тактику, которой решила придерживаться команда, а также может примерно оценить время, которое потребуется команде для решения каждой задачи. Жюри прекрасно понимает, что уже никак не может повлиять на число решенных командой задач, но зато, учитывая тактику команды, жюри может влиять на штрафное время, которое получит команда, располагая задачи в разном порядке. В самом деле, если на тур предлагается две задачи, и на решение одной из них команда тратит 10 минут, а на решение второй - 20, то штрафное время команды, если задачи расположить именно в таком порядке, будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую - на 30, 10+30=40). Если же задачи расположить в обратном порядке, то штрафное время будет равно 50 (сначала команда потратит 20 минут, потом еще 10, то есть пошлет задачи на 20-й и 30-й минутах, и штрафное время будет равно 20+30=50).

Жюри хочет, чтобы штрафное время команды "Super solvers" было как можно больше (быть может, это даст хоть какой-то шанс другим командам). Помогите членам жюри расположить задачи в таком порядке.

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

Во входном файле записано сначала число N — количество задач на тур. Затем идет N натуральных чисел, каждое из которых не превышает 300. i-ое из этих чисел задает количество минут, которое (по прогнозу тренера) команда "Super solvers" потратит на решение задач номер i.

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (c.in) Выходной файл (c.out)
1
1
25
1
2
2
20 
10
1 2
3
2
10 20
2 1

Задача B. Хоттаб-share/2

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

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.

В распоряжении шушанчиков имеется один компьютер, подключённый к интернету. Им требуется скачать N файлов, i-й файл размером si мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

1 ≤ si ≤ 1000

Все числа во входном файле целые

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
13 17
13
2
5
13 19 17 14 19
63

Задача C. Vasin Multimedia Player

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

Условие

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

Изучив некоторые аналогичные программы, Вася решил реализовать следующий алгоритм: когда пользователь выбирает файл для воспроизведения, то вместе с этим файлом добавляются также все "похожие" на него файлы в алфавитном порядке. Файлы добавляются даже в случае, если они уже есть в списке воспроизведения. Файлы считаются "похожими", если их имена имеют (непустое) одинаковое начало, после которого идёт символ разделителя либо конец строки. Разделителями считаются символы ' ' (пробел, ASCII 32), '_' (подчёркивание, ASCII 95) и '-' (минус, ASCII 45).

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

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

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

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

Ограничения

1 ≤ N ≤ 100; 0 ≤ M ≤ 100. Все имена файлов различны, состоят из маленьких латинских букв, цифр и разделителей и имеют длину от 1 до 100 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
11
five_-_dont_wanna_let_u_go
symphony 40 part 2 andante
ace of base_-_all_that_she_wants
queen - radio ga ga
symphony 40 part 1 allegro
ace of base_-_happy_nation
symphony
five and queen_-_we will rock you
symphony 40
ace of base_-_beautiful_life
queen - the_show_must_go_on
4
symphony 40
queen - radio ga ga
five and queen_-_we will rock you
symphony 40 part 1 allegro
symphony
symphony 40
symphony 40 part 1 allegro
symphony 40 part 2 andante
queen - radio ga ga
queen - the_show_must_go_on
five and queen_-_we will rock you
five_-_dont_wanna_let_u_go
symphony
symphony 40
symphony 40 part 1 allegro
symphony 40 part 2 andante

Задача D. Построение солдат - 1

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

Условие

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

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

Первая строка содержит число солдат N. В последующих строках содержатся N описаний каждого солдата: рост Ri и имя Si.

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

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

Ограничения

1 ≤ N ≤ 100000 0 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.

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

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

3
1.70 name1
1.75 name2
1.70 name3
    

name2
name1
name3
    

Задача E. k-я порядковая статистика

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

Условие

K-й порядковой статистикой N-элементного массива называется число Аk, которое будет стоять на K-м месте после сортировки этого массива по возрастанию.

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

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

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ N,  − 231 ≤ Ai ≤ 231 − 1

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

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

Задача F. Построение солдат - 2

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

Условие

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

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

Первая строка содержит число солдат N. В последующих строках содержатся N описаний каждого солдата: рост Ri и имя Si.

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

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

Ограничения

1 ≤ N ≤ 100000 0 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.

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

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

3
1.75 name1
1.70 name2
1.76 name3
    

2
    

Задача G. Автомобильные номера

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

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

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

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

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

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

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

Входной файл (numbers.in) Выходной файл (numbers.out)
1
X772KX
9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача H. Ответы к тесту

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

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

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

По этим данным Гена должен определить правильные ответы.

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

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

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

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

Исходные данные таковы, что существует хотя бы один вариант решения.

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

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

Задача I. Сумма+присвоение на отрезке

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

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

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

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

Изначально массив заполнен нулями.

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

На каждый запрос вида

Q l r
нужно вывести единственное число — сумму на отрезке.

Ограничения

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

Входной файл (sum.in) Выходной файл (sum.out)
1
5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
3
2
3
4
2
7

Problem J. Трёхмерное суммирование

Author:-   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Имеется трёхмерный массив чисел. Поступают запросы двух видов. Запрос первого вида заменяет значение в заданной ячейке на заданную величину. Запрос второго вида требует вычисления суммы значений в ячеках заданного параллелепиппеда.

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

Input file format

В первой строке входного файла находится целое число n — общее количество запросов.

Далее следует n строк, содержащих запросы. В начале каждой строки находится число 1 или 2 — тип запроса.

Для запросов первого типа далее в строке содержатся целые числа x, y, z, value — координаты ячейки и новое значение в ней.

Для запросов второго типа далее в строке содержатся целые числа x1, y1, z1, x1, y1, z1 — координаты параллелепиппеда, для которого следет предоставить ответ на запрос.

Output file format

Для каждого запроса второго типа следует вывести единственное число — ответ на запрос.

Constraints

1 ≤ n ≤ 100000;

1 ≤ x, y, z, x1, y1, z1, x2, y2, z2 ≤ 100;

0 ≤ 232 − 1;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
1 1 2 1 10
2 1 1 1 1 1 1
2 1 1 1 2 2 2
2 1 1 2 2 2 2
0
10
0


Задача K. Митинг

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

Условие

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

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

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi, tj > ti.

Напишите программу, составляющую список кандидатов на роль председателя.

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

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n троек натуральных чисел mi pi ti.

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

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

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

Задача L. Лабиринт

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

Условие

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

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

Во первой строке входного файла содержатся числа N, x0, y0, x1, y1. Далее следуют N строк по N символов в каждой — описание лабиринта.

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

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

Ограничения

0 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 1 4 1
..#.
..#.
..#.
....
9

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

Автор:А. Жуплев   Ограничение времени: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
##.#..##
##.#.###
...#.##.
.#.#..#.
##.#.#.#
...#.##.

Задача N. Потерявшиеся

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

Условие

Лабиринт размером N x N клеток состоит из стенок, обозначенных символом '#' (ASCII 35), и проходов, обозначенных символом '.' (ASCII 46). В различных клетках лабиринта находятся два путешественника, потерявшие друг друга. Каждый из них полагает, что сможет найти товарища, если будет двигаться по лабиринту в соответствии со своим планом. Первый путешественник на каждую секунду делает шаг вперёд на одну клетку, если это возможно, либо поворачивает направо, если впереди стена. Второй путешественник действует аналогично, но поворачивает налево.

Требуется определить, встретятся ли когда-нибудь путешественники, и, если да, то после скольки шагов. Первоначальные позиции путешественников заданы координатами (x, y) и направлением d — числом 1, 2, 3, 4 для севера, востока, юга и запада соответственно. Позиция (1, 1) находится в северо-западном углу лабиринта.

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

Первая строка содержит значения N x1 y1 d1 x2 y2 d2. Следующие N строк содержат по N символов каждая — описание лабиринта.

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

Выходной файл должен содержать единственное число — количество шагов до встречи, либо число −1, если встреча не состоится.

Ограничения

2 ≤ N ≤ 10, 1 ≤ x1, y1, x2, y2 ≤ N.

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

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

Задача O. Гвоздики

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

Условие

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

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

В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел  — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).

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

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

Ограничения

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

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

Задача P. Лестница

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

Условие

У лестницы n ступенек, пронумерованных числами 1, 2, ... , n снизу вверх. На каждой ступеньке написано число. Начиная с подножия лестницы (его можно считать ступенькой с номером 0), требуется взобраться на самый верх (ступеньку с номером n). За один шаг можно подниматься на одну или на две ступеньки. После подъёма числа, записанные на посещённых ступеньках, складываются. Нужно подняться по лестнице так, чтобы сумма этих чисел была как можно больше.

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

В первой строке входного файла записано целое число n (1 ⩽ n ⩽ 100). Во второй строке заданы целые числа a1, a2, ... , an через пробел ( − 10 000 ⩽ ai ⩽ 10 000) "--- это числа, записанные на ступеньках.

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

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

Ограничения

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

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

Problem Q. Knuth-Morris-Pratt

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

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Задача R. Сбалансированное дерево revisited

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

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

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

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

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

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

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

1.094s 0.015s 47