| ENG RUS | Timus Online Judge |
Обсуждение задачи 1936. Шоушилинjk_qq Hint. // Задача 1936. Шоушилин 15 окт 2017 02:54 If you think it in a way of dynamic programming it could help. Imagine we have N pirats. Calculate probability of draw for single round (either all N pirats has the same gesture or there's a pirat for every possible gesture). Then calculate average number of rounds to be played before someone lost (standard geometric sum). Now someone is lost and we have the same game but with less pirats. So we can use DP-approach with probabilities. Use doubles, it's enough to get AC. You would be happy to implement this problem (my impl is 30 lines with i/o on c++). Motasem AL-Kayed not sure about statement // Задача 1936. Шоушилин 25 ноя 2016 01:32 the statement says "You should help him determine the expected value of prize in case of his victory" but I believe it should be the case of anyone's victory. can someone who solved the problem please clarify this? thanks Edit: I got accepted assuming the original statement is wrong Edited by author 25.11.2016 17:53 Yuiffy the problem of relative error // Задача 1936. Шоушилин 4 авг 2014 18:30 Many AC codes input the n=100, output have many zero before the radix point, the relative error is not enough very much! Why did they accept? Vladimir some tests [9] // Задача 1936. Шоушилин 11 ноя 2012 00:54 Give me, please, first 10-15 answers. bsu.mmf.team Re: some tests [6] // Задача 1936. Шоушилин 12 ноя 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. Here's your answers: 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 Vladimir Re: some tests // Задача 1936. Шоушилин 12 ноя 2012 23:04 Ok, thank you! Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: some tests [4] // Задача 1936. Шоушилин 18 дек 2012 04:19 What was the issue? For me straightforward implementation in C++ using double got AC easily. bsu.mmf.team Re: some tests [3] // Задача 1936. Шоушилин 3 янв 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 Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: some tests [2] // Задача 1936. Шоушилин 4 янв 2013 16:09 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+. bsu.mmf.team Re: some tests [1] // Задача 1936. Шоушилин 5 янв 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 :) Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: some tests // Задача 1936. Шоушилин 6 янв 2013 01:25 Giorgi Giglemiani [Freeuni] Re: some tests [1] // Задача 1936. Шоушилин 5 ноя 2013 04:57 good test: n=40 ans=3688328.070956036 Spatarel Dan Constantin Re: some tests // Задача 1936. Шоушилин 24 май 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 answer = 13552*3*4*4*1*6*18.186159417 Bogatyr The "beats" are backwards // Задача 1936. Шоушилин 12 ноя 2012 18:35 http://en.wikipedia.org/wiki/Rock-paper-scissors paper beats rock (by surrounding it) rock beats scissors (by smashing them) scissors beats paper (by cutting it) :)
|