CFRAC2 - Continuous Fractions Again

A simple continuous fraction has the form:

subir imagenes

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 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 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.


    9 17
    5 10
    0 0
    75 34
    13 12

  • hide comments
    prudhvi_495: 2019-06-16 23:02:40

    easy one!!
    The numbers can be >= 10

    nadstratosfer: 2018-06-06 18:44:04

    Like CFRAC, fun while breaking down, very easy afterwards. Thumbs up!

    Daniel Carvalho's testcase is invalid, solve the first problem to see why.

    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

    Last edit: 2016-11-09 14:18:02
    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:
    3 5

    Anubhav Gupta: 2015-01-02 12:59:39

    long long!!!

    Bharath Reddy: 2014-04-04 15:37:01

    Very easy problem..
    I wonder why very few people have solved it..!

    Added by:Camilo Andrés Varela León
    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