strange problem Posted by svr 11 Mar 2008 21:33 I considered some constructions and got AC. But full analysis of the problem seems equals to scintific reserch. For this problem all timus correspondents very need in short, proven and full consideration but this is just mathematic vork. I know only: L-R==4; F==2*k- it's absolutely clear. Case F==0 possible only if 1) L=4;R=0 2) R=2*k,L=R+4;k>=2. I think but failed to prove that cases F==0,L==6;R==2 impossible also as if F==0,R=2*k+1;L=R+4; Cases when F=2*k>0 ,L=R+4,R>0 all possible, simple and depend on regular constructions. Resume:On olimpiads often impossible to have full foundations for your algorithms. Re: strange problem I agree that proving the correctness of your solution is a bit time-consuming for this task. Nevertheless, in the end the proof isn't that complicated, so I'll post it here in case someone finds it interesting. Suppose that we managed to position the plates (s straight segments and t turns) on the plane so that the line segments on them form a closed path. Let's introduce a coordinate system so that each plate can be described by a pair of integers (X, Y) giving the coordinates of its lower left corner. Let's start at any point in our closed path and traverse the entire path until we get back to the point where we started. At each point where we enter a new plate, let's look at the coordinates (X, Y) of the plate we're entering, and let's record a triple (x, y, d), where x = X mod 2, y = Y mod 2, and d is the direction we're facing at this particular point (one of N, W, S, E). If we know the triple (x, y, d) at the time we entered a plate, and if we know whether that plate is a left turn, a right turn, or a straight one, we can easily determine the triple that we'll get at the time we leave this plate and enter the next one. Thus for example, from 00N, a left turn takes you into 10W, a right turn takes you into 10E, and a straight segment takes you into 01N. If we keep computing possible transitions, we end up with a kind of state transition diagram with 16 possible states. I can't draw the diagram nicely here, but we can approximate it by arranging the states into a 4*4 grid: 00N 00S 01N 01S 10W 10E 00W 00E 11S 11N 10S 10N 01E 01W 11E 11W The transitions between states are very systematic: (1) A straight segment changes the state so that you remain in the same row, but move from the first column to the third (or vice versa), or from the second column to the fourth (or vice versa). (2) If you are in the left half of the grid (first two columns), a left turn moves you one row down (or from the fourth row back to the first one) but leaves you in the same column. A right turn moves you one row down as well, but it also switches you from the first to the second column and vice versa. (3) If you are in the right half of the grid (third and fourth column), a right turn moves you one row up (or from the first row into the fourth row) and leaves you in the same column. A left turn moves you one row up as well, but it also switches you from the third to the fourth column and vice versa. Of course, if our path is truly closed, we will finish in the same state where we started. We can assume without loss of generality that this state is 00N -- if it wasn't, we could always move and rotate the entire path (i.e. all the plates) a little bit. From (1) it follows that every straight segment moves us from the left half of the grid to the right one or vice versa. Since we started on the left half (in 00N) and have to finish there as well, it follows that the number of straight segments, i.e. s, must be even. From (2) and (3) it follows that every turn moves us from an odd row to an even row or vice versa. Since we started in the first row (in 00N) and must finish in the same row, it follows that the number of turns, i.e. t, must be even. We can also notice that a turn will always change the direction (the third character in our state) while a straight segment will leave it unchanged. For the path to be closed, we must be facing each of the four possible directions at some point, so we require at least four turns; thus t has to be >= 4. Now let's consider the special case when s = 0, i.e. there are no straight lines. Only the first two columns of our state grid are reachable (from 00N) in that case, and each turn we take moves us from the current row to the next row below it. Since we started in the first row and must finish in the first row as well, it follows that in this case t must be a multiple of 4. So, to summarize what we've seen so far: - s and t must be even - t must be >= 4 - if s = 0, then t must be a multiple of 4. Nearly all (s, t) that meet these constraints can be solved if we start by manually constructing solutions for cases where s = 0 and t = 4 or 16; and also for cases where s = 2 and t = 6 or 8 or 10. It is also easy to extend these paths by inserting 2 straight segments at a time, or by inserting 8 turns at a time. The only case which remains unsolved by these constructions is s = 0, t = 8. It turns out that no closed path exists with 8 turns and 0 straight segments, but I don't have an elegant proof of this (it is however easy to verify it with a program, using recursion). |