НачалоПодразделы
Другие разделы
Дата и время
21/11/2024 23:50:56
962. Цепные дроби
Цепные дроби
Техника программирования, моделированиеОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 4I) |
| 09/07/2008 | Лето 2008 - 4 (I) |
| 04/11/2023 | Марафон 80 задач, 3 этап (G) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Простая цепная дробь имеет вид
где `a_i` – целые числа. Такую цепную дробь можно записать в виде `[a_1,\ a_2,\ a_3,\ …,\ a_n]`. Нетрудно показать, что любое рациональное число `p/q`, где `p`, `q` – целые числа и `p\ >\ q\ >\ 0` может быть единственным образом представлено цепной дробью `[a_1,\ a_2,\ …,\ a_{n-1},1]`, где `n` и `a_i` – натуральные числа.
Напишите программу, которая для заданного рационального числа находит и печатает простую цепную дробь.
Ввод
Входной файл содержит два целых чисел `p` и `q` (`10^18\ >\ p\ >\ q\ >\ 0`).
Вывод
Запишите в выходной файл результат как показано в примере. Цепная дробь должна быть напечатана с соблюдением следующих правил:
- Горизонтальные линии состоят из символов "-" (минус);
- Ширина каждой горизонтальной линии в точности равна ширине знаменателя;
- Пробелы изображаются символами "." (точка);
- Единицы в числителях должны выравниваться по центру горизонтальной линии, то есть, слева и справа от единицы должно быть одинаковое количество пробелов, если это возможно. В противном случае один дополнительный пробел должен быть добавлен справа.
Пример ввода 1
75 34
Пример вывода 1
..........1...... 2.+.------------- ............1.... ....4.+.--------- ..............1.. ........1.+.----- ................1 ............5.+.- ................1
Пример ввода 2
65 60
Пример вывода 2
......1... 1.+.------ .........1 ....11.+.- .........1
