Codeforces Beta Round 78 (Div. 1 Only) |
---|
Закончено |
Во дворе известного на все Тридевятое царство монастыря Лио Шань давным-давно боги воздвигли три алмазных стержня, возложив на один из них n золотых дисков разного диаметра (в порядке уменьшения диаметра снизу вверх), и повелели перенести все диски с первого стержня на третий по следующим правилам:
Однако дела у монастыря в последнее время шли не очень хорошо, и его мудрому настоятелю Ку Син Сану пришлось обтесать некоторые диски с боков, чтобы использовать золото на благо. В самом деле, нельзя же сидеть настоятелю без кондиционера, да и проводить круглый год в монастыре скучновато — нужно куда-нибудь иногда выбираться, покататься на лыжах, например... Лишь позже Ку Син Сан осознал свою ошибку: после обтесывания диаметры некоторых дисков стали одинаковыми, а значит, некоторые ходы, которые раньше было запрещено осуществлять правилами, теперь стали возможны (в самом деле, класть диск на диск того же диаметра боги не запрещали). Таким образом, возможный конец света мог наступить раньше, чем было задумано богами изначально, и возможно — намного раньше. Настолько раньше, что Ку Син Сан даже не успеет накататься на лыжах и понежиться под кондиционером.
Последнего мудрый настоятель допустить никак не мог и поэтому обратился за помощью к очень старой и очень мудрой колдунье ПикиВедии — может быть, она поможет определить, за какое минимальное количество ходов решается задача богов. Однако, погадав на картах, колдунья не смогла дать настоятелю ответ на его вопрос. Тогда он и обратился за помощью к вам.
Сможете ли вы по заданному количеству дисков и их диаметрам найти кратчайшее решение задачи, при условии, что диски одинакового диаметра разрешено класть один на другой, однако порядок дисков на третьем колышке после всех перемещений должен совпадать с первоначальным порядком дисков на первом колышке?
В первой строке записано целое число n — количество дисков (1 ≤ n ≤ 20). Во второй строке записаны n целых чисел di — диаметры дисков после обтесывания их Ку Син Саном, снизу вверх (1 ≤ di ≤ 20, кроме того, di ≥ di + 1 для любого 1 ≤ i < n).
В первой строке выведите число m — минимальное количество ходов для решения задачи богов. В следующие m строк выведите описания ходов: два натуральных числа si и ti через пробел, задающие, соответственно, номер колышка, с которого переносится диск, и номер колышка, на который переносится диск (1 ≤ si, ti ≤ 3, si ≠ ti).
3
3 2 1
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
3
3 1 1
5
1 2
1 2
1 3
2 3
2 3
3
3 3 3
5
1 2
1 2
1 3
2 3
2 3
Обратите внимание на третий тест, демонстрирующий, что в конце порядок дисков должен остаться прежним, даже несмотря на одинаковый радиус дисков. Без выполнения этого условия задачу богов можно было бы решить за меньшее количество ходов — три (просто переместив три диска с первого колышка на третий).
Название |
---|