Problem A. Second Best

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:4 Mb
Output file:output.txt  

Statement

Given the sequence of integers A1, A2, …, AN, find a number As such that there exists exactly one Am > As, and for all k ≠ m Ak ≤ As.

Input file format

Input contains N followed by A1 A2… AN.

Output file format

Output should contain a single integer — As, or  − 1 if no such number exists.

Constraints

1 ≤ N ≤ 1000000, 0 ≤ Ai ≤ 109,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
1 2 3
2
2
4
3 3 2 3
-1

Задача B. Количество слов

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:d.in   Ограничение памяти:64 Мб
Выходной файл:d.out  

Условие

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

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

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

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

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

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

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

Ограничения

Входная строка имеет длину не более 200 символов.

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

Входной файл (d.in) Выходной файл (d.out)
1
Hello , world!
2
2
www.olympiads.ru
3
3
Gyro-compass - this is a ...
4

Задача C. Марсианская лингвистическая реформа

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

Условие

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

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

Марсиане просят написать программу, переводящую слова из старого в новый форматы.

Например, если старое слово имело вид eeaaeeuinfaormaaiatoyuaoics, то новое слово будет таким: eeaaeeuinfaormaaiatoyuaoics informatics.

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

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

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

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

Ограничения

Длина слова находится в диапазоне от 1 до 100 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
eeaaeeuinfaormaaiatoyuaoics
informatics
2
aeeaaayyaaauaaiaaiaacm
acm
3
bzzt
bzzt

Задача D. Фонари

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

Условие

На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

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

  1. N ≤ 2

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

Во входном файле содержится число N, за которым следует N пар целых чисел x1 y1 x2 y2… xN yN.

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

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

Ограничения

1 ≤ N, yi ≤ 100, 0 ≤ xi ≤ 100.

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

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

Задача E. Наименьший общий делитель

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

Условие

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

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

Входной файл содержит целые числа A B.

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

Выходной файл должен содержать единственно целое число — наименьший общий делитель A и B.

Ограничения

1 ≤ A, B ≤ 231 − 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 20
2
2
13 17
1

Задача F. Ближайшие точки

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

Условие

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

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: "На числовой прямой задано n точек. Необходимо найти среди них две ближайшие". Расстояние между двумя точками числовой прямой x и y равно |x − y|.

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

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

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

Вторая строка входного файла содержит n чисел xi - координаты заданных точек числовой прямой.

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

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

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

Если ответов несколько, выведите любой из них.

Ограничения

2 ≤ n ≤ 105

xi - целые числа, не превосходящие 109 по абсолютной величине

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

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

Задача G. Быстрая помощь

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

Условие

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

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности ai минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10000; 1 ≤ ai, L ≤ 1000

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

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

Задача H. Клетчатый сон

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

Условие

Однажды крокодилу Гене приснился сон, будто он видит огромную шахматную доску, столбцы и строки которой пронумерованы числами от 0 до 30000. Как и положено, клетки доски раскрашены в чёрный и белый цвета в шахматном порядке. Левая нижняя клетка доски имеет координаты (0, 0) и окрашена в чёрный цвет.

Во сне Гене не давал покоя вопрос: сколько на доске чёрных клеток с координатами (x, y), такими, что x1 ≤ x ≤ x2 и y1 ≤ y ≤ y2. Проснувшись, Гена первым делом попросил вас написать программу, которая отвечает на этот вопрос по заданным значениям x1, y1, x2, y2.

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

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

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

Выведите единственное число — количество чёрных клеток.

Ограничения

0 ≤ x1 ≤ x2 ≤ 30000, 0 ≤ y1 ≤ y2 ≤ 30000.

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

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

Задача I. 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

Задача J. Неполное решение

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

Условие

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

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

Помимо вышеперечисленного известно, что:

  1. Количество операндов равно N.
  2. Операции в примере выполняются слева направо, т.е. 1+2/3*4 означает ((1+2)/3)*4.
  3. При решении Вася использовал четыре операции: сложение ('+'), вычитание ('-'), умножение ('*') и деление нацело — ('/').
  4. На любом этапе вычислений промежуточный результат по модулю не превосходит 1000

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

Во входном файле содержится целые числа a1 a2… aN — операнды. За которыми следует ответ R.

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

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

Ограничения

2 ≤ N ≤ 1000, |ai| ≤ 1000, |R| ≤ 1000.

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

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

Задача K. Индикатор загрузки

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

Условие

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

Индикатор загрузки представляет собой поле n × m пикселей, отражающее состояние загрузки некоторого файла размером n ⋅ m байт. Все пиксели индикатора нумеруются от 1 до n ⋅ m слева направо сверху вниз, при этом пиксель c номером i окрашен в чёрный цвет, если i-й по счёту байт файла уже загружен, и в белый цвет — в противном случае.

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

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

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

В первой строке входного файла находятся целые числа n m b. Вторая строка содержит четыре числа r1 c1 r2 c2 — координаты видимой части индикатора. Следующие r2 − r1 + 1 строк по c2 − c1 + 1 символов каждая описывают видимую часть изображения: строки с r1-й по r2-ю, столбцы с c1-го по c2-й. Символ '=' (ASCII 61) обозначает чёрный пиксель, символ '.' (ASCII 46) — белый.

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

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

Ограничения

1 ≤ n, m ≤ 104, 1 ≤ b ≤ n ⋅ m, n ⋅ m делится на b нацело.

1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m, r2 − r1 ≤ 100, c2 − c1 ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7 5
2 3 2 3
.
0 28
2
5 7 5
1 5 3 7
.==
==.
..=
21 21

Задача L. Спираль

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

Условие

Квадратная матрица размера n × n заполнена целыми числами от 1 до n2 следующим образом.

Например, при n = 2 и n = 3 матрица принимает вид:

4 3        9 8 7
1 2        2 1 6
           3 4 5

Требуется по данному размеру матрицы n и номеру r вывести r-ю строку матрицы.

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

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

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

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

Ограничения

1 ≤ r ≤ n ≤ 105

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

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

0.560s 0.010s 35