Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
Continuous Fractions Again
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 4, Accepted users: 3
Problem 10042 : No special judgement
Problem description
  A simple continuous fraction has the form:

a1 + $\displaystyle {\frac{{1}}{{a_{2}+{\displaystyle \frac{1}{a_{3}+{\displaystyle \frac{1}{\ddots+{\displaystyle \frac{1}{a_{n}}}}}}}}}}$

where the ai's are integer numbers.

The previous continuous fraction could be noted as [a1, a2,..., an]. It is not difficult to show that any rational number $ {\frac{{p}}{{q}}}$, with integers p > q > 0, can be represented in a unique way by a simple continuous fraction with n terms, such that $ {\frac{{p}}{{q}}}$ = [a1, a2,..., an-1, 1], where n and the ai's are positive natural numbers.

Now given a simple continuous fraction, your task is to calculate a rational number which the continuous fraction most corresponds to it.

Input
  Input for each case will consist of several lines. The first line is two integer m and n,which describe a char martrix,then followed m lines,each line cantain n chars.
The char martrix describe a continuous fraction The continuous fraction is described by the following rules:

  • Horizontal bars are formed by sequences of dashes `-'.
  • The width of each horizontal bar is exactly equal to the width of the denominator under it.
  • Blank characters should be printed using periods `.'
  • The number on a fraction numerator must be printed center justified. That is, the number of spaces at either side must be same, if possible; in other case, one more space must be added at the right side.
The end of the input is indicated by a line containing 0 0.

Output
  Output will consist of a series of cases, each one in a line corresponding to the input case. A line describing a case contains p and q, two integer numbers separated by a space, and you can assume that 1020 > p > q > 0.

Sample Input
9 17
..........1......
2.+.-------------
............1....
....4.+.---------
..............1..
........1.+.-----
................1
............5.+.-
................1
5 10
......1...
1.+.------
.........1
....11.+.-
.........1
0 0
Sample Output
75 34
13 12
Judge Tips
  输出的最后结果应该是既约分数,也就是不能再进行约分。

Problem Source
  HNU Contest 

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:5881 today,10453982 total, since 2010-05-07