eolymp
bolt
Try our new interface for solving problems
Məsələlər

Непрерывные дроби

Непрерывные дроби

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Простая непрерывная дробь имеет вид:

где каждое из a_i является целым числом.

Выше записанную непрерывную дробь можно записать как [a_1, a_2, ..., a_n]. Не трудно доказать, что любое рациональное число , с целыми p > q > 0, может быть представлено единственным образом в виде простой непрерывной дроби n терминами такими, что = [a_1, a_2, ..., a_{n-1}, 1], где n и все a_i являются натуральными числами.

Ваша задача найти и распечатать простую непрервную дробь, соотвтетсвующую заданому рациональному числу.

Giriş verilənləri

Вход состоит из серии тестовых случаев, по одному в строке. Каждая строка содержит 2 целых числа, разделенных пробелом p и q, таких, что 10^20 > p > q > 0.

На завершение входных даных указывает строка, которая содержит 0 0.

Çıxış verilənləri

Тестовые случаи должны обрабатываться в том порядке, в каком они поступают во входных данных. Выходные данные в каждом случае состоят из нескольких строк. Первая строка указывает номер тестового случая в следующем формате:

Case i:

где i нужно заменить на номер соответствующего теста.

/

Вторая строка содержит входные данные в формате pq.

Последующие строки должны содержать саму непрерывную дробь, соотвествующую рациональному числу , заданному во входных данных. Рациональная дробь должна быть напечатана в соответствии с такими правилами:

  • Горизонтальные линии образуются последовательностями символов '-'.

  • Длина каждой горизонтальной линии в точности равна длине знаменателя под ней.

  • Вместо пробелов должно быть напечатано соответствующее количество символов '.'.

  • Число в числителе должно быть напечатано по середине дроби, т.е количество заменителей пробелов должно быть одинаковым, в крайнем случае справа должно быть напечатано на один заменитель пробела больше.

Пример выходных данных

Nümunə

Giriş verilənləri #1
75 34
0 0
Çıxış verilənləri #1
Case 1:
75 / 34
..........1......
2.+.-------------
............1....
....4.+.---------
..............1..
........1.+.-----
................1
............5.+.-
................1