시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB114473054.545%

문제

기존 하노이는 모든 학생이 알 것이라 판단하여 설명을 생략한다.

우리는 하노이의 이동을 알파벳 두 글자로 표현할 수 있는데, 예를 들어 A번 폴에서 B번 폴로 가장 위에 있는 디스크를 옮기는 것을 AB라고 표현한다고 한다. 변형 하노이는 문제 조건에 만족하도록 옮기는 것이다. 즉, 자기 임의적으로 디스크를 옮길 수 없다. 디스크를 옮기는 조건은 아래와 같다.

  • 동일한 디스크를 연속으로 두 번 옮길 수 없다.
  • 총 옮길 수 있는 경우는 6가지(AB, AC, BA, BC, CA, CB)이고 이 여섯 가지의 옮기는 경우의 우선순위가 주어진다. 즉, 1번 조건을 만족하는 옮길 수 있는 경우가 두 가지 이상 존재하면 그 중 우선순위가 높은 것을 택해야 한다.

문제는 위 조건에 따라 판을 옮길 때 모든 디스크를 B폴이나 C폴 중 한 폴로 모두 옮겼을 때 횟수가 몇 번인지 구하는 것이다. (위 조건을 만족하도록 옮기다 보면 항상 어느 폴로 모두 옮겨진다고 한다.)

입력

첫 줄에는 디스크의 수 N(1 ≤ N ≤ 30)과 주어진다. 두 번째 줄에는 6개의 이동 경우에 대해 우선순위가 높은 것부터 차례대로 주어진다.

출력

첫 줄에 이동횟수를 출력한다. 답은 10^18보다 작다고 가정한다.

예제 입력 1

2
AB BA CA BC CB AC

예제 출력 1

5

힌트

1. 1번 디스크를 A->B로 옮긴다. 2. 2번 디스크를 A->C로 옮긴다. 3. 1번 디스크를 B->A로 옮긴다. 4. 2번 디스크를 C->B로 옮긴다. 5. 1번 디스크를 A->B로 옮기면 끝나게 된다.

W3sicHJvYmxlbV9pZCI6IjExNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYzBcdWQ2MTUgXHVkNTU4XHViMTc4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIGhlaWdodD1cIjg4XCIgc3JjPVwiXC91cGxvYWRcLzIwMTAwM1wvaGFoYWguanBnXCIgd2lkdGg9XCIyNzhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZTMwXHVjODc0IFx1ZDU1OFx1YjE3OFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzU0YyBcdWFjODNcdWM3NzRcdWI3N2MgXHVkMzEwXHViMmU4XHVkNTU4XHVjNWVjIFx1YzEyNFx1YmE4NVx1Yzc0NCBcdWMwZGRcdWI3YjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YjI5NCBcdWQ1NThcdWIxNzhcdWM3NzRcdWM3NTggXHVjNzc0XHViM2Q5XHVjNzQ0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWI0NTAgXHVhZTAwXHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IEFcdWJjODggXHVkM2Y0XHVjNWQwXHVjMTFjIEJcdWJjODggXHVkM2Y0XHViODVjIFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWM2MmVcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzQ0IEFCXHViNzdjXHVhY2UwIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmNjMFx1ZDYxNSBcdWQ1NThcdWIxNzhcdWM3NzRcdWIyOTQgXHViYjM4XHVjODFjIFx1Yzg3MFx1YWM3NFx1YzVkMCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVjNjJlXHVhZTMwXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWM3OTBcdWFlMzAgXHVjNzg0XHVjNzU4XHVjODAxXHVjNzNjXHViODVjIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWM2MmVcdWFlMzggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViNTE0XHVjMmE0XHVkMDZjXHViOTdjIFx1YzYyZVx1YWUzMFx1YjI5NCBcdWM4NzBcdWFjNzRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWIzZDlcdWM3N2NcdWQ1NWMgXHViNTE0XHVjMmE0XHVkMDZjXHViOTdjIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWI0NTAgXHViYzg4IFx1YzYyZVx1YWUzOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWNkMWQgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IDZcdWFjMDBcdWM5YzAoQUIsIEFDLCBCQSwgQkMsIENBLCBDQilcdWM3NzRcdWFjZTAgXHVjNzc0IFx1YzVlY1x1YzEyZiBcdWFjMDBcdWM5YzBcdWM3NTggXHVjNjJlXHVhZTMwXHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWM2YjBcdWMxMjBcdWMyMWNcdWM3MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5ODksIDFcdWJjODggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM2MmVcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM3NzRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0IFx1YWRmOCBcdWM5MTEgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHVhYzAwIFx1YjE5Mlx1Yzc0MCBcdWFjODNcdWM3NDQgXHVkMGRkXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjNzA0IFx1Yzg3MFx1YWM3NFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkMzEwXHVjNzQ0IFx1YzYyZVx1YWUzOCBcdWI1NGMgXHViYWE4XHViNGUwIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBCXHVkM2Y0XHVjNzc0XHViMDk4IENcdWQzZjQgXHVjOTExIFx1ZDU1YyBcdWQzZjRcdWI4NWMgXHViYWE4XHViNDUwIFx1YzYyZVx1YWNiY1x1Yzc0NCBcdWI1NGMgXHVkNjlmXHVjMjE4XHVhYzAwIFx1YmE4NyBcdWJjODhcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gKFx1YzcwNCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YzYyZVx1YWUzMFx1YjJlNCBcdWJjZjRcdWJhNzQgXHVkNTZkXHVjMGMxIFx1YzViNFx1YjI5MCBcdWQzZjRcdWI4NWMgXHViYWE4XHViNDUwIFx1YzYyZVx1YWNhOFx1YzljNFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI1MTRcdWMyYTRcdWQwNmNcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAzMClcdWFjZmMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCA2XHVhYzFjXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzZiMFx1YzEyMFx1YzIxY1x1YzcwNFx1YWMwMCBcdWIxOTJcdWM3NDAgXHVhYzgzXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM3NzRcdWIzZDlcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NDAgMTBeMThcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MS4gMVx1YmM4OCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgQS0mZ3Q7Qlx1Yjg1YyBcdWM2MmVcdWFlMzRcdWIyZTQuIDIuIDJcdWJjODggXHViNTE0XHVjMmE0XHVkMDZjXHViOTdjIEEtJmd0O0NcdWI4NWMgXHVjNjJlXHVhZTM0XHViMmU0LiAzLiAxXHViYzg4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBCLSZndDtBXHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC4gNC4gMlx1YmM4OCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgQy0mZ3Q7Qlx1Yjg1YyBcdWM2MmVcdWFlMzRcdWIyZTQuIDUuIDFcdWJjODggXHViNTE0XHVjMmE0XHVkMDZjXHViOTdjIEEtJmd0O0JcdWI4NWMgXHVjNjJlXHVhZTMwXHViYTc0IFx1YjA1ZFx1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMTU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGFub2kgVG93ZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgJmxkcXVvO0hhbm9pIFRvd2VycyZyZHF1bzsgcHV6emxlIGNvbnNpc3RzIG9mIHRocmVlIHBlZ3MgKHRoYXQgd2Ugd2lsbCBuYW1lIEEsIEIsIGFuZCBDKSB3aXRoIG4gZGlza3Mgb2YgZGlcdWZiMDBlcmVudCBkaWFtZXRlcnMgc3RhY2tlZCBvbnRvIHRoZSBwZWdzLiBJbml0aWFsbHkgYWxsIGRpc2tzIGFyZSBzdGFja2VkIG9udG8gcGVnIEEgd2l0aCB0aGUgc21hbGxlc3QgZGlzayBhdCB0aGUgdG9wIGFuZCB0aGUgbGFyZ2VzdCBvbmUgYXQgdGhlIGJvdHRvbSwgc28gdGhhdCB0aGV5IGZvcm0gYSBjb25pY2FsIHNoYXBlIG9uIHBlZyBBLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hhbm9pKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzNXB4OyB3aWR0aDo0MDZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BIHZhbGlkIG1vdmUgaW4gdGhlIHB1enpsZSBpcyBtb3Zpbmcgb25lIGRpc2sgZnJvbSB0aGUgdG9wIG9mIG9uZSAoc291cmNlKSBwZWcgdG8gdGhlIHRvcCBvZiB0aGUgb3RoZXIgKGRlc3RpbmF0aW9uKSBwZWcsIHdpdGggYSBjb25zdHJhaW50IHRoYXQgYSBkaXNrIGNhbiBiZSBwbGFjZWQgb25seSBvbnRvIGFuIGVtcHR5IGRlc3RpbmF0aW9uIHBlZyBvciBvbnRvIGEgZGlzayBvZiBhIGxhcmdlciBkaWFtZXRlci4gV2UgZGVub3RlIGEgbW92ZSB3aXRoIHR3byBjYXBpdGFsIGxldHRlcnMgJm1kYXNoOyB0aGUgXHVmYjAxcnN0IGxldHRlciBkZW5vdGVzIHRoZSBzb3VyY2UgZGlzaywgYW5kIHRoZSBzZWNvbmQgbGV0dGVyIGRlbm90ZXMgdGhlIGRlc3RpbmF0aW9uIGRpc2suIEZvciBleGFtcGxlLCBBQiBpcyBhIG1vdmUgZnJvbSBkaXNrIEEgdG8gZGlzayBCLjxcL3A+XHJcblxyXG48cD5UaGUgcHV6emxlIGlzIGNvbnNpZGVyZWQgc29sdmVkIHdoZW4gYWxsIHRoZSBkaXNrcyBhcmUgc3RhY2tlZCBvbnRvIGVpdGhlciBwZWcgQiAod2l0aCBwZWdzIEEgYW5kIEMgZW1wdHkpIG9yIG9udG8gcGVnIEMgKHdpdGggcGVncyBBIGFuZCBCIGVtcHR5KS4gV2Ugd2lsbCBzb2x2ZSB0aGlzIHB1enpsZSB3aXRoIHRoZSBmb2xsb3dpbmcgYWxnb3JpdGhtLjxcL3A+XHJcblxyXG48cD5BbGwgc2l4IHBvdGVudGlhbCBtb3ZlcyBpbiB0aGUgZ2FtZSAoQUIsIEFDLCBCQSwgQkMsIENBLCBhbmQgQ0IpIGFyZSBhcnJhbmdlZCBpbnRvIGEgbGlzdC4gVGhlIG9yZGVyIG9mIG1vdmVzIGluIHRoaXMgbGlzdCBkZVx1ZmIwMW5lcyBvdXIgc3RyYXRlZ3kuIFdlIGFsd2F5cyBtYWtlIHRoZSBcdWZiMDFyc3QgdmFsaWQgbW92ZSBmcm9tIHRoaXMgbGlzdCB3aXRoIGFuIGFkZGl0aW9uYWwgY29uc3RyYWludCB0aGF0IHdlIG5ldmVyIG1vdmUgdGhlIHNhbWUgZGlzayB0d2ljZSBpbiBhIHJvdy48XC9wPlxyXG5cclxuPHA+SXQgY2FuIGJlIHByb3ZlbiB0aGF0IHRoaXMgYWxnb3JpdGhtIGFsd2F5cyBzb2x2ZXMgdGhlIHB1enpsZS4gWW91ciBwcm9ibGVtIGlzIHRvIFx1ZmIwMW5kIHRoZSBudW1iZXIgb2YgbW92ZXMgaXQgdGFrZXMgZm9yIHRoaXMgYWxnb3JpdGhtIHRvIHNvbHZlIHRoZSBwdXp6bGUgdXNpbmcgYSBnaXZlbiBzdHJhdGVneS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyB0d28gbGluZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBjb25zaXN0cyBvZiBhIHNpbmdsZSBpbnRlZ2VyIG51bWJlciBuICgxICZsZTsgbiAmbGU7IDMwKSAmbmRhc2g7IHRoZSBudW1iZXIgb2YgZGlza3MgaW4gdGhlIHB1enpsZS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGRlc2NyaXB0aW9ucyBvZiBzaXggbW92ZXMgc2VwYXJhdGVkIGJ5IHNwYWNlcyAmbWRhc2g7IHRoZSBzdHJhdGVneSB0aGF0IGlzIHVzZWQgdG8gc29sdmUgdGhlIHB1enpsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSB0byB0aGUgb3V0cHV0IFx1ZmIwMWxlIHRoZSBudW1iZXIgb2YgbW92ZXMgaXQgdGFrZXMgdG8gc29sdmUgdGhlIHB1enpsZS4gVGhpcyBudW1iZXIgd2lsbCBub3QgZXhjZWVkIDEwPHN1cD4xODxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2007 H번

  • 문제를 번역한 사람: author5