| ENG RUS | Timus Online Judge |
Уральская региональная командная олимпиада по программированию 2019
Соревнование завершено
L. Принцип ДирихлеОграничение времени: 0.5 секунды Ограничение памяти: 256 МБ Юный Петя Дирихле очень любит голубей. Каждый день он приходит на голубятню, рассаживает голубей по клеткам и считает, сколько голубей получилось в каждой из клеток. В один из дней у Пети оказалось n клеток и он нашёл на голубятне n голубей. Причём, оказалось, что n — чётное. Петя рассадил их по клеткам так, что в каждой клетке сидит ровно один голубь. «Как красиво!» — подумал, было, Петя, но тут увидел вот это:  Внутренний принципиальный перфекционист взыграл в нём, и он решил поменять ориентацию голубей, чтобы они сидели красиво. Петя считает, что голуби сидят красиво в двух случаях:
Определите минимальное количество голубей, у которых нужно поменять ориентацию, чтобы они сидели красиво. Исходные данныеВ первой строке дано одно чётное число n — количество голубей (2 ≤ n ≤ 100). Далее идут три строки длиной 5n − 1 символов каждая. В них описываются n голубей. Каждый голубь занимает по четыре символа в каждой из трёх строк. Так обозначаются голуби, повёрнутые влево и вправо соответственно:
<@.. ..@>
.OO= =OO.
./\. ./\.
Используются символы « .» (код 46), «/» (код 47), «<» (код 60), «=» (код 61), «>» (код 62), «@» (код 64), «O» (код 79), «\» (код 92). Каждая пара соседних голубей разделена одним столбцом из точек. Гарантируется, что в строках не содержится ничего, кроме точек и описания голубей.РезультатВыведите единственное число — ответ на задачу. Примеры
ЗамечанияВ первом примере нужно повернуть первого, четвёртого и двух последних голубей, тогда первая половину голубей будет смотреть влево, а вторая — вправо. Во втором примере нужно повернуть первого голубя, и тогда они будут чередоваться. Автор задачи: Кирилл Бороздин Источник задачи: Уральская командная олимпиада по программированию 2019 |