Олимпиада 1С 2024, предметный тур
A. Present Cubinuous
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Василисы сегодня день рождения! Она позвала всех своих друзей в гости пить чай. Борис, как и полагается, хочет принести Василисе подарок, поэтому он купил $$$A$$$ замечательных квадратов со стороной $$$2$$$, а также $$$B$$$ прекрасных квадратов со стороной $$$1$$$. Осталось только найти подходящую упаковку в Бесконечном магазине.

Борис обнаружил, что в магазине есть много подарочных коробок. Вот только из соображений стандартизации ширина каждой коробки равна $$$K$$$. Но хоть в чём-то название магазина остаётся не просто маркетинговым ходом: таких коробок тут бесконечно много, и можно найти коробку любой целочисленной длины.

Борис очень просит вас помочь ему выбрать коробку ширины $$$K$$$ и минимальной длины, в которую он может положить все свои подарки так, чтобы стороны подарков были параллельны сторонам коробки.

Входные данные

Первая строка входных данных содержит целое число $$$A$$$ ($$$0 \le A \le 10^8$$$) — количество квадратов со стороной $$$2$$$.

Вторая строка содержит целое число $$$B$$$ ($$$0 \le B \le 10^8$$$) — количество квадратов со стороной $$$1$$$.

Третья строка содержит целое число $$$K$$$ ($$$2 \le K \le 10^8$$$) — ширину каждой коробки в магазине.

Гарантируется, что $$$A + B \gt 0$$$, то есть Василисе подарили хотя бы один квадрат.

Выходные данные

Выведите одно число $$$X$$$ — минимальную длину коробки такую, что в коробку $$$K \times X$$$ вместятся все подаренные квадраты, уложенные параллельно сторонам коробки.

Система оценки

Решения, правильно работающие, когда числа $$$A$$$, $$$B$$$, $$$K$$$ не превосходят $$$100$$$, будут оцениваться в 35 баллов.

Примеры
Входные данные
3
3
3
Выходные данные
6
Входные данные
4
1
5
Выходные данные
4
Входные данные
2
4
4
Выходные данные
3
Примечание

Возможные способы уложить квадраты для примеров из условия:

Пример 1Пример 2Пример 3

Во втором примере Василисе подарили $$$4$$$ квадрата со стороной $$$2$$$ (изображены на рисунке красным) и $$$1$$$ квадрат со стороной $$$1$$$ (изображен на рисунке жёлтым). Также известно, что ширина коробки (вертикальная сторона) равна $$$5$$$. Тогда минимальная длина (горизонтальная сторона) коробки, которая вмещает все квадраты, равна $$$4$$$. Пример расположения квадратов в такой коробке изображён на рисунке. Можно показать, что в коробку со стороной меньше $$$4$$$ все квадраты поместить нельзя.

B. Акция на день рождения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На день рождения Василиса решила угостить выпечкой $$$N$$$ своих гостей. Она получила в местной пекарне промокод на $$$K$$$ рублей, но для его использования нужно выбрать выпечки ровно на $$$K$$$ рублей, иначе акция недействительна. В пекарне продаётся два вида товаров: кексы по $$$A$$$ рублей за штуку и печенье по $$$B$$$ рублей за штуку (при этом $$$A \ne B$$$). Василиса хочет купить ровно $$$N$$$ штук выпечки.

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

Входные данные

Первая строка входных данных содержит целое число $$$K$$$ ($$$1 \le K \le 10^{9}$$$) — номинал промокода в пекарне.

Вторая строка содержит целое число $$$N$$$ ($$$1 \le N \le 10^{9}$$$) — количество гостей Василисы.

Третья строка содержит целое число $$$A$$$ ($$$1 \le A \le 10^{9}$$$) — стоимость одного кекса.

Четвёртая строка содержит целое число $$$B$$$ ($$$1 \le B \le 10^{9}$$$) — стоимость одного печенья.

Гарантируется, что $$$A \ne B$$$.

Выходные данные

Если существует набор выпечки, удовлетворяющий условию, то выведите два числа — количество кексов и количество печенья, которое должна купить Василиса, соответственно. Если же такого набора выпечки не существует, то выведите «$$$-1$$$» (без кавычек).

Система оценки

Решения, правильно работающие, когда значения $$$K$$$, $$$N$$$, $$$A$$$, $$$B$$$ не превосходят $$$10^{3}$$$, будут оцениваться в $$$30$$$ баллов.

Решения, правильно работающие, когда значения $$$K$$$, $$$N$$$, $$$A$$$, $$$B$$$ не превосходят $$$10^{6}$$$, будут оцениваться в $$$60$$$ баллов.

Примеры
Входные данные
11
3
5
1
Выходные данные
2 1
Входные данные
15
3
5
3
Выходные данные
3 0
Входные данные
16
3
5
4
Выходные данные
-1
Примечание

В первом примере Василисе нужно купить 3 единицы выпечки стоимостью 11 рублей. Она может купить 2 кекса по 5 рублей и 1 печенье по 1 рублю. $$$2 + 1 = 3$$$ и $$$2 \cdot 5 + 1 \cdot 1 = 11$$$

C. Змейка и яблоки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Родители подарили Василисе на день рождения «Икес Бокес Сирес Икес», на котором она решила поиграть в змейку. Игровое поле представляет собой прямоугольник из $$$n$$$ строк и $$$m$$$ столбцов.

Змейка длины $$$k$$$ состоит из $$$k$$$ сегментов, пронумерованных от $$$1$$$ до $$$k$$$ от головы к хвосту. Каждый сегмент занимает одну клетку поля. Изначально змейка имеет длину $$$1$$$ и занимает только верхнюю левую клетку поля (клетка в строке $$$1$$$ и столбце $$$1$$$).

Также в течение игры на поле появится $$$q$$$ яблок, причём изначально на поле есть только первое яблоко. $$$i$$$-е яблоко появляется на поле, когда змейка съедает яблоко $$$i-1$$$. Таким образом, до конца игры на поле в каждый момент находится ровно одно яблоко.

Пусть голова змейки находится в клетке в строке $$$i$$$ и столбце $$$j$$$. Тогда следующая клетка на пути змейки определяется так:

  • Если голова находится не в самой правой клетке текущей строки ($$$j \lt m$$$), то следующей клеткой будет клетка в той же строке и в столбце $$$j + 1$$$.

  • Если голова находится в строке $$$i$$$ и столбце $$$m$$$ (то есть в самой правой клетке строки), то следующей клеткой на пути будет клетка в строке $$$i + 1$$$ и столбце $$$1$$$.

  • Если же голова змейки находилась в строке $$$n$$$ и столбце $$$m$$$, то следующей будет клетка в строке $$$1$$$ и столбце $$$1$$$.

В течение игры каждую секунду происходит следующее.

  • Рассмотрим следующую клетку на пути змейки. Если в ней нет яблока, то голова змейки перемещается на эту клетку, а остальные сегменты перемещаются за ней, то есть сегмент номер $$$i$$$ ($$$1 \lt i \le k$$$) перемещается в клетку, в которой находился сегмент $$$i-1$$$.
  • Если в следующей клетке на пути находится яблоко, то змейка съедает его и увеличивает свою длину на $$$1$$$. В результате клетка, в которой находилось яблоко, становится новым сегментом змейки и там оказывается её голова, а остальные сегменты остаются на месте, и их номера увеличиваются на $$$1$$$.

Каждый раз, когда змейка съедает яблоко, на поле появляется следующее яблоко (если съеденное яблоко не было последним). Если яблоко появилось в клетке, которая в данный момент занята змейкой, то змейка съедает его в ту же секунду, не перемещаясь, и на поле появляется следующее яблоко. Если и последующие яблоки будут появляться в клетках, уже занятых змейкой, то все они будут съедены моментально. Для большей ясности изучите пояснения к примеру в разделе «Замечание».

Определите, за какое количество секунд змейка съест все $$$q$$$ яблок.

Можно показать, что не может возникнуть ситуация, в которой длина змейки станет больше $$$n \cdot m$$$.

Входные данные

В первой строке находятся три числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \le n, m, q \le 10^5$$$) — количество строк и количество столбцов игрового поля и количество яблок.

В $$$i$$$-й из следующих $$$q$$$ строк находятся два числа $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — номера строки и столбца клетки, в которой появляется $$$i$$$-е яблоко. Обратите внимание, что яблоко может появиться в той клетке, в которой яблоко уже было ранее.

Выходные данные

Программа должна вывести одно число — количество секунд, через которое змейка съест все яблоки.

Обратите внимание, что ответ может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

Система оценки

Решения, правильно работающие при $$$q = 1$$$, будут оцениваться в $$$20$$$ баллов.

Решения, правильно работающие при $$$n, m, q \le 200$$$, будут оцениваться в $$$50$$$ баллов.

Примеры
Входные данные
2 3 4
1 3
2 2
2 1
1 1
Выходные данные
6
Входные данные
2 2 4
1 1
1 2
1 2
1 1
Выходные данные
1
Входные данные
2 4 4
1 3
1 4
1 1
2 4
Выходные данные
8
Примечание

В первом примере в поле $$$2$$$ строки, $$$3$$$ столбца, и в игре будет $$$4$$$ яблока. Игра закончится через $$$6$$$ секунд:

До начала игрыПосле первой секундыПосле второй секунды

Во вторую секунду змейка съела первое яблоко и стала на $$$1$$$ длиннее. Также на поле появилось второе яблоко.

После третьей секундыПосле четвёртой секунды

В четвёртую секунду змейка съедает второе яблоко и увеличивает свою длину на $$$1$$$. Также третье яблоко появляется в клетке, в которой уже находится змейка, поэтому оно оказывается съедено моментально, а змейка не увеличивается. На поле появляется четвёртое яблоко.

После пятой секундыПосле шестой секунды

После пятой секунды голова змейки находится в клетке $$$(2;3)$$$, поэтому следующей клеткой на её пути будет клетка $$$(1;1)$$$. Голова змейки перемещается в неё и змейка съедает последнее (четвёртое) яблоко.

Во втором примере в момент начала игры змейка съест яблоко в клетке $$$(1;1)$$$ (это произойдёт моментально). Далее, в первую секунду змейка съест яблоко в клетке $$$(1;2)$$$, и её голова переместится в эту клетку. В эту же секунду второе яблоко появится в клетке, в которой сейчас находится голова, и окажется съедено. Третье яблоко также будет съедено моментально, так как в клетке $$$(1;1)$$$ находится второй сегмент змейки.

D. Многочисленные монеты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В денежной системе Древнего Египта было $$$n$$$ различных типов монет. Курс обмена монет полностью стабилен. Монеты пронумерованы по ценности от $$$1$$$ до $$$n$$$: монета $$$1$$$ является наименее ценной, а монета $$$n$$$ — наиболее ценной. А именно: $$$a_i$$$ монет типа $$$i$$$ равноценны одной монете типа $$$i+1$$$, для всех $$$1 \le i \le n-1$$$ (известно, что $$$a_i \geq 2$$$). Также можно производить несколько обменов, то есть $$$1$$$ монета типа $$$3$$$ по стоимости равна $$$a_1 \cdot a_2$$$ монетам типа $$$1$$$. Можно как менять более ценные монеты на менее ценные, так и наоборот.

Сегодня у Василисы день рождения. В подарок она получила набор древнеегипетских монет. В наборе содержится $$$b_1$$$ монет типа $$$1$$$, $$$b_2$$$ монет типа $$$2$$$, ..., $$$b_n$$$ монет типа $$$n$$$.

Чтобы помочь Василисе оценить её богатство, она просит вас обработать $$$q$$$ запросов. Запросы бывают двух типов:

  1. 1 x y — Василиса добавляет в свой набор $$$x$$$ монет типа $$$y$$$. Формально: $$$b_y := b_y + x$$$.

  2. 2 x y — определить, достаточно ли у Василисы монет, чтобы обменять их на $$$x$$$ монет типа $$$y$$$. Стоимости монет относительно друг друга определяются курсами обмена, описанными выше.
Входные данные

В первой строке входных данных содержится единственное целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество различных монет в денежной системе Древнего Египта.

Во второй строке входных данных содержатся $$$n - 1$$$ целых чисел: $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$2 \le a_i \le 10^9$$$) — $$$a_i$$$ обозначает количество монет типа $$$i$$$, которое равно по стоимости одной монете типа $$$i + 1$$$.

В третьей строке входных данных содержатся $$$n$$$ целых чисел: $$$b_1, b_2, \ldots, b_{n}$$$ ($$$0 \le b_i \le 10^9$$$) — первоначальное количество монет каждого типа в наборе Василисы.

В четвёртой строке входных данных содержится единственное целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

В следующих $$$q$$$ строках содержатся запросы, по одному в строке. Каждый запрос состоит из трёх чисел $$$t, x, y$$$ ($$$1 \le t \le 2, 1 \le x \le 10^9, 1 \le y \le n$$$). Если $$$t = 1$$$, Василиса добавляет в свой набор $$$x$$$ монет типа $$$y$$$. Если $$$t = 2$$$, вам нужно сравнить стоимость всего текущего набора Василисы со стоимостью $$$x$$$ монет типа $$$y$$$.

Выходные данные

Для каждого запроса типа $$$2$$$ в отдельной строке выведите $$$1$$$, если стоимость набора Василисы не меньше стоимости $$$x$$$ монет типа $$$y$$$. Если это неверно, то выведите число $$$0$$$.

Система оценки

Помимо тестов из условия, в этой задаче $$$50$$$ тестов, каждый из которых оценивается в $$$2$$$ балла.

Гарантируется, что:

  • В тестах стоимостью $$$10$$$ баллов выполняется: $$$n = 2$$$

  • В тестах стоимостью $$$10$$$ баллов выполняется: $$$y = 1$$$ во всех запросах типа $$$2$$$

  • В тестах стоимостью $$$10$$$ баллов выполняется: нет запросов типа $$$1$$$, суммарная стоимость набора Василисы не превышает стоимости $$$10^{9}$$$ монет типа $$$1$$$.

  • В тестах стоимостью $$$10$$$ баллов выполняется: $$$a_i = 2$$$ для всех $$$1 \leq i \leq n$$$.

  • В тестах стоимостью $$$30$$$ баллов выполняется: $$$n \cdot q \leq 2 \cdot 10^5$$$.

  • В тестах стоимостью $$$30$$$ баллов дополнительных ограничений нет.
Пример
Входные данные
5
2 4 5 3
120 60 15 3 1
14
2 600 1
2 601 1
2 75 3
2 76 3
1 3 2
1 1 1
2 76 3
1 1 1
2 76 3
1 1000000000 1
2 10000000 4
2 10000000 5
1 999999777 1
2 1000000000 2
Выходные данные
1
0
1
0
0
1
1
0
1
Примечание

В примере из условия есть $$$5$$$ типов монет. Одна монета типа $$$2$$$ стоит как $$$2$$$ монеты типа $$$1$$$, одна монета типа $$$3$$$ стоит как $$$8$$$ монет типа $$$1$$$, одна монета типа $$$4$$$ стоит как $$$40$$$ монет типа $$$1$$$, и одна монета типа $$$5$$$ равноценна $$$120$$$ монетам типа $$$1$$$.

Первоначально у Василисы есть $$$120$$$ монет типа $$$1$$$, $$$60$$$ монет типа $$$2$$$, $$$15$$$ монет типа $$$3$$$, $$$3$$$ монеты типа $$$4$$$ и $$$1$$$ монета типа $$$5$$$. В пересчёте на монеты типа $$$1$$$ монеты Василисы имеют ценность эквивалентную $$$600$$$ монетам типа $$$1$$$. В пересчёте на монеты типа $$$3$$$ — ценность монет Василисы эквивалентна $$$75$$$ монетам типа $$$3$$$. Это даёт ответы на первые четыре запроса.

В пятом запросе добавляется $$$3$$$ монеты типа $$$2$$$. В шестом запросе добавляется $$$1$$$ монета типа $$$1$$$. После этого суммарная ценность монет эквивалентна $$$600 + 2 \cdot 3 + 1 = 607$$$ монетам типа $$$1$$$. При этом $$$76$$$ монет типа $$$3$$$ равноценны $$$608$$$ монетам типа $$$1$$$, поэтому ответом на седьмой запрос будет $$$0$$$.

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