Студент Вася решил приобрести себе новый гаджет.
Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.
В магазине Васе объяснили правила предоставления кредита.
Первоначально сумма долга равна стоимости гаджета C.
По истечении максимум N лет вся сумма долга должна быть выплачена
Вася должен определить ежемесячный платеж M — целое число рублей,
которое он будет выплачивать каждый месяц.
Исключение может составлять последний платёж —
оставшаяся на последний месяц сумма долга может оказаться меньше M.
Каждый месяц после Васиного платежа оставшаяся сумма долга
увеличивается на P процентов и округляется вверх до целого числа.
Поскольку на деньги, оставшиеся от выплаты по кредиту, Васе нужно питаться целый месяц,
он хочет выбрать минимально возможную сумму ежемесячного платежа, позволяющую рассчитаться за кредит
в установленный срок. Требуется написать программу, определяющую эту сумму.
Рекомендуется рассмотреть частичные решения
P = 0
C, P ≤ 103
Формат входного файла
Входной файла содержит целые числа NPC.
Формат выходного файла
Выходной файл должен содержать единственное целое число — подходящий Васе ежемесячный платеж.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
forest.in
Ограничение памяти:
256 Мб
Выходной файл:
forest.out
Условие
Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес,
на месте которого должно быть кукурузное поле. В лесу растут 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 ≤ 1018;
X < K;
X < M.
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (10 баллов)
1 ≤ X ≤ 1018.
Дополнительно к приведенным ограничениям выполняется условие K = M.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 4 (48 баллов)
1 ≤ X ≤ 1018, 1 ≤ A, B ≤ 109, 2 ≤ K, M ≤ 1018.
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест
начисляются независимо.
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Формат входного файла
Входной файл содержит пять целых чисел, разделенных пробелами:
A, K, B, M и X.
Формат выходного файла
Выходной файл должен содержать одно целое число — искомое количество дней.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
diploma.in
Ограничение памяти:
64 Мб
Выходной файл:
diploma.out
Условие
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике.
Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы.
К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры:
W — в ширину и H — в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками.
Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной
стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы
прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет,
чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго
в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих
внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для
размещения всех своих дипломов.
Система оценивания
Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.
Формат входного файла
Входной файл содержит три целых числа: W, H, N
Формат выходного файла
В выходной файл необходимо вывести ответ на поставленную задачу.
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано E — вес пустой копилки, F — вес копилки с монетами,
N — количество достоинств монет,
Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа EFN.
В следующих N строках находятся по два числа — CiWi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число − 1.
Лягушка попала в пруд с кувшинками, который можно представить в виде сетки N на M (в узлах сетки находятся кувшинки).
Теперь она хочет попасть с нижнего левого угла пруда в верхний правый, прыгая только по кувшинкам.
Сама лягушка может прыгать только одним из следующих способов:
1. Прыгнуть на 2 клетки вверх
2. Прыгнуть на 2 клетки вправо
3. Прыгнуть на 1 клетку по-диагонали
Лягушка не может выходить за границы сетки
Требуется найти, сколькими способами лягушка может попасть из нижнего левого угла пруда в верхний правый. Ответ взять по модулю 1000000007.
Формат входных данных
Входные данные состоят из двух чисел, записанных через пробел: N и M
Формат выходных данных
Выходные данные должны содержать только одно число - количество способов добраться из нижнего левого угла в верхний правый, взятое по модулю 1000000007
