|
|
Show all threads Hide all threads Show all messages Hide all messages | How to prove the formula? | Alexey Dergunov [Samara SAU] | 1631. Drunk King 2 | 7 Jul 2014 04:41 | 2 | It's very easy to get but how to prove it? Edited by author 08.08.2012 02:32 Warning: spoilers. Don't read if you have not solved problem. ------------------------------------------------------------ Well, I can't prove that there always exists path with such length, but I can prove that every path has at least such length. Obviously, we need to prove that there is always at least (n + m + 1) diagonal moves. Let cell be black if both it coordinates are not divisible by two and white otherwise. There are (n+1)(m+1)/4 black squares. Let f be amount of white cells we have visited plus amount of diagonal moves we have made. We start our movement from some black point. When we start f is zero. Assume we are now in black point. Lemma To reach another black points we need to increase f by at least 3. Proof: 10101 00000 10X01 00000 10101 (X is our cell, 0's are while squares, 1 are black). It's obvious, that if don't do diagonal moves at all, we need to visit at least 3 white squares. If we do at least 2, then we visit at least one white square, 2 + 1 = 3. If we do exactly 1, then if it is first move, then we can't leave white squares with second non-diagonal move. If first move is non-diagonal, then second diagonal can't help. So in that case it's true too. So we have proved lemma. Now, f is amount of diagonal moves plus nm - (n+1)(m+1)/4. From the other side f >= 3(n+1)(m+1)/4 because of lemma. So (amount of diagonal moves) >= 4(n+1)(m+1)/4 - nm = n + m + 1. Sorry for my bad English and possible bad explanation. Spoilers End -------------------- | d | EpicFail | 1631. Drunk King 2 | 8 Nov 2010 19:13 | 8 | d EpicFail 11 Oct 2008 15:38 Can drunk King make the first and the last moves in the same direction? Re: d Aisenshtein Daniil 11 Oct 2008 15:44 Re: d qwe (Dmitry) 11 Oct 2008 15:54 if "NO COMMENTS" why you write this? information - Zero Re: d spNautilus 11 Oct 2008 15:46 King cannot do that because the move to the corner and the move from that corner cannot be the same direction. Re: d BlackShark 25 Dec 2008 18:45 It's really easy!!! var n,m:real; begin readln(m,n); writeln((m*n-m-n-1+sqrt(2)*(n+m+1)):0:12); end. Pascal forever!!! Re: d Komarov Dmitry [Pskov SPI] 12 Nov 2009 01:59 FFFFUUUU~. It's not Pascal, it's just Math!!1 Re: d wRabbits_AlMag(VNTU) 5 Feb 2010 13:59 Re: d Vlas Tudor 8 Nov 2010 19:13 how did you get to the formula? m*n-m-n-1+sqrt(2)*(n+m+1) | 9*9? | freedevc | 1631. Drunk King 2 | 15 Apr 2010 23:55 | 2 | 9*9? freedevc 30 Oct 2008 07:11 answer of 9*9 is 88.87005769. Is it right? Edited by author 30.10.2008 07:13 Re: 9*9? monyura[ONU 1 2/3] 15 Apr 2010 23:55 Hm...my AC solution say yes | 9*7 | Dreik | 1631. Drunk King 2 | 29 Oct 2008 23:51 | 4 | 9*7 Dreik 11 Oct 2008 16:00 At test 9*7 answer is 71.284271. Is it rigtht? Correct answer is 70.041630560 Simple math :) Please! Could you give me formula of this problem? Thanks you. My email is freedevc@live.com Edited by author 29.10.2008 23:24 Edited by author 29.10.2008 23:24 Try to expand one from the sample picture :) it's very easy you'll see |
|
|
|