Հանոյի աշտարակներ
Տրված են 3 ձողեր (ձախը – 1, միջինը – 2, աջը – 3), որտեղ առաջին ձողի վրա գտնվում են տարբեր չափերի
n կլոր սկավառակներ։ Սկավառակները դասավորված են փոքրից մեծ՝ վրայից ներքև։ Թույլատրվում է միայն վերևի սկավառակը տեղափոխել մեկ ձողից մյուսը՝ տեղադրելով այն ավելի մեծ սկավառակի վրա։ Այսինքն, մեծ սկավառակը չի կարելի դնել փոքր սկավառակի վրա։Ձեզ խնդրում են տպել բոլոր այն գործողությունները, որոնք թույլ են տալիս բոլոր սկավառակները տեղափոխել առաջին ձողից երրորդը՝ օգտագործելով հնարավոր նվազագույն քանակի քայլեր։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 16), որը ցույց է տալիս սկավառակների քանակը առաջին ձողի վրա:Ելք
Ծրագիրը պետք է տպի բոլոր այն գործողությունները, որոնք անհրաժեշտ են սկավառակները առաջին ձողից երրորդը տեղափոխելու համար, որովհետև յուրաքանչյուր ձողի վրա գտնվող սկավառակներից ամեն մեկը պետք է լինի իրենից ներքև գտնվող սկավառակից փոքր։ Արդյունքում տպվող գործողությունների քանակը չպետք է գերազանցի -ը։
Օրինակներ
Մուտք | Ելք |
2 | 1 -> 2
1 -> 3
2 -> 3 |
3 | 1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB