| ENG RUS | Timus Online Judge |
2149. Pigeonhole PrincipleTime limit: 0.5 second Memory limit: 256 MB Little Pete Dirichlet likes pigeons a lot. He comes to the dovecote everyday, puts pigeons into holes and counts how many pigeons there are in each hole. One day he found n holes, and the dovecote had exactly n pigeons. Also, n was even. Pete put pigeons into holes so that each hole contains exactly one pigeon. “So beautiful!” — he had thought at first, but then looked carefully and saw this:  His inner perfectionist got upset, and he decided to change the orientation of some pigeons, so that they would sit in a nice pattern. Pete considers these two patterns nice:
Find out the smallest amount of pigeons whose orientation needs to be changed to form a nice pattern. InputThe first line contains one even integer n — the amount of pigeons (2 ≤ n ≤ 100). Then, three lines of length 5n − 1 each follow. They describe n pigeons. Every pigeon takes up four characters in each of the three lines. Pigeons, oriented to the left and to the right respectively, are denoted like this:
<@.. ..@>
.OO= =OO.
./\. ./\.
Characters used are “ .” (code 46), “/” (code 47), “<” (code 60), “=” (code 61), “>” (code 62), “@” (code 64), “O” (code 79), “\” (code 92). Each pair of adjacent pigeons are separated with a column of periods. It is guaranteed that lines contain nothing except for descriptions of pigeons and columns separating them.OutputOutput one number — the answer to the problem. Samples
NotesIn the first example he needs to rotate the first, the fourth and the last two pigeons, then the first half would look to the left, and right half — to the right. In the second example he needs to rotate the first pigeon so they would alternate. Problem Author: Kirill Borozdin Tags: problem for beginners |