CFRAC2 - Continuous Fractions Again
A simple continuous fraction has the form:
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 p / q, with integers p > q > 0, can be represented in a unique way by a simple continuous fraction with n terms, such that 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 matrix, then followed m lines, each line cantain n chars. The char matrix 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 10^20 > p > q > 0.
Example
Input: 9 17 ..........1...... 2.+.------------- ............1.... ....4.+.--------- ..............1.. ........1.+.----- ................1 ............5.+.- ................1 5 10 ......1... 1.+.------ .........1 ....11.+.- .........1 0 0 Output: 75 34 13 12
hide comments
prudhvi_495:
2019-06-16 23:02:40
easy one!!
|
|
nadstratosfer:
2018-06-06 18:44:04
Like CFRAC, fun while breaking down, very easy afterwards. Thumbs up!
|
|
sky_scraper:
2018-01-28 16:33:48
to make it clear just get the numbers separately and think for a formula/pattern the result follows |
|
nidhi_061:
2017-06-23 10:31:38
can anyone explain the problem please? I am not getting it. Last edit: 2017-06-23 10:32:09 |
|
prakash:
2016-11-09 14:17:22
very easy accept in 1go use long long int
|
|
darol:
2015-04-03 09:43:24
for numerator / denominator use long in java |
|
Daniel Carvalho:
2015-03-11 03:29:24
For those getting WA, here's a nice test case:
|
|
Anubhav Gupta:
2015-01-02 12:59:39
long long!!! |
|
Bharath Reddy:
2014-04-04 15:37:01
Very easy problem..
|
Added by: | Camilo Andrés Varela León |
Date: | 2007-01-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | HNU Contest |