Задача A. Hello, world! ≡

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)

Задача B0. FizzBuzz ≡

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

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

23

25

Buzz

30

FizzBuzz

Задача B1. Программист и квартплата ≡

Условие

Молодой программист Иннокентий решил переехать на новую квартиру и начать жить самостоятельно. Внимательно изучив коммунальные платежи, Иннокентий выяснил, что 1 киловатт электричества стоит K бурлей. Бюджет на электричество у Кеши равен M бурлям. Помогите ему понять, на какое количество полных дней бюджета Кеши хватит для оплаты электричества, если известно, что:

с 16:00 до 18:00 всегда горит свет, поглощающий Р киловатт в час;

с 9:00 до 18:00 всегда работает ноутбук, поглощающий Z киловатт в час;

круглые сутки работает роутер, поглощающий F киловатт в час.

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

Входные данные содержат целые числа M — бюджет, K — стоимость 1 киловатта, Р — количество киловатт, поглощающихся светом, Z — ноутбуком, F — роутером.

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

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

Ограничения

1 ≤ M, K, P, Z, F ≤ 10⁵

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

20000 20 10 6 1

10

15000 100 3 40 500

0

Задача B2. Энтое слово ≡

Условие

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

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

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

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

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

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

FEFU was established in 1899 as the Eastern Institute
5

1899

FEFU was established
5

established

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

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (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

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

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется 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

Задача C3. Гирлянда ≡

Условие

Ваша программа должна вывести в выходной файл изображение гирлянды. Гирлянда состоит из N звеньев, каждое из которых имеет вид ромба, состоящего из символов '#' (ASCII 35) для нечётных звеньев, либо '*' (ASCII 42) — для чётных звеньев. Размер i-го звена задаётся целым числом A_i. Каждая сторона ромба размером A_i состоит из A_i + 1 символа.

Гирлянда должна быть изображена на фоне прямоугольника, заполненного символами '.' (ASCII 46).

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

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

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

Ограничения

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

1 1

.#.
#.#
.#.

2 3 2

...#...
..#.#..
.#...#.
#.....#
.#...#.
..#*#..
..*#*..
.*...*.
..*.*..
...*...

3 1 1 2

..#..
.#*#.
.*#*.
.#*#.
#...#
.#.#.
..#..

Задача C4. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

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

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

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

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

6 14 12

Задача D0. Гаджет в кредит ≡

Условие

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

В магазине Васе объяснили правила предоставления кредита.

• Первоначально сумма долга равна стоимости гаджета C.
• По истечении максимум N лет вся сумма долга должна быть выплачена
• Вася должен определить ежемесячный платеж M — целое число рублей, которое он будет выплачивать каждый месяц. Исключение может составлять последний платёж — оставшаяся на последний месяц сумма долга может оказаться меньше M.
• Каждый месяц после Васиного платежа оставшаяся сумма долга увеличивается на P процентов и округляется вверх до целого числа.

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

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

1. P = 0
2. C, P ≤ 10³

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

Входной файла содержит целые числа N P C.

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

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

Ограничения

1 ≤ C ≤ 10⁹; 0 ≤ P ≤ 10⁹; 1 ≤ N ≤ 10⁴

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

1 0 1

1

1 124 12

8

1 1 12

2

Задача D1. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Задача D2. Вырубка леса ≡

Условие

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

• 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
• 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
• 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
• 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
• 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
• 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
• 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

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

Система оценивания и описание подзадач

Подзадача 1 (32 баллов)

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (10 баллов)

1 ≤ X ≤ 10¹⁸; X < K; X < M.

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

Подзадача 3 (10 баллов)

1 ≤ X ≤ 10¹⁸.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 10¹⁸, 1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

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

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

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

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

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

Ограничения

1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸, 1 ≤ X ≤ 10¹⁸

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

2 4 3 3 25

7

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

Условие

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

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

1. N ≤ 2

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

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

Ограничения

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

3
1 1 50 10 51 10

2

Задача E2. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

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

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

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

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача E3. Ближайшее число ≡

Условие

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

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

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

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача E4. Очередь к врачу ≡

Условие

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

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

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

Вторая строка содержит N чисел, отсортированных по возрастанию: t_i  — время, когда i − ый посетитель пришел на прием к терапевту.

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

0 ≤ t_i ≤ 10⁹

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

5 5
0 5 5 6 20

2

5 2
1 4 6 8 20

0

6 5
0 5 10 15 19 25

1

Задача F0. Черепаха в лабиринте ≡

Условие

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

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

Вам нужно написать программу для черепахи Тортилы.

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

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

В следующих далее N строчек по M символов содержится описание лабиринта:

• Точка '.'(ASCII 46) обозначает пустую клетку
• Решётка '#'(ASCII 35) обозначает стену, в такие клетки заползти нельзя

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

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

Ограничения

1 ≤ N, M ≤ 500

Гарантируется, что левый нижний и правый верхний углы лабиринта — пустые клетки

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

3 3
...
.#.
...

2

5 3
...
...
#..
.#.
...

6

2 10
........#.
..#.......

0