НачалоПодразделы
Дата и время
21/11/2024 23:16:48
Лето 4
A. Олимпиада B. Оффшорное программирование C. Многоугольник D. Стена E. Сортировка списка F. Разбиение матрицы G. Обобщённые матрёшки H. Узелки I. Цепные дроби J. Унарная система счисления K. Башня
I. Цепные дроби
Техника программирования, моделированиеОлимпиадные задачи на русском языке
| 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
