Темы
Информатика(2656 задач)
--->
228 задач
<---
#113649
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2016,
Лига B,
Задача G
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
С древних времён ужасный крылатый Сфинкс подстерегает путников у Большого Камня по дороге в священный город Истины, задаёт им хитроумные загадки и съедает тех, кто не сумел дать правильный ответ. Турист Пётр тоже решил посетить город Истины и встретил чудовище.
Сфинкс задал ему такую загадку: «На Большом Камне написано число n . Найди наименьшее целое положительное число k , такое что сумма цифр числа k в десятичной системе счисления делится на n и сумма цифр числа k + 1 в десятичной системе счисления делится на n ».
Пётр догадался, что коварный Сфинкс задаёт всем путникам одну и ту же задачу, изменяя лишь число n , и загорелся желанием избавить мир от смертоносных загадок чудовища. Он решил написать на Большом Камне алгоритм, который позволит всем путникам давать правильный ответ на загадку. Помогите ему в этом.
Входные данные
В единственной строке находится целое число n ( 1 ≤ n ≤ 100 000 ).
Выходные данные
В случае если искомого числа k не существует, выведите одно число 0 .
В противном случае выведите целое положительное число k , являющееся ответом на загадку Сфинкса. Ответ не должен содержать пробелов и ведущих нулей.
Примечание
В первом примере суммы цифр чисел k и k + 1 должны делиться на 1. Это условие выполнено для любого целого положительного k , поэтому ответом является 1.
Во втором примере суммы цифр чисел k и k + 1 должны делиться на 4. Числа 39 и 40 удовлетворяют этому требованию, поскольку 3 + 9 = 12 и 4 + 0 = 4 . Нетрудно убедиться, что никакое меньшее число k не является ответом на эту загадку Сфинкса.
Примеры
Входные данные
1
Выходные данные
1
Входные данные
4
Выходные данные
39
#113650
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2016,
Лига B,
Задача H
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Где-то в Москве в очередной раз построили новый дом: красивый, современный и многоэтажный. Он состоит из ровно \(n\) жилых этажей, пронумерованных от \(1\) до \(n\) снизу вверх, и подземной парковки, являющейся нулевым этажом.
Дом уже был почти готов к сдаче в эксплуатацию, но вот незадача — в самый ответственный момент по всему зданию прорвало водопроводные трубы, в результате чего многие этажи залило водой. К моменту, когда все трубы были заделаны, на \(i\)-м этаже находилось \(w_i\) литров воды.
Также из-за того, что при строительстве дома все средства ушли на отделку фасада, а на перекрытия между этажами был пущен самый дешёвый материал, оказалось, что между этажами ощутимо протекают потолки. В частности, пропускная способность пола \(i\)-го этажа составляет \(v_i\) литров воды в час.
В рамках данной задачи считается, что скорость вытекания воды с этажа зависит только от пропускной способности пола и не зависит от количества воды на этаже. Временем падения воды с потолка этажа до пола также следует пренебречь. Считайте, что все этажи достаточно объёмные, чтобы вместить всю воду, скопившуюся в здании.
Владельцы стройки интересуются, через сколько часов вся вода вытечет на парковку, и они смогут начать продажи квартир?
Входные данные
В первой строке записано единственное целое число \(n \ (1 \le n \le 200 000\)) — количество жилых этажей здания.
Вторая строка содержит n целых чисел \(w_1, \ w_2, \dots, \ w_n \ (0 \le w_i \le 1000)\), задающих количество воды в литрах на каждом из жилых этажей здания.
Третья строка содержит \(n\) целых чисел \(v_1, \ v_2, \dots, \ v_n \ (1 \le v_i \le 200 000\)), задающих скорость протекания пола каждого из жилых этажей здания в литрах в час.
Выходные данные
Выведите единственное число — время в часах, через которое вся вода стечёт на подземную парковку.
Ваш ответ будет засчитан, если его абсолютная или относительная погрешность не превосходит \(10^{−4}\) , а именно: если ваш ответ — \(p_{ans}\), а ответ жюри — \(j_{ans}\), то ваш ответ будет засчитан, если \(\frac{|p_{ans} \ − \ j_{ans}|}{max\{1, \ |j_{ans}|\}} \le 10^{−4}\) .
Пояснения к примерам
В первом примере на первом этаже изначально 10 литров воды, а на втором — 20 литров, все полы текут со скоростью 5 литров в час. Через 2 часа после начала 10 единиц воды перетечёт с первого этажа на парковку, а также со второго этажа на первый, значит, на первом этаже количество воды не изменится, а на втором этаже станет на 10 литров меньше. По прошествии ещё двух часов на первом этаже по-прежнему будет 10 литров воды, а второй этаж опустеет. А ещё через 2 часа вся вода с первого этажа стечёт на подземную парковку.
Примеры
Входные данные
2 10 20 5 5
Выходные данные
6.0000000000
Входные данные
3 0 0 100 45 40 50
Выходные данные
2.5000000000
#113651
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2016,
Лига B,
Задача I
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Около полугода назад было доказано, что проверка возможности прохождения уровня в классической игре Super Mario Bros. лежит в классе сложности PSPACE и, более того, является PSPACE -полной задачей. Мы не предлагаем вам понять, что это значит, но предлагаем почувствовать, насколько сложно бывает программно играть в компьютерные игры. Для этого мы опишем упрощённый вариант игры и предложим проверить, возможно ли пройти уровень в нашем варианте «Марио» или нет (для понимания задачи необязательно быть знакомым с оригинальной игрой).
Наш вариант игры происходит на клетчатом поле, состоящем из n строк на m столбцов. Каждая клетка поля может принадлежать одному из следующих видов:
- пустая клетка, обозначается символом подчёркивания ' _ ';
- клетка с землёй, обозначается решёткой ' # ';
- клетка, содержащая монетку, обозначается строчной английской буквой ' c ';
- клетка, в которой находится Марио, обозначается строчной английской буквой ' m ';
- клетка, в которой находится Принцесса, обозначается строчной английской буквой ' p '.
Пронумеруем строки сверху вниз числами от 1 до n и столбцы слева направо целыми числами от 1 до m . Где-то в m -м столбце находится Принцесса (в клетке, обозначенной буквой ' p '). А в одной из клеток первого столбца стоит Марио (в клетке, обозначенной ' m '). Конечно, и Принцесса, и Марио стоят на земле, то есть в клетках, под каждым из них находится земля.
Также в некоторых столбцах от второго до ( m - 1) -го, возможно, находятся монетки. В одном столбце находится не более одной монетки, а также любая монетка лежит на земле, то есть в клетке под монеткой обязательно находится земля.
Марио, как и в классическом варианте игры, нужно добраться до Принцессы, но еще ему необходимо собрать все монетки, которые есть на поле. Марио может перемещаться только посредством прыжков.
Прыжок Марио состоит из двух частей: сначала он летит вертикально вверх, а потом горизонтально вправо. Вертикальная часть прыжка может иметь длину y от 0 до a клеток, а горизонтальная может иметь длину x от 0 до b клеток. В частности, Марио может прыгнуть вертикально вверх, не перемещаясь по горизонтали, а также прыгнуть горизонтально вправо, не смещаясь при этом по вертикали. Естественно, Марио не может пролетать сквозь клетки, содержащие землю. Обратите внимание, в отличие от оригинальной игры Марио не может перемещаться влево.
Если после окончания прыжка Марио оказывается в клетке, под которой нет земли, он падает вниз, пока под ним не окажется земля. В случае, если Марио долетает до n -й (самой нижней) строки, он проваливается вниз за экран и погибает, а игра заканчивается. Также Марио не может выпрыгивать за границы поля сверху или справа.
Если Марио оказывается в клетке с монеткой (возможно, в процессе прыжка), то он её подбирает.
Определите, возможно ли добраться до клетки с Принцессой, подобрав все монетки.
Входные данные
В первой строке содержится 4 целых числа n , m , a , b ( 2 ≤ n , m ≤ 100 , 1 ≤ a , b ≤ 10 ) — размеры поля и ограничения на длину прыжка Марио.
Далее следуют n строк по m символов, описывающих уровень. Каждый символ является одним из следующих: ' _ ', ' # ', ' c , ' m ', ' p ' (см. описание клеток в основной части условия).
Гарантируется, что на поле находятся единственная клетка с Марио и единственная клетка с Принцессой.
Гарантируется, что в каждом столбце от второго до ( m - 1) -го включительно находится не более одной монетки, а в первом и последнем столбце монеток нет.
Гарантируется, что Марио, Принцесса и монетки находятся в клетках, непосредственно под которыми есть клетки с землёй, в частности, Марио, Принцесса и монетки не находятся в n -й строке.
Выходные данные
Выведите слово « YES » (без кавычек), если Марио может собрать все монетки с поля и оказаться в клетке с Принцессой, в противном случае выведите слово « NO » (без кавычек).
Примечание
В первом примере Марио должен сделать два прыжка. Первым прыжком на 1 клетку вправо Марио подберёт монетку, а вторым на одну клетку вверх и две клетки вправо доберётся до принцессы.
Во втором примере Марио не может добраться до принцессы. Обратите внимание, Марио не может находиться в последней строке, так как он проваливается вниз за экран и погибает.
В четвёртом примере Марио не может сразу прыгнуть к Принцессе, потому что он должен подобрать монетку, но если он прыгнет вправо и вниз к монетке, то он не сможет потом вернуться обратно к Принцессе (обратите внимание, Марио не может вернуться обратно в стартовую точку, потому что он не умеет прыгать влево), поэтому ответ на этот тест — « NO ».
Примеры
Входные данные
3 4 1 2 ___p mc_# ##_#
Выходные данные
YES
Входные данные
4 5 10 3 __#_p mc__# ##___ _____
Выходные данные
NO
Входные данные
5 3 3 2 ___ _#_ _#p m_# ##_
Выходные данные
YES
Входные данные
4 4 1 3 m__p #__# _#c_ __#_
Выходные данные
NO
Выбрано
:
|