10555 - Dead Fraction

Farid Ahmadov · Post by **Farid Ahmadov** » Tue Sep 30, 2003 11:07 pm

Hi.
My program gives correct answers for all cases that I try. Maybe I miss something. 0.dddd means any fraction of form for example: 0.2165.

Here we're given 0.2165...
0.2165...=0.216555555555... or 0.2165...=0.2165216521652165...

I think my algorithm is correct. I take last digit from the end of the string.
I change 0.XXXX... to XXXX.... If last digit that I took is 9 then I add to XXXX... one. If it is not so I do following: (9*XXXX...+10*(last digit))/1000... Let A be 9*XXXX...+10*(last digit) and B be 1000...
while (A mod 2=0)and(B mod 2=0) do { divide A and B by 2 }
while (A mod 3=0)and(B mod 3=0) do { divide A and B by 3 }
while (A mod 5=0)and(B mod 5=0) do { divide A and B by 5 }
That's all.

I think this is correct. Maybe the problem is in Longint. It does not fit into Longint (long) or Int64 (long long)? Any help will do.

Thanks.

ditrix · Post by **ditrix** » Wed Oct 01, 2003 1:05 am

can anybody post a correct output for this input ?

Code: Select all

0.8...
0.508466572...
0.74998...
0.2112327...
0.70...
0.15021608...
0.4811...
0.023...
0.4189...
0.6338...
0.469161...
0.53317...
0.2095...
0.25...
0.867725163...
0.218500053...
0.6308...
0.958...
0.0...
0.1748121...
0.5097959...
0.7...
0.6129...
0.252...
0.33806765...
0.868690587...
0.1407...
0.27142445...
0.576253341...
0.20...
0

my output is the next :

Code: Select all

8/9
21186086/41666625
18731/24975
58089/275000
7/10
405989/2702700
433/900
7/300
31/74
251/396
677/1443
6598/12375
83/396
23/90
977167/1126125
1024219/4687500
1249/1980
863/900
0/1
7211/41250
33983/66660
7/9
613/1000
25/99
204869/606000
143333947/165000000
19/135
2467495/9090909
388049/673400
1/5

Abednego · Post by **Abednego** » Wed Oct 01, 2003 6:43 am

My program gives the same answers, and it gets WA.

What is the correct output for this?

0.0...
0.9...
0

My program prints

0/1
1/1

Red Scorpion · Post by **Red Scorpion** » Wed Oct 01, 2003 6:45 am

hi, ditrix.
my output exactly same as yours, except for this:
0.0...

.. There is no test case like that.
good luck.

Red Scorpion · Post by **Red Scorpion** » Wed Oct 01, 2003 6:51 am

hi, Abednego,

the result form :
0.9...

is : 1/1

Abednego · Post by **Abednego** » Wed Oct 01, 2003 6:58 am

Finally! I found a mistake in my code. Perhaps you have the same problem:
the answer to this test case:

0.123456789...
0

is NOT

10/81

I got it accepted after fixing that.

ditrix · Post by **ditrix** » Wed Oct 01, 2003 10:48 am

my output for 0.123456789... is 10287037/83325000 but I still have a "Wrong Answer" from judge. I have lightly modified my code and now it gives differents answers for some outputs. For example I take this input :

Code: Select all

0.74998...
0.53317...
0

and two outputs my program can produce are :

Code: Select all

18731/24975
6598/12375

or

Code: Select all

9740/12987
1310/2457

which is the right one? (the difference is to use the first 0 or not)

Per · Post by **Per** » Wed Oct 01, 2003 11:17 am

The first output set is the correct one.

little joey · Post by **little joey** » Wed Oct 01, 2003 11:45 am

I still don't understand the question. One issue that is not covered in the above examples is the question what exactly is the repeating part. The description doesn't cover that. Is it only the last digit? A run of digits that occurs more than once?

What is the answer for 0.1212...? Is it 0.1212222222... (121/1000+2/9000=1091/9000) or is it 0.121212121212... (12/99=4/33)?
The second one is the simpelest.

And for 0.31212...? Is it 0.312123121231212..., 0.31212121212... or 0.312122222222...?

A very vague description, Mr. Kisman.

Per · Post by **Per** » Wed Oct 01, 2003 11:54 am

This is the essence of the problem. We don't know how large the repeating part is, so we have to try every possible part (from 1 to d digits) and choose the one which results in lowest denominator.

little joey · Post by **little joey** » Wed Oct 01, 2003 12:30 pm

Right Per,

Thanks, now I get it.

But I still think the problem description could be more clear on this part. Even after reading it 10+ times I still had no clue, but your remark makes it all clear.

An example in the problem text would have made it much less ambiguous. But I sense a tendency lately to give less and less information and only give the most trivial of cases in the sample input. It almost looks like the problem setters are more destined to make you tripple over bad or incomplete descriptions, dirty input, vague or unspecified input types and missing range specifications, then testing one's programming skills. A case for the EPP, I would guess. Some form of quality assurance wouldn't be misplaced...

-little joey

gvcormac · Post by **gvcormac** » Wed Oct 01, 2003 4:40 pm

little joey wrote:Right Per,

Thanks, now I get it.

But I still think the problem description could be more clear on this part. Even after reading it 10+ times I still had no clue, but your remark makes it all clear.

An example in the problem text would have made it much less ambiguous. But I sense a tendency lately to give less and less information and only give the most trivial of cases in the sample input. It almost looks like the problem setters are more destined to make you tripple over bad or incomplete descriptions, dirty input, vague or unspecified input types and missing range specifications, then testing one's programming skills. A case for the EPP, I would guess. Some form of quality assurance wouldn't be misplaced...

-little joey

I can't speak for other contests, but the policy applied to Waterloo contests is that the problem statement should contain enough information to specify exactly the desired output. This policy does not imply that redundant or tutorial information is necessarily given. While the sample illustrates one or more cases it does not purport to explore the boundary cases.

For the fall Waterloo contests, each problem was solved beforehand by at least three people (this one was solved by four). Concerns of these solvers were reported to me, the contest administrator, and I made editorial changes in response to those concerns.

For this problem, it is my opinion there is only one reasonable interpretation of the problem statement - the one that yields the judges' output.

little joey · Post by **little joey** » Wed Oct 01, 2003 6:00 pm

Fair enough. I don't ask for redundant or tutorial information, I just want to understand the question after reading it some ten times or more. And since the question is ok, that leaves me, and all other people that didn't understand it, too stupid to solve it, I guess.

As for my second comment, I wasn't speeking about Waterloo specifically, I just made a general remark about a trend I noticed for some time, and now felt the need to write down. I know it's easy to complain beeing on the consumers side of problem setting, but I've solved some problems now and have a pretty solid opinion on what is a good problem description and what not. Writing about that in a forum like this is ment to be constructive critisism, not an attack on the problem setters. I'm sorry if my posting gave the wrong impression.

-little joey

Farid Ahmadov · Post by **Farid Ahmadov** » Wed Oct 01, 2003 8:28 pm

Hi everybody. Hi joey. I agree with you. Your opinion is absolutely correct.
And what if there is no forum on Online Judge's site. What will a problem solver do? I have read the description of problem nearly 10 times, to not miss anything in the problem statement. There was said nothing about the length of repeating part or the length of the string.

I found out that maximal length of the string is 14 and we can use (I think) Longint. But I tried both Int64 and Longint. And I still get WA.

For all sample inputs and for inputs here my program gives correct outputs.

INPUT:

Code: Select all

0.554...
0.9...
0.8...
0.88...
0.10...
0.987654321...
0.122222222...
0.101010...
0.12654...
0.12...
0.23100001...
0.8...
0.508466572...
0.74998...
0.2112327...
0.70...
0.15021608...
0.4811...
0.023...
0.4189...
0.6338...
0.469161...
0.53317...
0.2095...
0.25...
0.867725163...
0.218500053...
0.6308...
0.958...
0.1748121...
0.5097959...
0.7...
0.6129...
0.252...
0.33806765...
0.868690587...
0.1407...
0.27142445...
0.576253341...
0.20...
0

OUTPUT:

Code: Select all

61/110
1/1
8/9
8/9
1/10
54869684/55555555
11/90
10/99
174/1375
4/33
1049999/4545450
8/9
21186086/41666625
18731/24975
58089/275000
7/10
405989/2702700
433/900
7/300
31/74
251/396
677/1443
6598/12375
83/396
23/90
977167/1126125
1024219/4687500
1249/1980
863/900
7211/41250
33983/66660
7/9
613/1000
25/99
204869/606000
143333947/165000000
19/135
2467495/9090909
388049/673400
1/5

If there are inputs that I missed or there are wrong answers please tell me. Thanks.

Lain · Post by **Lain** » Wed Oct 01, 2003 8:41 pm

2ditrix:

May be you have the same mistake.

You're doing the problem using: (pred*(10^c-1)+cycle)/((10^c-1)*10^p), where 0.pred(cycle)...

How are you reducing the numbers in numerator and denominator?

Try gcd, If you don't use it.