{"problem":{"name":"D. Help Monks","description":{"content":"In a far away kingdom is the famous Lio Shan monastery. Gods constructed three diamond pillars on the monastery's lawn long ago. Gods also placed on one pillar _n_ golden disks of different diameters ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF98D"},"statements":[{"statement_type":"Markdown","content":"In a far away kingdom is the famous Lio Shan monastery. Gods constructed three diamond pillars on the monastery's lawn long ago. Gods also placed on one pillar _n_ golden disks of different diameters (in the order of the diameters' decreasing from the bottom to the top). Besides, gods commanded to carry all the disks from the first pillar to the third one according to the following rules:\n\n*   you can carry only one disk in one move;\n*   you cannot put a larger disk on a smaller one.\n\nThere was no universal opinion concerning what is to happen after the gods' will is done: some people promised world peace and eternal happiness to everyone, whereas others predicted that the kingdom will face communi… (gee, what am I rambling about?) the Armageddon. However, as everybody knew that it was impossible to solve the problem in less than 2_n_ - 1 moves and the lazy Lio Shan monks never even started to solve it, everyone lives peacefully even though the problem was never solved and nobody was afraid of the Armageddon.However, the monastery wasn't doing so well lately and the wise prior Ku Sean Sun had to cut some disks at the edges and use the gold for the greater good. Wouldn't you think that the prior is entitled to have an air conditioning system? Besides, staying in the monastery all year is sooo dull… One has to have a go at something new now and then, go skiing, for example… Ku Sean Sun realize how big a mistake he had made only after a while: after he cut the edges, the diameters of some disks got the same; that means that some moves that used to be impossible to make, were at last possible (why, gods never prohibited to put a disk on a disk of the same diameter). Thus, the possible Armageddon can come earlier than was initially planned by gods. Much earlier. So much earlier, in fact, that Ku Sean Sun won't even have time to ski all he wants or relax under the air conditioner.\n\nThe wise prior could never let that last thing happen and he asked one very old and very wise witch PikiWedia to help him. May be she can determine the least number of moves needed to solve the gods' problem. However, the witch laid out her cards and found no answer for the prior. Then he asked you to help him.\n\nCan you find the shortest solution of the problem, given the number of disks and their diameters? Keep in mind that it is allowed to place disks of the same diameter one on the other one, however, the order in which the disks are positioned on the third pillar in the end should match the initial order of the disks on the first pillar.\n\n## Input\n\nThe first line contains an integer _n_ — the number of disks (1 ≤ _n_ ≤ 20). The second line contains _n_ integers _d__i_ — the disks' diameters after Ku Sean Sun cut their edges. The diameters are given from the bottom to the top (1 ≤ _d__i_ ≤ 20, besides, _d__i_ ≥ _d__i_ + 1 for any 1 ≤ _i_ < _n_).\n\n## Output\n\nPrint on the first line number _m_ — the smallest number of moves to solve the gods' problem. Print on the next _m_ lines the description of moves: two space-separated positive integers _s__i_ and _t__i_ that determine the number of the pillar from which the disk is moved and the number of pillar where the disk is moved, correspondingly (1 ≤ _s__i_, _t__i_ ≤ 3, _s__i_ ≠ _t__i_).\n\n[samples]\n\n## Note\n\nPay attention to the third test demonstrating that the order of disks should remain the same in the end, even despite the disks' same radius. If this condition was not necessary to fulfill, the gods' task could have been solved within a smaller number of moves (three — simply moving the three disks from the first pillar on the third one).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在遥远的王国中，有一座著名的黎山寺院。众神很久以前在寺院的草坪上建造了三根钻石柱子，并在其中一根柱子上放置了 #cf_span[n] 个不同直径的金盘（按直径从底部到顶部递减的顺序排列）。此外，众神命令将所有圆盘按照以下规则从第一根柱子移动到第三根柱子：\n\n然而，寺院近年来运势不佳，智慧的住持 ku sean sun 不得不将一些圆盘的边缘切掉，将黄金用于更重要的用途。难道你认为住持没有资格拥有空调系统吗？此外，全年待在寺院里实在太无聊了……人总得尝试点新鲜事物，比如去滑雪……ku sean sun 在切完边缘后才意识到自己犯了一个大错：切完之后，一些圆盘的直径变得相同；这意味着一些原本不可能完成的操作现在变得可能了（因为众神从未禁止将一个圆盘放在直径相同的另一个圆盘上）。因此，末日可能比众神最初计划的更早到来——早得多。以至于 ku sean sun 根本没有足够的时间去滑雪或在空调下放松。\n\n这位智慧的住持绝不能让最后这件事发生，于是他求助于一位极其年长且极其智慧的女巫 pikiwedia。也许她能确定解决众神问题所需的最少移动次数。然而，女巫摊开她的牌后，却未能为住持找到答案。于是他请你来帮忙。\n\n你能找到这个问题的最短解法吗？给定圆盘数量及其直径。请记住，允许将直径相同的圆盘叠放，但最终第三根柱子上圆盘的顺序必须与初始第一根柱子上的顺序一致。\n\n第一行包含一个整数 #cf_span[n] —— 圆盘的数量（#cf_span[1 ≤ n ≤ 20]）。第二行包含 #cf_span[n] 个整数 #cf_span[di] —— ku sean sun 切割边缘后的圆盘直径。直径按从底部到顶部的顺序给出（#cf_span[1 ≤ di ≤ 20]，且对任意 #cf_span[1 ≤ i < n]，有 #cf_span[di ≥ di + 1]）。\n\n第一行输出一个整数 #cf_span[m] —— 解决众神问题所需的最少移动次数。接下来的 #cf_span[m] 行，每行描述一次移动：两个用空格分隔的正整数 #cf_span[si] 和 #cf_span[ti]，分别表示从哪根柱子移动圆盘以及移动到哪根柱子（#cf_span[1 ≤ si, ti ≤ 3]，#cf_span[si ≠ ti]）。 \n\n注意第三个测试用例表明，即使圆盘直径相同，最终第三根柱子上圆盘的顺序也必须与初始顺序一致。如果这一条件不是必须满足的，众神的问题可以用更少的移动次数解决（只需三次——直接将三个圆盘从第一根柱子移到第三根柱子）。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] —— 圆盘的数量（#cf_span[1 ≤ n ≤ 20]）。第二行包含 #cf_span[n] 个整数 #cf_span[di] —— ku sean sun 切割边缘后的圆盘直径。直径按从底部到顶部的顺序给出（#cf_span[1 ≤ di ≤ 20]，且对任意 #cf_span[1 ≤ i < n]，有 #cf_span[di ≥ di + 1]）。\n\n## Output\n\n第一行输出一个整数 #cf_span[m] —— 解决众神问题所需的最少移动次数。接下来的 #cf_span[m] 行，每行描述一次移动：两个用空格分隔的正整数 #cf_span[si] 和 #cf_span[ti]，分别表示从哪根柱子移动圆盘以及移动到哪根柱子（#cf_span[1 ≤ si, ti ≤ 3]，#cf_span[si ≠ ti]）。 \n\n[samples]\n\n## Note\n\n注意第三个测试用例表明，即使圆盘直径相同，最终第三根柱子上圆盘的顺序也必须与初始顺序一致。如果这一条件不是必须满足的，众神的问题可以用更少的移动次数解决（只需三次——直接将三个圆盘从第一根柱子移到第三根柱子）。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of disks.  \nLet $ D = (d_1, d_2, \\dots, d_n) $ be the sequence of disk diameters, where $ d_i \\geq d_{i+1} $ for all $ 1 \\leq i < n $, and $ 1 \\leq d_i \\leq 20 $.  \nLet the three pillars be labeled $ 1, 2, 3 $.  \nInitially, all disks are stacked on pillar $ 1 $ in order $ d_1 $ (bottom) to $ d_n $ (top).  \nThe goal is to move all disks to pillar $ 3 $, preserving the **exact vertical order** (i.e., if disk $ i $ was below disk $ j $ initially, then disk $ i $ must remain below disk $ j $ on pillar $ 3 $).\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 20 $  \n2. $ 1 \\leq d_i \\leq 20 $ for all $ i $  \n3. $ d_i \\geq d_{i+1} $ for all $ 1 \\leq i < n $  \n4. A disk may be placed on another disk **if and only if** its diameter is **less than or equal to** the diameter of the disk below it.  \n5. Only the top disk of a pillar may be moved.  \n6. The final configuration on pillar $ 3 $ must have the disks in the **same relative order** as initially: $ d_1 $ at bottom, $ d_n $ at top.\n\n**Objective**  \nFind the **minimum number of moves** $ m $ and the sequence of moves $ (s_i, t_i) $, $ i = 1, \\dots, m $, such that:  \n- Each move transfers the top disk from pillar $ s_i $ to pillar $ t_i $,  \n- All constraints are satisfied,  \n- The final stack on pillar $ 3 $ matches the initial order.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF98D","tags":["constructive algorithms"],"sample_group":[["3\n3 2 1","7\n1 3\n1 2\n3 2\n1 3\n2 1\n2 3\n1 3"],["3\n3 1 1","5\n1 2\n1 2\n1 3\n2 3\n2 3"],["3\n3 3 3","5\n1 2\n1 2\n1 3\n2 3\n2 3"]],"created_at":"2026-03-03 11:00:39"}}