Задача A. Alice and numbers ≡

Условие

Юная программистка Алиса не любит целое число K.

Алиса хочет узнать количество целых чисел в диапазоне от 1 до N включительно, не делящихся на K.

Формат входных данных

Входные данные содержат два целых числа N и K.

Формат выходных данных

Выведите единственное целое число — количество целых чисел, не делящихся на K.

Ограничения

2 ≤ N ≤ 10⁹

1 ≤ K ≤ 100

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

5 2

3

4 2

2

Задача B. Blown by the wind ≡

Условие

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

Утром Вася обнаружил, что из-за сильного ветра, который дул ночью то в одну то в другую сторону, некоторые камни укатились в разные стороны. Теперь в M целочисленных координатах y_i находится по b_i камней.

Тем не менее, относительное положение камней не могло измениться. Т.е. если первый камень находился в координате x₁, а второй камень — в координате x₂ > x₁, то их координаты y будут удовлетворять неравенству y₂ ≥ y₁. Камни, находившиеся в одинаковых координатах x могут попасть в разные координаты y.

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

Формат входных данных

Первая строка содержит целое число N.

Следующие N строк содержат по два целых числа, разделенных пробелом — x_i, a_i, в порядке возрастания x_i.

Следующая строка содержит целое число M.

Следующие M строк содержат по два целых числа, разделенных пробелом — y_i, b_i, в порядке возрастания y_i.

The next M lines contain two integers each, separated by a space — y_i, b_i, in ascending order of y_i.

Формат выходных данных

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

Ограничения

1 ≤ N, M ≤ 10⁵

 − 10⁹ ≤ x_i, y_i ≤ 10⁹

1 ≤ a_i, b_i ≤ 10⁹

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

3
1 1
2 1
3 1
1
3 3

1

2
1 5
2 1
4
1 2
2 1
3 1
4 2

2

Задача C. Caterpillar ≡

Условие

Гусеница длины L ползёт по пересечённой местности. Пересечённую местность можно представить в виде одномерного массива из N клеток с разными высотами. Клетка a_i называется спуском, если a_i > a_i + 1. Клетка a_i называется подъёмом, если a_i < a_i + 1. Изначально гусеница занимает первые L клеток.

Чтобы продвинуться на одну клетку вперёд, гусеница тратит 1 секунду времени. Однако если среди занимаемых ей клеток спусков больше, чем подъёмов, и голова гусеницы находится на спуске, то она моментально продвигается вправо на одну клетку.

Определите, через сколько секунда голова гусеница достигнет последней клетки.

Формат входных данных

Первая строка входных данных содержит два целых числа L, N. Вторая строка содержит N целых чисел a_i.

Формат выходных данных

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

Ограничения

1 ≤ a_i, N, L ≤ 10⁶, L ≤ N, a_i ≠ a_i + 1

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

1 4
4 3 2 3

1

3 10
10 9 8 7 8 9 10 9 8 7

4

Задача D. Duel of battleships ≡

Условие

В бою сошлись два парусных линейных корабля. Каждый из кораблей имеет длину L метров. Орудия на кораблях расположены через каждый метр и направлены строго перпендикулярно кораблю. Первое орудие расположенно на расстоянии 1 метр от начала корабля. Мощность каждого орудия на первом корабле p₁, а на втором p₂.

Дуэль линейных кораблей проходит следующим образом: два корабля плывут навстречу друг другу по параллельным траекториям, в определённый момент капитан корабля даёт приказ "огонь" и все орудия на борту корабля стреляют в своём направлении. Два корабля могут выстрелить в любом порядке, в том числе одновременно. Каждый корабль успевает выстрелить ровно один раз. Если в момент выстрела k пушек корабля попадают в корабль противника, то противник получит урон p ⋅ k, где p — текущая огневая мощь орудия стреляющего корабля, и огневая мощь каждого орудия противника снизится на (p ⋅ k)1000.

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

Формат входных данных

Первая строка входных данных содержит три числа: L, p₁, p₂.

Формат выходных данных

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

Ограничения

1 ≤ L ≤ 10⁹; 1 ≤ p₁, p₂ ≤ 10⁷

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

4 100 100000

100

10.0 1000.0 112

9989.92

Задача E. strEss ≡

Условие

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

Словарь имеет ряд особенностей: в слове может быть ровно один основной вариант ударения (обозначается символом ') и ноль или более дополнительных вариантов ударения (обозначаются символами "). Петю интересует только основной вариант ударения. Кроме того, в словаре встречаются ошибки, а именно: основное или дополнительное ударение может указывать на согласную букву. При обнаружении ошибки Петя не доверяет словарю и программа должна для этого слова вывести строку NO.

Гласные буквы: a, e, i, o, u, y. Остальные буквы — согласные.

Ваша программа должна обработать K слов и для каждого слова вывести слово с основным ударением (ударная буква должна быть заглавной) или NO, если ударение в словаре стоит некорректно или слова нет в словаре.

Формат входных данных

Первая строка входных данных содержит два целых числа N K. Далее следует N строк, содержащие описание словаря. Следующие K строк содержат слова для расстановки ударений.

Формат выходных данных

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

Ограничения

1 ≤ N, K ≤ 500

Сумма длин всех строк на превосходит 4 ⋅ 10⁴. Все строки состоят из маленьких латинских букв и следующих символов: , ' ". Гарантируется, что в каждом слове есть ровно одно основное ударение и все символы, обозначающие ударения, стоят строго после ударных букв.

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

5 7
apple, a'pple"
stress, stre'ss
cucumber, cu'cu"mbe"r
phonetics, phonetics'
phonetic, ph"o'netic
stress
cucumber
phonetics
phonetic
apple
strass
sdgfousdhg

strEss
cUcumber
NO
NO
Apple
NO
NO

Задача F. Fixed step ≡

Условие

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

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

Если решений несколько, среди них следует выбрать любую подпоследовательность с максимальным шагом.

Формат входных данных

Входные данные содержат единственную строку S.

Формат выходных данных

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

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

Ограничения

0 < |S| ≤ 5000

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

ababbbabab1b2b2b3baa

1 2

abc123xyz456def789pt

0 0

Задача G. Geometric tomography ≡

Условие

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

Пусть имеется некоторый выпуклый многоугольник, вложенный в прямоугольник ABCD со сторонами параллельными осям координат (см. рисунок). Обозначим за P_AB, P_BC, P_CD и P_DA серию фотоснимков, представляющих собой множества вершин исходного многоугольника, которые могут быть спроецированы на соответствующие ребра прямоугольника. Помимо этого будем считать, что существует ровно одна промаркированная вершина, отмеченная на каждом из содержащих ее снимков.

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

Формат входных данных

Во входных данных построчно хранятся множества P_AB, P_BC, P_CD и P_DA, записанные в следующем виде. Вначале идет число вершин N, попадающих в текущее множество. За ними следует ровно N целых чисел — проекции указанных вершин на соответствующее ребро. Далее следует индекс маркерной вершины, под которым она фигурирует в текущем множестве, или  − 1, если она в нем не содержится.

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

Формат выходных данных

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

Ограничения

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

Число вершин многоугольника не превосходит 2 ⋅ 10⁵, а их координаты лежат в диапазоне от 0 до 10⁹.

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

3 54 146 267 -1
4 50 104 210 263 3
4 267 221 117 54 2
3 263 145 50 0

263 117
145 54
50 146
104 267
210 221

4 9 136 257 257 1
4 24 92 221 240 0
4 257 257 136 9 -1
3 240 175 24 2

24 136
92 257
221 257
240 136
175 9

Задача H. Square-convexity: surface ≡

Условие

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

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

Формат входных данных

Входные данные содержат три проекции тела, изображенные ASCII графикой: вид сверху, спереди и справа.

Каждая проекция состоит из символов "." (ASCII 46) — обозначение пустот в описании проекции, и "#" (ASCII 35) — грани квадратновыпуклого тела. Длина ребра блока, представленного каждым символом, равна 1. Гарантируется, что в описании проекции нет строк и столбцов, полностью состоящих из пустот. Описание каждой проекции завершается символом "-" (ASCII 45) в отдельной строке.

Формат выходных данных

Выходные данные должны содержать одно целое число: площадь поверхности.

Ограничения

Ширина и высота каждой проекции не превосходит 100 символов, а объем тела не равен нулю.

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

#
#
#
-
#
#
-
.#.
###
-

18

Задача I. Island cafe ≡

Условие

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

В i-й день Вася тратил на обед в кафе a_i монет. По условиям программы, он мог либо накопить ⌊ 0.01 ⋅ a_i⌋ от суммы обеда в виде бонусов, либо оплатить до ⌊ 0.5 ⋅ a_i⌋ бонусами, которые у него есть.

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

Формат входных данных

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

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

Формат выходных данных

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

Ограничения

1 ≤ N ≤ 10³

1 ≤ a_i ≤ 10⁴

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

2
1000 20

10

3
100 1000 1000

11

Задача J. Square-convexity: volume ≡

Условие

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

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

Формат входных данных

Входные данные содержат три проекции тела, изображенные ASCII графикой: вид сверху, спереди и справа.

Каждая проекция состоит из символов "." (ASCII 46) — обозначение пустот в описании проекции, и "#" (ASCII 35) — грани квадратновыпуклого тела. Длина ребра блока, представленного каждым символом, равна 1. Гарантируется, что в описании проекции нет строк и столбцов, полностью состоящих из пустот. Описание каждой проекции завершается символом "-" (ASCII 45) в отдельной строке.

Формат выходных данных

Выходные данные должны содержать одно целое число: объем тела.

Ограничения

Ширина и высота каждой проекции не превосходит 100 символов, а объем тела не равен нулю.

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

#
#
#
-
#
#
-
.#.
###
-

4

##
##
-
##
##
-
##
##
-

8