ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1936. Roshambo

some tests
Posted by Vladimir 11 Nov 2012 00:54
Re: some tests
Posted by bsu.mmf.team 12 Nov 2012 17:30
It's not hard to get the correct formula for this problem, but harder to implement it because of high precision required.
At last I had to use precalculated array for getting AC.
2 -> 1.5
3 -> 2.25
4 -> 3.21428571
5 -> 4.48571429
6 -> 6.21981567
7 -> 8.64673579
8 -> 12.1044438
9 -> 17.0919353
10 -> 24.3495978
Re: some tests
Posted by Vladimir 12 Nov 2012 23:04
Ok, thank you!
Re: some tests
What was the issue? For me straightforward implementation in C++ using double got AC easily.
Re: some tests
Posted by bsu.mmf.team 3 Jan 2013 16:04
How did you take 100th power of 3/2?
I can't think it out. I've never used decimal long arithmetic.

Edited by author 03.01.2013 16:06

Edited by author 03.01.2013 16:06
Re: some tests
It is useful to remember that standard double type can store numbers up to 10^300 (and even a bit more). (3/2)^100 < 2^100 < 10^35
=> no problem to compute it in double. And since you need relative accuracy of only 7 digits => 16+ digits that double variable stores is more than enough to compute what you need.
Actually, here with usual double you can calculate answers for n up to 500+.
Re: some tests
Posted by bsu.mmf.team 5 Jan 2013 23:41
Is it really true?
I always thought that double type takes only 8 bytes of memory and hence cannot store such big numbers.
But anyway thank you. Maybe I just have bad compiler or bad implementation as always :)
Re: some tests
Re: some tests
Posted by Giorgi Giglemiani [Freeuni] 5 Nov 2013 04:57
good test:
n=40 ans=3688328.070956036
Re: some tests
Posted by Spatarel Dan Constantin 24 May 2014 01:44
The problem asks for at least 6 correct decimals. I had to compute up to 100 decimals (in intermediate computations) to get the required precision in the final answer for n = 100.

Here is the (censored) answer for the biggest possible test:
n = 100