Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1369. Дверь в чудесный сад
Элементы теории чисел, диофантовы уравненияОлимпиадные задачи на русском языке
| 20/03/2010 | Южно-Уральский открытый командный чемпионат по программированию (A) |
| 27/03/2010 | Занятие 11 (C) |
| 14/11/2013 | Занятие 9 для продолжающих (C) |
| 07/07/2016 | Лето 2016 - 6 (командная) (A) |
Ограничения: время – 100ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
"Алиса открыла дверцу и увидела за ней нору, совсем узкую, не шире крысиной.
Алиса встала на колени и заглянула в нее – в глубине виднелся сад удивительной красоты. Ах, как ей захотелось
выбраться из темного зала и побродить между яркими цветочными клумбами и прохладными фонтанами! Но
она не могла просунуть в нору даже голову."
Если Алиса выпьет `K` капель из найденного на стеклянном столике пузырька, то ее рост уменьшится в `K` раз, а если
она откусит `L` кусочков от пирожка из коробочки под столом, то ее рост увеличится в `L` раз. Алиса может попасть в сад,
только если ее рост будет строго больше `P_1/Q_1` и строго меньше `P_2/Q_2`.
Напишите программу, определяющую по ограничениям на рост, сколько капель нужно выпить Алисе из пузырька и
сколько кусочков пирожка нужно съесть, чтобы попасть в сад. Начальный рост Алисы равен 1.
Первая строка ввода содержит 4 целых числа `P_1`, `Q_1`, `P_2`, `Q_2` (`1\ ≤\ P_1,\ Q_1,\ P_2,\ Q_2\ ≤\ 10^9`,
`P_1/Q_1\ <\ P_2/Q_2`) – ограничения на рост Алисы.
Вывести два целых числа `K` и `L` – наименьшее возможное количество капель (ведь "Алиса отлично помнила,
что если выпьешь слишком много из бутылки, на которой нарисованы череп и кости и написано "Яд!", то почти наверняка
тебе не поздоровится") и количество кусочков пирожка. Если существует несколько вариантов для значения `L`,
то вывести наименьшее из них.
Пример ввода
27 161 28 160
Пример вывода
23 4
