Giải mã phân số

Xem PDF

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 586M Input: bàn phím Output: màn hình

Cho phân số có dạng \(\frac{p}{q}\) trong đó \(p,q\) là các số nguyên dương. Và người ta chứng minh được rằng, luôn tồn tại duy nhất một bộ giải mã \((a_1,a_2,...,a_n)\) của phân số \(\frac{p}{q}\)thoả mãn các điều kiện sau:

  • \(a_i\in \mathbb{N}^{*}\text{ } (\forall i=\overline{1,n})\)

  • \(a_n=1\)

  • \(\frac{p}{q}=a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{...+\frac{1}{a_n}}}}\)

Yều cầu: Cho trước hai số nguyên dương \(p,q\). Hãy in ra bộ giải mã của \(\frac{p}{q}\) dưới dạng như sau:

  • Những kí tự trống ta in ra dấu ".".

  • Đối với thanh ngang của phân số ta sử dụng các chuỗi các dấu "-".

  • Tử số phải nằm tương ứng với điểm chính giữa của thanh ngang phân số.

  • Thanh ngang phân số phải có độ dài vừa đủ bao phủ phần mẫu bên dưới.

(Để hiểu rõ hơn, các bạn có thể xem ví dụ bên dưới).

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 30)\) - Thể hiện số testcase.

  • \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(p,q(0<q<p<10^{18})\) và đề bài ra đảm bảo \(p>q\).

Output

  • Ứng với mỗi testcase, in ra kết quả có dạng như sau:

  • Dòng thứ nhất ghi: Case i: với \(1\le i\le t\).

  • Block tiếp theo, biểu diễn bộ giải mã của phân số tương ứng.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(50>p>q>0\).

  • Subtask \(2\) (\(80\%\) số điểm): \(10^{18}>p>q>0\).

Example

Test 1

Input
3
39 16
39 19
1002 1001 
Output
Case 1:
..........1......
2.+.-------------
............1....
....2.+.---------
..............1..
........3.+.-----
................1
............1.+.-
................1
Case 2:
......1...
2.+.------
.........1
....18.+.-
.........1
Case 3:
.......1....
1.+.--------
...........1
....1000.+.-
...........1

Bình luận

Không có bình luận nào.