Муниципальный этап ВсОШ по информатике, 7-8 классы, Московская область, 2022
Statement is not available in English language
A. Игрушечный небоскрёб
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Пете на день рождения подарили конструктор — игрушечный небоскрёб. Всего в конструкторе $$$N$$$ столбиков, $$$M$$$ стеклышек и $$$K$$$ пластин. Согласно инструкции, сначала нужно в качестве основания поставить пластину, а каждый следующий этаж получить из $$$x$$$ столбиков и $$$y$$$ стеклышек, накрытых следующей пластиной.

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

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

Тест №1: N = 15, M = 3, K = 8, x = 7, y = 1

Тест №2: N = 38, M = 24, K = 71, x = 2, y = 15

Тест №3: N = 81, M = 98, K = 125, x = 40, y = 16

Тест №4: N = 288, M = 95, K = 13, x = 10, y = 3

Тест №5: N = 579, M = 824, K = 35, x = 19, y = 46

Тест №6: N = 2048, M = 3491, K = 350, x = 412, y = 78

Тест №7: N = 5792, M = 510, K = 41, x = 31, y = 12

Тест №8: N = 9428, M = 4236, K = 8978, x = 6580, y = 115

Тест №9: N = 997, M = 8361, K = 1241, x = 3084, y = 6027

Тест №10: N = 861, M = 1405, K = 1118, x = 13, y = 44

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

Для каждого теста введите в тестирующую систему одно целое число, являющееся ответом на задачу – максимальное количество этажей в Игрушечном небоскребе.

Примеры
Входные данные
13 6 50 2 1
Выходные данные
6
Входные данные
3 7 10 1 2
Выходные данные
3
Входные данные
15 29 4 3 2
Выходные данные
3

Statement is not available in English language
B. Монетки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Мальчик Толя очень любит ходить в поход. Так как ближайший поход планируется на довольно продолжительный срок, то свой довольно тяжелый рюкзак Толя уже собрал. Однако ему сообщили в последний момент, что в походе им предстоит переплыть широкую реку, и билет на пароход будет стоить $$$m$$$ рублей. Так как Толя давно планировал этот поход, то решил открыть свою копилку и собрать из накопленных монет деньги на билет. Рассмотрев свои запасы, он обнаружил, что каждая монета имеет один из трёх номиналов: 1, 2 или 5 рублей; также Толя заметил, что каждая монетка номиналом в 1 рубль весит $$$a$$$ грамм, номиналом в 2 рубля — $$$b$$$ грамм, номиналом в 5 рублей — $$$c$$$ грамм. Так как Толя уже укомплектовал свой рюкзак, то он хочет взять такой набор монет, чтобы общая стоимость была ровно $$$m$$$ рублей, а вес набора был минимально возможным.

Помогите Толе.

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

В единой строке вводятся четыре натуральных числа: $$$m$$$, $$$a$$$, $$$b$$$, $$$c$$$ — стоимость билета и веса монеток номинала 1, 2 и 5 соответственно.

Тест №1: m = 17, a = 85, b = 80, c = 84

Тест №2: m = 96, a = 12, b = 21, c = 78

Тест №3: m = 245, a = 82, b = 52, c = 45

Тест №4: m = 13694, a = 43138, b = 12826, c = 38074

Тест №5: m = 309547, a = 74184, b = 10872, c = 78565

Тест №6: m = 479197, a = 4371, b = 11917, c = 56051

Тест №7: m = 529821, a = 24605, b = 78749, c = 7418

Тест №8: m = 586345, a = 89735, b = 95663, c = 31442

Тест №9: m = 806214, a = 75886, b = 17763, c = 17157

Тест №10: m = 969988, a = 50433, b = 76424, c = 21138

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

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

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

В примере из условия самая лёгкая монета оказалась с номиналом 5, поэтому самый минимальный набор по весу получится, если Толя возьмёт две монетки номинала 5 и одну монетку номинала 2. Суммарный вес набора будет 8 грамм.

Statement is not available in English language
C. Пирамида
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Аня вернулась домой, и у неё возникла идея: повторить достижение древних египтян и сделать свою пирамиду. На день рождения Ане подарили набор из $$$n$$$ игрушечных шариков — из них она и будет собирать свою пирамиду. Для построения слоя с номером $$$i$$$ необходимо использовать $$$i\cdot{(i+1)}/2$$$ шариков. Помогите Ане выяснить по заданному $$$n$$$, насколько высокая пирамидка у неё получится.

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

Тест №1: $$$n$$$ = 35

Тест №2: $$$n$$$ = 74

Тест №3: $$$n$$$ = 129

Тест №4: $$$n$$$ = 1456936

Тест №5: $$$n$$$ = 230411405

Тест №6: $$$n$$$ = 20540284444505

Тест №7: $$$n$$$ = 700000460725789860

Тест №8: $$$n$$$ = 131064599158912097

Тест №9: $$$n$$$ = 518476202531756699

Тест №10: $$$n$$$ = 943875484380147541

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

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

Пример
Входные данные
11
Выходные данные
3
Примечание

В примере из условия можно сделать пирамидку высотой 3. На нижнем слое будет 6 шариков, на следующем — 3 шарика, а на последнем будет располагаться 1 шарик: суммарное количество шариков — 6 + 3 + 1 = 10.

Statement is not available in English language
D. Прыгающий кубик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Васин друг-программист написал новую игру для телефона, которую дал Васе протестировать. Она называется «Прыгающий кубик». Игрок управляет кубиком, каждый уровень представляет собой линию из $$$n$$$ клеток, но в некоторых местах этой линии есть провалы. Игрок может прыгнуть на любое расстояние вправо от $$$1$$$ до $$$k$$$. Если игрок прыгнет на клетку, где нет провала, то продолжит игру, а если туда, где есть провал, то проиграет и начнет сначала, но теперь на том месте, где он проиграл, провала не будет. Изначально игрок находится на клетке с номером $$$1$$$, и нужно добраться до клетки $$$n$$$.

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

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

На первой строке записаны три числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, k \le 10^5, 0 \le m \le n$$$) – длина уровня, количество провалов на уровне и длина максимального прыжка соответственно.

На следующей строке записано $$$m$$$ чисел – номера, под которыми находятся провалы. Все номера различны и являются числами от $$$1$$$ до $$$n$$$.

Гарантируется, что на клетках под номером $$$1$$$ и под номером $$$n$$$ нет провалов.

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

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

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