Problem A. Second Best ≡

Statement

Given the sequence of integers A₁, A₂, …, A_N, find a number A_s such that there exists exactly one A_m > A_s, and for all k ≠ m A_k ≤ A_s.

Input file format

Output file format

Constraints

Sample tests

3
1 2 3

2

4
3 3 2 3

-1

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

Условие

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

• прописные и строчные (т.е. большие и маленькие) латинские буквы,
• пробелы,
• знаки препинания: точка, запятая, восклицательный и вопросительный знак,
• символ -, обозначающий в некоторых случаях тире, а в некоторых — дефис.

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

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

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

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

Ограничения

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

Hello , world!

2

www.olympiads.ru

3

Gyro-compass - this is a ...

4

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

Условие

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

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

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

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

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

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

Ограничения

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

eeaaeeuinfaormaaiatoyuaoics

informatics

aeeaaayyaaauaaiaaiaacm

acm

bzzt

bzzt

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

Условие

На улице длиной в 100 метров установлено N фонарей высотой y₁, y₂, …, y_N метров на расстоянии x₁, x₂, … x_N метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

1. N ≤ 2

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

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

Ограничения

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

3
1 1 50 10 51 10

2

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

Условие

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

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

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

Ограничения

1 ≤ A, B ≤ 2³¹ − 1

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

10 20

2

13 17

1

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ n ≤ 10⁵

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

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

5
10 3 6 2 5

1
2 4

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

Условие

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

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

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

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

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

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

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

Ограничения

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

2 10
8 5

25

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

Условие

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

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

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

Ограничения

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

0 0 1 1

2

3 1 5 4

6

Задача I. Vasin Multimedia Player ≡

Условие

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

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

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

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

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

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

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

Ограничения

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

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

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. Неполное решение ≡

Условие

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

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

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

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

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

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

Ограничения

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

1
1
2

+

1
2
2
1

+-

10
7
1

/

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

Условие

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

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

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

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

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

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

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

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

Ограничения

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

1 ≤ r₁ ≤ r₂ ≤ n, 1 ≤ c₁ ≤ c₂ ≤ m, r₂ − r₁ ≤ 100, c₂ − c₁ ≤ 100.

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

5 7 5
2 3 2 3
.

0 28

5 7 5
1 5 3 7
.==
==.
..=

21 21

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

Условие

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

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

Например, при 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 ≤ 10⁵

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

2 1

4 3

3 2

2 1 6

4 3

6 1 2 11