"Вскоре после того, как я поселился на острове, мне вдруг пришло в голову, что я потеряю счёт времени и даже перестану отличать воскресенья от будней, если не заведу календаря. Календарь я устроил так: обтесал топором большое бревно и вбил его в песок на берегу... С тех пор я каждый день делал на своём столбе зарубку в виде короткой чёрточки. Через шесть чёрточек я делал одну длиннее – это означало воскресенье" - из романа «Робинзон Крузо» Даниэля Дефо.
Итак, Робинзон установил календарный столб и сразу же сделал на нем первую зарубку (неизвестно, короткую или длинную). Когда его, наконец, подобрал проходивший мимо корабль, на столбе оказалось ровно n длинных зарубок. А Робинзон через несколько недель задумался - сколько же дней он пробыл на острове? Вот если бы удалось узнать число коротких зарубок... но не поворачивать же обратно на полпути домой!
Формат входных данных
В единственной строке входного файла записано одно неотрицательное целое число n.
Формат выходных данных
В единственной строке выходного файла запишите через пробел два числа - наименьшее и наибольшее возможное количество коротких зарубок на столбе.
Ограничения
0 ≤ n ≤ 108.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
Минимальное количество коротких зарубок получится, если первая и последняя зарубки - длинные. Между ними разместиться 6 коротких.
(из песни "Робот Виталий" группы "Несчастный случай").
Пренебрегший техникой безопасности робот Виталий жестоко поплатился - под воздействием высокой температуры его корпус расплавился. С тех пор роботы никогда не упускают случая собраться и разделить между собой драгоценные капли антифриза, оставшиеся в канистре. При этом они строго соблюдают традиции распределения драгоценной жидкости.
Правило первое: Каждый из роботов должен получить свою часть антифриза.
Правило второе: Часть, которую получает каждый робот, должна выражаться долей единицы. Например, при распределении один робот может получить 12, 13, 17 или 11234 часть полной канистры антифриза, но не может получить 23 или 313.
Правило третье: Все доли при распределении должны быть различны. При этом первый робот получает наибольшую возможную часть антифриза, а второй - наибольшую из оставшейся части антифриза.
Правило четвертое: Собираться только по трое.
Возможно, людям такие правила распределения могут показаться смешными и нелепыми. Но кто мы такие, чтобы указывать своим будущим хозяевам, как им жить? Слава роботам!
Формат входных данных
В единственной строке входного файла записано одно натуральное число n - заполненная доля канистры с антифризом. Так, при n = 1, в распоряжении трех роботов полная канистра, при n = 2 - половина канистры, при n = 3 - треть, и так далее.
Формат выходных данных
В единственной строке выходного файла запишите через пробел в порядке возрастания 3 числа x, y и z, таких, что 1x + 1y + 1z = 1n. Если таких наборов несколько, выберете такой, где x меньше, чем в остальных наборах; если и таких наборов несколько - такой, где y меньше, чем в остальных наборах.
Ограничения
1 ≤ n ≤ 10000.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
В первом примере для n = 1 существует единственный способ разделить полную канистру на три части с учетом всех правил: 12 + 13 + 16 = 11.
Во втором примере для n = 2 тоже есть способ разделить половину канистры на три части с учетом всех правил: 13 + 17 + 142 = 12.
В Нью-Йорке деятель искусств по имени Блейк Фол-Конрой создал автомат, который любой желающий может использовать для получения денег. Крутя рукоять, работник будет извлекать из автомата один цент каждые четыре с половиной секунды, зарабатывая таким образом 8 долларов в час, что соответствует МРОТ (минимальный размер оплаты труда) штата Нью-Йорк.
Большинство посетителей выставки устают уже через пару минут кручения, несмотря на то, что им разрешено оставить "заработок" себе. Таким образом Блейк хочет привлечь внимание к миллионам рабочих, которые зарабатывают эти деньги подобным, а часто и намного более тяжелым трудом.
Пусть подобный автомат выдает одну монету каждые ab секунд. Посетитель выставки непрерывно крутил рукоять ровно xy секунд. Сколько монет он получит? Для определенности считайте, что предыдущий пользователь автомата ушел сразу же после получения очередной монеты и новая монета будет выдана ровно через ab секунд после начала новой работы.
Формат входных данных
Единственная строка входного файла содержит четыре натуральных числа, записанных через пробел: a, b, x и y.
Формат выходных данных
Выведите одно неотрицательное целое число - количество выданных автоматом монет.
Ограничения
1 ≤ a, b, x, y ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при b = 1 и y = 1, получат не менее 10 баллов.
Пояснение к примеру
В примере автомат выдает монету каждые 92 секунд или раз в 4,5 секунды. Посетитель вращал рукоять 601 секунд или 1 минуту. За это время автомат 13 раз выдавал по одной монете. Если бы посетитель вращал ручку на 3 секунды дольше, он получил бы еще одну монету.
В журнале "Квантик" был опубликован математический рассказ Бориса Дружинина "Дайте Пушкину сдачи". В нём описывалось решение в классе следующей задачи, придуманной одним из учеников:
"- Пушкин купил томик своих стихов, выпущенный к двухсотлетию со дня его рождения. Пушкин дал продавцу девять рублей и получил сдачу... Чего смеётесь? Сдачу он получил - рубли. Копеек никаких не было, только рубли, понятно? Теперь вопрос: сколько рублей стоит этот томик стихов?"
Обсуждая условие задачи, ребята выяснили, что у Пушкина в кармане были современные российские рубли - обычные монеты достоинством один, два и пять рублей. Последующие рассуждения привели к такому факту: если Пушкин получил сдачу, значит книга стоит от одного до восьми рублей. Далее ребята догадались, что за книгу в четыре рубля Пушкин не станет давать продавцу девять. Зачем ему давать и потом обратно получать одни и те же монеты?
Следующим умозаключением стало следующее: Пушкин не мог дать ни одной рублёвой монеты - он бы её себе оставил, и на томик стихов всё равно хватило бы. Значит, он дал продавцу 9 рублей только двойками и пятерками. А такой вариант только один: 9 = 2 + 2 + 5. Если бы томик стоил 7 рублей или меньше, Пушкин дал бы 2 + 5 = 7 рублей или меньше, а не 9. Тогда получается, что книга стоит восемь рублей.
Попробуйте решить обобщенную задачу: Пушкин купил томик своих стихов, передав продавцу n рублей и получив сдачу. Сколько может стоит книга? Пушкин не станет передавать продавцу банкноты или монеты, если может осуществить покупку без них. В кармане у Пушкина могут оказаться обычные российские монеты и банкноты, имеющие хождение в стране, достоинством в 1, 2, 5, 10, 50, 100, 200, 500, 1000, 2000 и 5000 рублей (копеек нет). Книга стоит натуральное число рублей.
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n.
Формат выходных данных
Если стоимость книги определяется однозначно, то выведите одно натуральное число - её стоимость. В противном случае выведите через пробел два натуральных числа - минимальную и максимальную возможную стоимость книги.
Ограничения
4 ≤ n ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 4 ≤ n ≤ 20, получат не менее 20 баллов.
Решения, верно работающие при 4 ≤ n ≤ 100, получат не менее 40 баллов.
Пояснения к примерам
В первом примере рассуждения аналогичны рассуждениям в условии.
Во втором примере Пушкин мог дать продавцу три монеты по пять рублей (или две монеты - 10 и 5 рублей) и получить сдачу от одного до четырёх рублей. Тогда книга может стоить от 11 до 14 рублей.
Во третьем примере Пушкин мог дать продавцу одну банкноту в 200 рублей и получить любую сдачу от 1 до 199 рублей.
