시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 169 54 39 39.394%

문제

하노이의 탑이라는 유명한 문제가 있다.

하지만 이 문제는 너무 유명한 나머지 이제는 식상하다.

그러니까 이번엔 탑을 3개가 아닌 4개로 늘려서 생각해보자!

N개의 원판과 4개의 막대가 있을 때, 즉 보조 막대가 한 개가 아닌 두 개이면 몇 번 움직여서 모든 원판을 끝의 원판으로 옮길 수 있을까?

4개의 막대를 이용해서 N개의 원판을 모두 옮기기 위한 최소 이동 횟수를 구해보자.

입력

각 줄에 원판의 개수 N(1 ≤ N ≤ 1000)이 주어진다.

출력

테스트 케이스와 함께 답을 출력한다(단, 답은 64-bit 정수 타입(e.g. long long)으로 표현 가능하다).

예제 입력 1

1
3
5

예제 출력 1

Case 1: 1
Case 2: 5
Case 3: 13

힌트

사실 막대가 4개 이상인 하노이의 탑 문제는 Open Problem이므로 이 답이 최적이라는 보장은 없다 :(

W3sicHJvYmxlbV9pZCI6Ijk5NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NThcdWIxNzhcdWM3NzRcdWM3NTggXHViMTI0IFx1ZDBkMSIsImRlc2NyaXB0aW9uIjoiPHA+PGEgaHJlZj1cIlwvcHJvYmxlbVwvMTkxNFwiPlx1ZDU1OFx1YjE3OFx1Yzc3NFx1Yzc1OCBcdWQwZDE8XC9hPlx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWM3MjBcdWJhODVcdWQ1NWMgXHViYjM4XHVjODFjXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMTA4XHViYjM0IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNzc0XHVjODFjXHViMjk0IFx1YzJkZFx1YzBjMVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2VjXHViMmM4XHVhZTRjIFx1Yzc3NFx1YmM4OFx1YzVkNCBcdWQwZDFcdWM3NDQgM1x1YWMxY1x1YWMwMCBcdWM1NDRcdWIyY2MgNFx1YWMxY1x1Yjg1YyBcdWIyOThcdWI4MjRcdWMxMWMgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwITxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzZkMFx1ZDMxMFx1YWNmYyA0XHVhYzFjXHVjNzU4IFx1YjljOVx1YjMwMFx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWM5ODkgXHViY2Y0XHVjODcwIFx1YjljOVx1YjMwMFx1YWMwMCBcdWQ1NWMgXHVhYzFjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWI0NTAgXHVhYzFjXHVjNzc0XHViYTc0IFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNWVjXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWQzMTBcdWM3NDQgXHViMDVkXHVjNzU4IFx1YzZkMFx1ZDMxMFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzggXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+NFx1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjNmQwXHVkMzEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCZuYnNwO1x1YzYyZVx1YWUzMFx1YWUzMCBcdWM3MDRcdWQ1NWMmbmJzcDtcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5Jm5ic3A7XHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjNmQwXHVkMzEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEmbmJzcDsmbGU7Jm5ic3A7TiZuYnNwOyZsZTsmbmJzcDsxMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzY0MCBcdWQ1NjhcdWFlZDggXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNChcdWIyZTgsIFx1YjJmNVx1Yzc0MCA2NC1iaXQgXHVjODE1XHVjMjE4IFx1ZDBjMFx1Yzc4NShlLmcuIGxvbmcgbG9uZylcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNCkuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzBhY1x1YzJlNCZuYnNwOzxhIGhyZWY9XCJodHRwOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9Ub3dlcl9vZl9IYW5vaSNXaXRoX2ZvdXJfcGVnc19hbmRfYmV5b25kXCI+XHViOWM5XHViMzAwXHVhYzAwIDRcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc4Jm5ic3A7XHVkNTU4XHViMTc4XHVjNzc0XHVjNzU4IFx1ZDBkMSBcdWJiMzhcdWM4MWM8XC9hPlx1YjI5NCBPcGVuIFByb2JsZW1cdWM3NzRcdWJiYzBcdWI4NWMgXHVjNzc0IFx1YjJmNVx1Yzc3NCBcdWNkNWNcdWM4MDFcdWM3NzRcdWI3N2NcdWIyOTQgXHViY2Y0XHVjN2E1XHVjNzQwIFx1YzVjNlx1YjJlNCA6KDxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTk0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZvdXItVG93ZXIgVG93ZXJzIG9mIEhhbm9pIiwiZGVzY3JpcHRpb24iOiI8cD5SZWZlciB0byBwcm9ibGVtIHRocmVlIGZvciBhIGRlc2NyaXB0aW9uIG9mIHRoZSBjbGFzc2ljIHRocmVlLXRvd2VyIHZlcnNpb24gb2YgdGhlIFRvd2VycyBvZiBIYW5vaSBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCB3ZSBleHRlbmQgdGhlIFRvd2VycyBvZiBIYW5vaSB0byBoYXZlIGZvdXIgdG93ZXJzIGFuZCBhc2sgdGhlIHF1ZXN0aW9uICZsZHF1bztXaGF0IGFyZSB0aGUgZmV3ZXN0IG51bWJlciBvZiBtb3ZlcyB0byBzb2x2ZSB0aGUgVG93ZXJzIG9mIEhhbm9pIHByb2JsZW0gZm9yIGEgZ2l2ZW4gbiBpZiB3ZSBhbGxvdyBmb3VyIHRvd2VycyBpbnN0ZWFkIG9mIHRoZSB1c3VhbCB0aHJlZT8mcmRxdW87IFdlIGtlZXAgdGhlIHJ1bGVzIG9mIHRyeWluZyB0byBtb3ZlIG4gZGlza3MgZnJvbSBvbmUgc3BlY2lmaWVkIHBvc3QgdG8gYW5vdGhlciBhbmQgZG8gbm90IGFsbG93IGEgYmlnZ2VyIGRpc2sgdG8gYmUgcHV0IG9uIHRvcCBvZiBhIHNtYWxsZXIgb25lLiBXaGF0IGlzIG5ldyBmb3IgdGhpcyBwcm9ibGVtIGlzIHRvIGhhdmUgdHdvIHNwYXJlIHBvc3RzIGluc3RlYWQgb2YganVzdCBvbmUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0byBtb3ZlIDMgZGlza3MgZnJvbSBwb3N0IEEgdG8gcG9zdCBELCB3ZSBjYW4gbW92ZSBkaXNrIDEgZnJvbSBBIHRvIEIsIGRpc2sgMiBmcm9tIEEgdG8gQywgZGlzayAzIGZyb20gQSB0byBELCBkaXNrIDIgZnJvbSBDIHRvIEQsIGFuZCBkaXNrIDEgZnJvbSBCIHRvIEQsIG1ha2luZyBhIHRvdGFsIG9mIDUgbW92ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGJlIHBvc2l0aXZlIGludGVnZXJzIChuKSwgb25lIHBlciBsaW5lLCBub25lIGJlaW5nIGxhcmdlciB0aGFuIDEsMDAwLiBGb3IgZWFjaCB2YWx1ZSBvZiBuLCBjb21wdXRlIHRoZSBmZXdlc3QgbnVtYmVyIG9mIG1vdmVzIGZvciB0aGUgZm91ci10b3dlciBwcm9ibGVtLiBTdG9wIHByb2Nlc3NpbmcgYXQgdGhlIGVuZCBvZiB0aGUgZmlsZS4gKFRoZXJlIGlzIG5vIGVuZC1vZi1kYXRhIGZsYWcuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgZmV3ZXN0IG51bWJlciBvZiBtb3Zlcy4gRm9sbG93IHRoaXMgZm9ybWF0IGV4YWN0bHk6ICZsZHF1bztDYXNlJnJkcXVvOywgb25lIHNwYWNlLCB0aGUgY2FzZSBudW1iZXIsIGEgY29sb24gYW5kIG9uZSBzcGFjZSwgYW5kIHRoZSBhbnN3ZXIgZm9yIHRoYXQgY2FzZS4gWW91IG1heSBhc3N1bWUgdGhlIGFuc3dlciB3aWxsIGZpdCBpbiBhIDY0LWJpdCBpbnRlZ2VyIHR5cGUuIERvIG5vdCBwcmludCBhbnkgdHJhaWxpbmcgc3BhY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==