474 - Heads / Tails Probability

EggHead · Post by **EggHead** » Mon Dec 03, 2001 5:57 am

I was very surprised when I got WA of this prolbem. My program used log, so I can pass the largest data, but I don't know why I always got WA!
Please help!

FCS · Post by **FCS** » Tue Dec 04, 2001 3:37 am

Why don't you try storing your own exponent and mantissa instead? How might you have used logs? I think you may have a floating point precision problem.

EggHead · Post by **EggHead** » Thu Dec 06, 2001 10:16 am

Hello everyone!
I made a pascal program and try to pass 474, but failed all the time. And I found nearly no pascal programmers passed that. And some used C or C++ said they cannot pass with pascal! Why? Who can tell me? Thanks?

EggHead · Post by **EggHead** » Thu Dec 06, 2001 10:23 am

Of course I stored them by myself, and use log to calc a^b in pascal. Yeah, it may be float error between pascal and C.

And, Who can post me a program which can pass it?

wyvmak · Post by **wyvmak** » Thu Dec 13, 2001 7:35 pm

add this special case to your program:

2^-6 = 1.562E-2

Ilham Kurnia · Post by **Ilham Kurnia** » Tue Dec 25, 2001 12:05 pm

I think I'm one of two users who had solved this using Pascal... Well, I used floating point error checking twice... But then again, it's not something special isn't it?

I don't know exactly why there are only very few who have solved P#474 using Pascal. But, one of the notorious problems when you're making a solution using Pascal is that you have to be careful when you're reading the input. I recall having to try more than 5 different ways of reading input before getting my solution accepted.
Try using the following for Problem #474:

while not eof do
begin readln(n); Solve_it(N); end;

It may or may not help you...

[ This Message was edited by: Ilham Kurnia on 2001-12-25 11:06 ]

Alexander Denisjuk · Post by **Alexander Denisjuk** » Sat Jan 05, 2002 5:12 pm

On 2001-12-13 18:35, wyvmak wrote:
add this special case to your program:

2^-6 = 1.562E-2

But 2^-6 = 1.5625E-2!
So, the right answer should be 2^-6 = 1.563E-2!

Hence there is a mistake in test!

I think the matter of fact it the difference in rounding in C and Pascal.

In C: 1.5625E-2approx1.562E-2

In Pascal: 1.5625E-2approx1.563E-2

So, all the rejected Pascal programs (including my one

) should be accepted. All the accepted C programs (including my one

) should get WA.

Ilham Kurnia · Post by **Ilham Kurnia** » Sun Jan 06, 2002 3:23 pm

actually no...
When you round 0.015625 to 4 significant figures scientifically, you get 0.01562 instead of 0.01563.
There are 3 general rules for rounding:
(last digit means the (last digit + 1) in
dispute... so in the case above, it is 5)
1. If the last digit is greater than 5, then you round the previous digit up. If the last digit is less than 5, then you round it down.
2. If it is 5, you look at the following digit(s). If it is not equal to 0, then you round the previous digit up. Else, see the next rule.
3. Look at the previous digit. If it is an even number, then you round it down. If it is an odd number, then you round it up.

hope this helps.

[ This Message was edited by: Ilham Kurnia on 2002-01-06 14:24 ]

Ilham Kurnia · Post by **Ilham Kurnia** » Sun Jan 06, 2002 3:31 pm

Something that pops up to my mind...
Try to round the immediate results... My code is like that. somehow it avoids the rounding error.

hey... suddenly I'm the only person who got it right using pascal... strange... last week I saw another one...

[ This Message was edited by: Ilham Kurnia on 2002-01-06 14:40 ]

Alexander Denisjuk · Post by **Alexander Denisjuk** » Wed Jan 16, 2002 11:35 am

On 2002-01-06 14:23, Ilham Kurnia wrote:

There are 3 general rules for rounding:
(last digit means the (last digit + 1) in
dispute... so in the case above, it is 5)
.................
3. Look at the previous digit. If it is an even number, then you round it down. If it is an odd number, then you round it up.

This rule seems strange. Colud you please tell us the author of this rule?

I used the following rules of rounding, which one can find in "Academic Press Dictionary of Science and Technology" (cf. http://www.harcourt.com/dictionary/def/ ... 69500.html):

rounding Mathematics. the alteration of a radix representation of a real number, so that the true value of the number is represented to some desired accuracy. Also, rounding off. Any number whose radix representation is obtained in this manner is called a radix approximation. The following procedure is customarily followed: Let b be the base or radix used in the representation, and suppose the rightmost digit to be retained is followed by the digit x. If x <=(b - 1)/2, then the digits to the left of x are left unchanged, and x and the digits to its right are replaced with zeros. This is known as rounding down, since the result is less than or equal to the original number. If x > (b - 1)/2, then the rightmost digit to be retained is increased by 1 (carrying to the next place if necessary), and x and the digits to its right are replaced with zeros. This is known as rounding up, since the result is greater than or equal to the original number. Trailing zeros to the right of x are not written in the rounded number.

According to this rule (x=5, b=10, x>(b-1)/2) 0,015625 approx 0,01563. So the right answer for the case n=6 should be 1.563E-2. This answer does not depend on the algorithm you use to solve this problem, sinse 2^{-6}=0,015625 (it is exact value).

Since there are different rules of rounding, don't you think the better way is to eliminate the case n=6 from the test input data? The rounding is not the matter of the problem.

[ This Message was edited by: Alexander Denisjuk on 2002-01-16 10:50 ]

Ilham Kurnia · Post by **Ilham Kurnia** » Thu Jan 17, 2002 1:56 am

Try the following:

http://wind.cc.whecn.edu/~mechalke/chap ... apter2.PDF
http://www.chem.tamu.edu/class/fyp/math ... sigfg.html
and many more

Furthermore, I've looked at several general chemistry and physics books, they suggest the same.

However, your rounding method is not wrong. I recall that there are two types of rounding: the mathematical rounding, which you described, and the scientific rounding which I described and used by the judge (maybe).

hmmm... that other solution in Pascal is back in the list...

Ilham

[ This Message was edited by: Ilham Kurnia on 2002-01-17 01:01 ]

Alexander Denisjuk · Post by **Alexander Denisjuk** » Fri Jan 18, 2002 11:12 am

So,

should we ask the Judge to eliminate the case n=6 from the test set?

Ilham Kurnia · Post by **Ilham Kurnia** » Fri Jan 18, 2002 12:42 pm

be my guest, but i don't think they will. it is a valid test case, no matter what.

.. · Post by .. » Fri Jan 18, 2002 7:48 pm

I want to share my experience to all of you:

I have a progam that can be accepted by judge,

when I run it in Unix, it gives me
2^-6 = 1.563e-2
when I run it in Linux, it gives me
2^-6 = 1.562e-2

I am really confused about this.......

Also, I find that my program will gives me like this:
2^-28738 = 10.000e-8652
2^-70777 = 10.000e-21307
Certainly, this is WRONG answer.....
It seems that the test case doesn't contain these cases.........

Alexander Denisjuk · Post by **Alexander Denisjuk** » Sun Jan 20, 2002 1:53 pm

On 2002-01-18 11:42, Ilham Kurnia wrote:
be my guest, but i don't think they will. it is a valid test case, no matter what.

So they should write exact rounding rules to be used.

By the way, 2^(-7)= 0,0078125. So in the case n=7 there are also two possible answers.