У Тимофея есть n марок номиналом по p рублей каждая. Ему требуется отправить как можно больше писем по тарифу t рублей за письмо. Естественно, для этого на каждое из писем ему придется наклеить столько марок, чтобы их суммарная стоимость была не меньше t, иначе на почте его отправление не примут. Какое наибольшее количество писем сможет отправить Тимофей?
Формат входных данных
Три строки входного файла содержат натуральные числа: n, p и t.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
1 ≤ n, p, t ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при t ≤ p, получат не менее 30 баллов.
Пояснение к примеру
В примере у Тимофея две марки номиналом по 3 рубля, а стоимость одного отправления составляет 4 рубля. Тимофею придется наклеить обе марки на один конверт.
Несколько лет назад археологи раскопали игровой кубик 600-летнего возраста, который, вероятно, использовался для жульничества. На гранях деревянного кубика из средневековой Норвегии находились две пятёрки, две четвёрки, тройка и шестерка — а единички и двойки не было. Считается, что этот кубик использовался для обмана при игре в кости, а не в какой-то особой игре, в которой нужны были определённые комбинации чисел.
Тимофей одновременно бросают два кубика, простой и нечестный. По описанию нечестного кубика определите, с какой вероятностью на нём выпадет число, большее, чем на обычном.
Напомним, что в качестве вероятности выступает отношение количества исходов, благоприятствующих данному событию, к общему числу равновозможных исходов.
Формат входных данных
Единственная строка входного файла содержит шесть натуральных чисел xi, записанных через пробел — числа на гранях нечестного кубика.
Формат выходных данных
Выведите два натуральных числа — числитель и знаменатель несократимой дроби, выражающей вероятность описываемого события.
В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня заведующий отделом для проверки одной из гипотез дал Тимофею следующее задание: определить, сколько есть способов выбрать из первых n натуральных чисел два различных числа так, чтобы их сумма оканчивалась на его любимую цифру d?
Формат входных данных
Две строки входного файла содержат два натуральных числа: n и d.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например longlong в C++, int64 в FreePascal, long в Java.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 109
0 ≤ d ≤ 9
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 1000, получат не менее 40 баллов.
Пояснение к примеру
В примере дано n = 10. Переберем все возможные пары чисел из диапазона от 1 до 10 и сложим их — в пяти случаях получим сумму, оканчивающуюся на 3.
Тимофей очень хочет победить на региональном этапе Всероссийской олимпиады школьников по экологии. На этом этапе предусмотрен тур защиты проектов, поэтому в рамках своего исследования мальчик каждый день наблюдает за берёзой, растущей напротив окна его квартиры. За лето на ней распустилось ровно n зелёных листочков. В течение осени зеленый лист сначала становился желтым, а потом опадал. Тимофею было интересно, сколько листьев останется на берёзе через k дней.
К сожалению, юный эколог выбрал не самый удачный способ подсчета листьев. В каждый из k дней он выбирал какой-нибудь из двух цветов (зеленый или желтый), подсчитывал, какая часть оставшихся на берёзе листьев имеет такой цвет, и записывал эту дробь на бумажку. Наступила зима, и Тимофей не может вспомнить точное количество оставшихся листьев на берёзе. Помогите ему!
Для определенности считайте, что каждый день с берёзы опадало наименьшее возможное количество листьев.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и k. В следующих k строках через пробел расположены символ g или y, обозначающий цвет листьев подсчитанной части — зелёный или желтый соответственно, а также два целых числа ai, bi — числитель и знаменатель несократимой дроби, выражающей эту часть. Гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведите одно неотрицательное целое число — максимально возможное количество оставшихся на берёзе листьев после k дней.
Ограничения
1 ≤ n ≤ 109
1 ≤ k ≤ 50
0 ≤ ai < b ≤ 1000
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при k = 1, получат не менее 20 баллов.
Пояснение к примеру
В примере дана берёза, на которой летом было 100 листьев и 5 дней наблюдения. В первый день на берёзе было 34 зеленых листьев. Тогда всего получается 75 зеленых и 25 желтых листьев.
Во второй день на берёзе было 12 желтых листьев. Ни одного листочка не опало, а 25 зелёных листочков пожелтело и тогда на дереве 50 зелёных и 50 желтых листьев.
В третий день на берёзе было 57 зеленых листьев. Без 30 опавших жёлтых листочков не обойтись. На дереве 50 зелёных и 20 желтых листьев.
В четвертый день на берёзе было 45 желтых листьев. 36 зелёных листьев пожелтели. На дереве 14 зелёных и 56 желтых листьев.
В последний пятый день на берёзе было 16 зелёных листьев. Три зелёных листочка пожелтели и опали. Один желтый листочек тоже опал. На дереве 11 зелёных и 55 желтых листьев. Всего на берёзе осталось 66 листов.
