Студент Вася решил приобрести себе новый гаджет.
Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.
В магазине Васе объяснили правила предоставления кредита.
Первоначально сумма долга равна стоимости гаджета C.
По истечении максимум N лет вся сумма долга должна быть выплачена
Вася должен определить ежемесячный платеж M — целое число рублей,
которое он будет выплачивать каждый месяц.
Исключение может составлять последний платёж —
оставшаяся на последний месяц сумма долга может оказаться меньше M.
Каждый месяц после Васиного платежа оставшаяся сумма долга
увеличивается на P процентов и округляется вверх до целого числа.
Поскольку на деньги, оставшиеся от выплаты по кредиту, Васе нужно питаться целый месяц,
он хочет выбрать минимально возможную сумму ежемесячного платежа, позволяющую рассчитаться за кредит
в установленный срок. Требуется написать программу, определяющую эту сумму.
Рекомендуется рассмотреть частичные решения
P = 0
C, P ≤ 103
Формат входного файла
Входной файла содержит целые числа NPC.
Формат выходного файла
Выходной файл должен содержать единственное целое число — подходящий Васе ежемесячный платеж.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
diploma.in
Ограничение памяти:
64 Мб
Выходной файл:
diploma.out
Максимальный балл:
101
Условие
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике.
Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы.
К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры:
W — в ширину и H — в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками.
Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной
стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы
прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет,
чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго
в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих
внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для
размещения всех своих дипломов.
Система оценивания
Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.
Формат входного файла
Входной файл содержит три целых числа: W, H, N
Формат выходного файла
В выходной файл необходимо вывести ответ на поставленную задачу.
На улице длиной в 100 метров установлено N фонарей
высотой y1, y2, …, yN метров
на расстоянии x1, x2, … xN метров от начала улицы.
Форма отражателей такова, что свет каждого фонаря
распространяется в пределах конуса с углом при вершине 90°.
Требуется определить яркость самого освещённого участка улицы, т.е.
максимальное количество фонарей, освещающих один и тот же участок.
Рекомендуется рассмотреть частичные решения:
N ≤ 2
Формат входного файла
Во входном файле содержится число N, за которым следует N пар
целых чисел x1y1x2y2… xNyN.
Формат выходного файла
Выходной файл должен содержать единственное число — максимальное количество фонарей.
Перед началом шоссейно-кольцевых автомобильных гонок проводится квалификация,
результаты которой определяют расположение автомобилей на старте гонки.
Во время квалификации каждый гонщик может проехать неограниченное число кругов,
и минимальное время, за которое гонщик смог проехать круг,
называется его лучшим временем.
Затем на старте гонки гонщики сортируются по возрастанию лучшего времени,
в случае его равенства впереди будет тот, кто показал это время раньше.
Когда гонщик завершает очередной круг, в журнал записываются числа Bi и Ti —
номер его машины и разность между временем,
за которое он проехал этот круг, и текущим лучшим
среди всех гонщиков временем.
(Ti измеряется в тысячных долях секунды, T1 всегда равно 0).
Если Ti < 0, то время, показанное этим гонщиком, становится лучшим.
Требуется определить результат квалификации по записям в журнале.
Формат входного файла
Входной файл содержит число N — общее количество кругов,
сделанных всеми гонщиками в квалификации.
Далее содержатся N пар целых чисел BiTi —
записи в журнале в хронологическом порядке.
Формат выходного файла
Выходной файл должен содержать номера гоночных автомобилей,
перечисленные в порядке расположения на старте гонки.
Ограничения
1 ≤ N ≤ 105
Разница между лучшим и худшим временем не превышает 109 тысячных секунды
Дан неориентированный граф. Проверьте, является ли он деревом.
Формат входного файла
В первой строке входного файла заданы через пробел два целых числа
n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих
строк содержит два целых числа ui и vi через пробел — номера концов
i-го ребра.
Граф не содержит петель и кратных рёбер.
Формат выходного файла
В первой строке выходного файла выведите YES, если граф является
деревом, и NO в противном случае.
You are to write a program that receives a weighted directed graph and finds
distances from source vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W.
Length of path is the sum of weights of its edges.
Vertices are numbered with integers from 1 to N.
Input file format
First line of input file contains three integers NM and S,
where M is the number of edges. Next M lines contain three
integers each —
starting vertex number, ending vertex number and weight of some edge respectively.
All weights are positive.
There is at most one edge connecting two vertices in every direction.
Output file format
Output file must contain N integers — distances from
source vertex to all vertices.
If some vertices are not reachable from S, corresponding numbers must be −1.
Constraints
1 ≤ N ≤ 1000.
All weights are less or equal than 1000.
