Задача A. Брокер ≡

Условие

Брокер Лёша решил подзаработать, для чего собирается совершить N звонков в разные банки. Стратегия Лёши проста: он просит у очередного банка деньги и иногда их получает. Банк под номером i может выдать брокеру ровно m_i денег и делает это только в том случае, если у брокера на момент звонка уже есть r_i денег на счету. С самого начала на счету брокера содержится A денег.

Очередной звонок происходит так: Лёша тратит t_i секунд на то, чтобы выяснить, сколько и при каких условиях банк может дать ему денег. Каждая секунда разговора по телефону стоит ему C денег.

Если счет брокера удовлетворяет условию банка, и если самому брокеру выгодно продолжать разговор, он тратит дополнительно t_i секунд на совершение сделки и вежливое завершение разговора, после чего ему на счет поступает m_i денег. В ином случае Лёша мгновенно отменяет сделку, бросает трубку и получает от банка 0 денег.

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

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

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

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

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

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

Выходные данные должны содержать одно целое число — баланс счета брокера в конце дня. Баланс может быть отрицательным.

Ограничения

0 ≤ N ≤ 10²

0 ≤ A, C, r_i, m_i ≤ 10⁴

1 ≤ t_i ≤ 10³

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

3 1000 10
10 500 1000
1000 0 20
5 2000 8400

100

Задача B. Точка в углу ≡

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x₁, y₁) и (x₂, y₂).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

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

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

Входной файл содержит целые числа x₁ y₁ x₂ y₂ x y — координаты вершин прямоугольника и точки.

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

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

Ограничения

 − 10⁴ ≤ x₁,y₁,x₂,y₂ ≤ 10⁴

min(x₁, x₂) ≤ x ≤ max(x₁, x₂)

min(y₁, y₂) ≤ y ≤ max(y₁, y₂)

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

100 200 300 400 290 210

CORNER

100 200 300 400 200 300

CENTER

Задача C. Бада развешивает зоков ≡

Условие

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

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

В первом примере, приведённом ниже, двоих зоков можно повесить рядом. Для этого хватит 3 прищепок.

Во втором примере в ряд можно повесить троих зоков (на это уйдёт 4 прищепки), а четвёртого зока повесить на другую верёвку, использовав ещё 2 прищепки. Можно также повесить зоков на двух верёвках по два зока на каждой, также использовав в сумме 6 прищепок.

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

Во входном файле содержатся целые числа N и M.

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

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

Ограничения

1 ≤ N, M ≤ 10⁶

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

2 2

3

4 3

6

Задача D. Редактор уровней с грибами ≡

Условие

Юный программист Вася создал аркадную игру. В этой игре герой перемещается по горизонтальным платформам и может собирать грибы. Теперь Вася работает над редактором уровней для этой игры.

Уровень для игры кодируется прямоугольной таблицей символов из N строк и M столбцов. Свободные ячейки таблицы обозначаются символом '.' (ASCII 46). Ячейки, занятые платформами — символом '#' (ASCII 35). Каждый гриб занимает одну ячейку и обозначается символом '*' (ASCII 42).

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 20

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

4 11
..**.......
.###.*..###
....##.....
.##........

2

Задача E. Забор по фен-шую ≡

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту a_i сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a₁ < a₂ > a₃ < a₄ > …, либо условие a₁ > a₂ < a₃ > a₄ < ….

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

Напишите программу, которая по указанным длинам досок a_i определяет новый набор длин b_i, в котором:

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

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

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

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

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

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15

Задача F. В поисках Васи ≡

Условие

Мальчик Влад идёт в гости к своему другу Васе, который живёт в доме с N подъездами и M этажами. На каждом этаже каждого подъезда расположено одинаковое количество квартир. Влад помнит номер Васиной квартиры X (квартиры нумеруются с 1), но не помнит ни номер подъезда, ни этаж.

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

У Влада есть K предположений насчет того, какое количество квартир может быть на одном этаже одного подъезда. Влад собирается вычислить для каждого из K предположений номер подъезда и номер этажа, зайти в соответствующий подъезд, подняться на этаж и позвонить в домофон, чтобы проверить, живёт ли здесь Вася. Перейти из одного подъезда в другой можно только через улицу (0 этаж). Влад может проверять свои предположения в любом порядке.

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

В примере 2 для 1-го и 2-го предположения Вася живёт на 10 этаже 1 подъезда, в то время как для 3-го предположения Вася будет жить на 7 этаже 1 подъезда. Влад может сначала подняться на 7 этаж 1 подъезда для проверки 3-го предположения, а потом подняться на 10 этаж этого же подъезда для проверки предположений 1 и 2.

В примере 3 для 1-го предположения количество квартир в доме будет равно 40, а для 2-го предположения — 60. Ни в том, ни в другом случае в доме не найдётся квартиры с номером 100.

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

Входной файл содержит целые числа N M X K — количество подъездов и этажей в доме Васи, номер его квартиры, количество предположений Влада. Далее следуют K различных целых чисел a_i — предположения Влада о количестве квартир на одном этаже одного подъезда дома Васи.

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

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

Если ни одно предположение Влада не позволяет определить, где живёт Вася, то выведите  − 1.

Ограничения

1 ≤ N, M ≤ 10⁴; 1 ≤ X ≤ 10⁶; 1 ≤ K ≤ 10⁵; 1 ≤ a_i ≤ 10⁵

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

10 10 100
2
1 10

20

10 10 100
3
10 11 15

10

2 10 100
2
2 3

-1

Задача G. Вася и мысли ≡

Условие

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

В начале прогулки Вася размышляет о Важных Вещах, и ноги несут его с постоянной скоростью, равной либо v₁, либо v₂ м/c. Затем Вася отвлекается и начинает думать о Всякой Ерунде. В этот момент его скорость становится равной либо w₁, либо w₂ м/c.

Если Вася затратил на прогулку T секунд, каково максимальное возможное расстояние, пройденное им с Важными Вещами в голове?

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

Первая строка входного файла содержит числа D T. Во второй строке записаны числа v₁ v₂. В третьей строке записаны числа w₁ w₂. Каждое число имеет не более трёх знаков после десятичной точки.

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

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

Входные данные таковы, что решение всегда существует.

Ограничения

1 ≤ D, T ≤ 1000

10^− 3 ≤ v₁ < v₂ ≤ 10²

10^− 3 ≤ w₁ < w₂ ≤ 10²

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

10.0 5.0
1.0 3.0
0.5 1.0

9.0

15.0 3.0
1.0 2.5
4.25 6.1

2.291

25.0 5.0
1.0 3.0
4.0 5.0

0.0

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

Условие

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

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

1. N ≤ 2

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

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

Ограничения

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

3
1 1 50 10 51 10

2

Задача I. Библиотека для списков ≡

Условие

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

Прикрепленный файл представляет собой хедер "linear_sequence.h".

Задача J. Библиотека для динамических массовов ≡

Условие

Смотри задание

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

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

Ограничения

Problem K. Lin-log sort 2 ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Задача O. Быки и коровы 2 ≡

Условие

На одномерном поле длиной N клеток пасутся быки и коровы. Каждая клетка либо пустая, либо занята быком, либо занята коровой.

На поле периодически нападают волки, поэтому пастухи решили оградить участок длиной h клеток.

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

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

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

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

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

Ограничения

1 ≤ N < 10⁵, 1 ≤ h ≤ N

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

15 5
XX...XXYYYXX.YY

6 10

Задача P. Подсчёт баллов за задачу ≡

Условие

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

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

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

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

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

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

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

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача R. Аквалангист ≡

Условие

Аквалангист Джонс находится в море в координате x_j, y_j на глубине h_j метров. Джонс заметил акулу, которая находится в координате x_s, y_s на глубине h_s метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью v_s м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

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

Входные данные содержат в двух строках целые числа x_j, y_j, h_j и x_s, y_s, h_s, v_s.

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

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |x_j|, |y_j|, h_j, |x_s|, |y_s|, h_s ≤ 10⁵

1 ≤ v_s ≤ 100

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

0 0 1
100 100 100 1

YES

0 0 1
0 0 2 2

NO

Problem S. Alice and numbers ≡

Statement

Young programmer Alice does not like integers number K.

Alice wants to know number of integers in range from 1 to N (inclusive) not divisible by K.

Input format

Input contains two integer numbers N and K.

Output format

Output a single integer — number of integers not divisible by K.

Constraints

2 ≤ N ≤ 10⁹

1 ≤ K ≤ 100

Sample tests

5 2

3

4 2

2

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

Условие

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

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

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

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

Ограничения

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

3
1 1 1
1 2 1
1 2 3

2