|
|
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 -------------------- Can drunk King make the first and the last moves in the same direction? No comments if "NO COMMENTS" why you write this? information - Zero King cannot do that because the move to the corner and the move from that corner cannot be the same direction. 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!!! FFFFUUUU~. It's not Pascal, it's just Math!!1 how did you get to the formula? m*n-m-n-1+sqrt(2)*(n+m+1) answer of 9*9 is 88.87005769. Is it right? Edited by author 30.10.2008 07:13 Hm...my AC solution say yes 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 |
|
|