Изба-пятистенка или пятистенок — жилая деревянная прямоугольная постройка, разделенная внутренней поперечной стеной на две неравные части: избу (горницу) и сени. Пятая стена связывает между собой две длинные стены и делает конструкцию более прочной - не даст разъехаться связанным стенам.
Тимофей участвует в олимпиаде по технологии и хочет сделать модель такого дома. Он выбрал размеры для короткой (a) и длинной (b) стен избы, нарисовал план-чертеж и приготовил инструменты для работы. Осталось найти пиломатериал...
Учитель технологии выдал Тимофею круглую заготовку длиной c, от которой можно отрезать кусочки длиной a или b, обрабатывать и укладывать их в конструкцию в соответствии с исконно русскими традициями - венец за венцом.
По данным значениям a, b и c определите высоту избы. Считайте, что каждый ряд из двух продольных или трех поперечных брёвен увеличивает высоту дома на 1. Неполный ряд укладывать нельзя. Естественно, ряды из продольных и поперечных брёвен должны чередоваться.
Формат входных данных
Единственная строка входного файла содержит три натуральных числа, записанных через пробел: a, b и c - длины брёвен и заготовки.
Формат выходных данных
Выведите одно неотрицательное целое число - максимальную высоту модели избы, которую можно построить из заготовки.
Ограничения
1 ≤ a < b < c ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
В первом примере Тимофей уложит в первый ряд три поперечных бревна, отрезав от заготовки 9 единиц длины. Во второй ряд Тимофей должен будет уложить два продольных бревна, отрезав от заготовки еще 10 единиц длины. От заготовки осталось 9 единиц длины, их как раз хватит на третий ряд.
Во втором примере Тимофей сможет отрезать от заготовки лишь два продольных бревна и уложить их в единственный ряд.
Несчастный узник томится в одиночной камере. Из всех развлечений в его распоряжении лишь книга "Граф Монте-Кристо" и электронные часы, показывающие точное время в формате hh:mm (с ведущими нулями). Дисплей часов состоит из четырех индикаторов, в каждом из которых содержатся 7 сегментов (палочек), которые могут светиться и образовывать цифры. Таким образом, всего имеется 28 сегментов. Пример цифр таких часов приведен на рисунке.
Поскольку других источников света в камере нет, узник может читать книгу только при свете дисплея часов. При этом чтение возможно, только если в камере достаточносветло - то есть светится не менее n различных сегментов. Книга интересная, поэтому узник хочет узнать наиболее продолжительный непрерывный промежуток времени, в течение которого он сможет читать.
Формат входных данных
В единственной строке записано одно натуральное число n.
Формат выходных данных
Выведете одно натуральное число - ответ на задачу в минутах.
Ограничения
9 ≤ n ≤ 26
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
Наиболее продолжительный период времени, во время которого светятся не менее 12 сегментов, длится в течение 13 часов 59 минут - с 21:12 до 11:10 включительно.
Сегодня на занятии кружка по математике Тимофей узнал о существовании фигурных чисел. Больше всего его заинтересовали треугольные и квадратные числа.
Напомним, что число называется треугольным, если количество объектов, которое оно выражает, можно расставить в виде правильного треугольника. Аналогично, если это количество можно расставить в виде квадрата, то число называется квадратным.
На рисунке вы видите начало ряда треугольных чисел (1, 3, 6, 10, ...) и ряда квадратных чисел (1, 4, 9, 16, ...).
Тимофею нравится находить закономерности. Он смог доказать, что любое квадратное число (если оно больше 1) представимо в виде суммы всего двух треугольных чисел! Для поиска более сложных закономерностей ему нужно знать количество различных способов это сделать.
Помогите Тимофею! Найдите количество способов представления данного квадратного числа в виде суммы двух треугольных. Способы, отличающиеся порядком слагаемых, считаются одинаковыми.
Формат входных данных
В единственной строке входного файла записано одно натуральное квадратное число n.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Ограничения
4 ≤ n ≤ 1010
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
Комментарий к первому примеру: существует единственный способ представить 4 в виде суммы двух треугольных чисел: 4 = 3 + 1.
Комментарий ко второму примеру: существует два способа представить 16 в виде суммы двух треугольных чисел: 16 = 10 + 6 = 15 + 1.
Комментарий к третьему примеру: существует четыре способа представить 10000 в виде суммы двух треугольных чисел: 10000 = 5050 + 4950 = 5995 + 4005 = 8515 + 1485 = 9180 + 820.
По сюжету сатирической сказки Михаила Салтыкова-Щедрина «Повесть о том, как один мужик двух генералов прокормил», два отставных генерала, выйдя на пенсию, неизвестным образом попадают на необитаемый остров. Они хотят выбраться с острова, однако не могут, поскольку даже не разбираются в сторонах света. Вскоре они решают найти мужика (то есть крестьянина), который сможет их вернуть домой. Генералы находят на острове мужика. Мужик строит для них лодку и переправляет через моря в Петербург. По прибытии в Петербург они наедаются, напиваются и едут в казначейство за деньгами. В благодарность за спасение с острова они посылают мужику рюмку водки и пятак серебра, восклицая: «Веселись, мужичина!».
Но у нас не сказка, а задача, да и генералы с тех пор слегка изменились, поэтому они будут помогать мужику строить лодку. Для её изготовления нужно n досок, каждый человек за один день способен сделать одну доску. Мужик, как архетип неутомимого народа, способен работать каждый день, а вот генералам нужен отдых, выходные и отпуск на море (хорошо, что место действия соответствует). Поэтому первый генерал работает a дней подряд, а потом b дней подряд отдыхает. Второй генерал работает c дней подряд, а потом d дней подряд отдыхает. Как скоро будет построена лодка?
Формат входных данных
Единственная строка входного файла содержит пять натуральных чисел, записанных через пробел: n - требуемое количество досок, a, b, c и d - расписание работы генералов.
Формат выходных данных
В единственной строке выведите одно натуральное число - минимальное количество дней, требуемое для постройки лодки.
Ограничения
1 ≤ n ≤ 1018.
1 ≤ a, b, c, d ≤ 1015.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 106, получат не менее 40 баллов.
Пояснения к примерам
В первом примере нужно изготовить 11 досок. Мужик работает каждый день, первый генерал работает один день, потом отдыхает два дня, второй генерал работает два дня, потом отдыхает три. События будут развиваться следующим образом:
В первый день мужик и оба генерала делают по одной доске каждый.
Во второй день мужик и второй генерал делают по одной доске каждый, первый генерал отдыхает. Всего готово 5 досок.
В третий день работает только мужик, оба генерала отдыхают. Всего готово 6 досок.
В четвертый день мужик и первый генерал делают по одной доске каждый, второй генерал отдыхает. Всего готово 8 досок.
В пятый день работает только мужик, оба генерала отдыхают. Всего готово 9 досок.
В шестой день мужик и второй генерал делают по одной доске каждый, первый генерал отдыхает. Всего готово 11 досок - лодка построена. Работа завершена за 6 дней.
