printЛето 4

printI. Цепные дроби

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Простая цепная дробь имеет вид
5325.gif
где `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
Источник: Весенний турнир имени Мартовского Зайца, 2007
loading