시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1611 998 886 61.872%

문제

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만드려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

  1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
  2. 정사각형의 중심에 점을 하나 추가한다.

첫 단계에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때 까지의 모습이다.

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다. N 단계를 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

출력

첫째 줄에 N 단계를 거친 후에 점의 수를 출력한다.

예제 입력 1

1

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjI5MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5MTFcdWM1NTkgXHVjNzc0XHViM2Q5IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWQ1NjhcdWFlZDggU0ZcdWM2MDFcdWQ2NTRcdWI5N2MgXHVjYzBkXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzYwMVx1ZDY1NFx1YjI5NCBcdWM2NzhcdWFjYzQgXHVjOWMwXHVkNjE1XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHVjMmU0XHVjODFjXHViODVjIFx1YzZiMFx1YzhmY1x1YzEyMFx1Yzc0NCBcdWQwYzBcdWFjZTAgXHVjNjc4XHVhY2M0IFx1ZDU4OVx1YzEzMVx1YzVkMCBcdWFjMDBcdWMxMWMgXHVjZDJjXHVjNjAxXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YWRmOFx1Yjc5OFx1ZDUzZFx1YzczY1x1Yjg1YyBDR1x1Y2M5OFx1YjlhY1x1Yjk3YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2NzhcdWFjYzQgXHVjOWMwXHVkNjE1XHVjNzQwIFx1YzkxMVx1YzU1OSBcdWM3NzRcdWIzZDkgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzgxMCA0XHVhYzFjXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1ZDZjNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNjZDBcdWMxMWMgXHVjOWMwXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzAxIFx1YmNjMFx1Yzc1OCBcdWM5MTFcdWM1NTlcdWM1ZDAgXHVjODEwXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM1ZDAgXHVjODEwXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjY2FiIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YWM3MFx1Y2U1OFx1YmE3NCBcdWNkMWQgNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjMGM4XHViODVjIFx1YzBkZFx1YWUzNFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMgXHVhZTRjXHVjOWMwIFx1YWNjNFx1YzE4ZFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjZDFkIDJcdWJjODggXHVhYzcwXHVjY2U0XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzBcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21tLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI3MXB4OyB3aWR0aDo3MTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzgxMFx1Yzc0MCBcdWQ1NWMgXHVhYzFjIFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGNcdWM1NThcdWIyZTQuIFx1YmE1NFx1YmFhOFx1YjlhYyBcdWMxOGNcdWJhYThcdWI3YzlcdWM3NDQgXHVjOTA0XHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM5MTFcdWJjZjVcdWQ1NThcdWIyOTQgXHVjODEwXHVjNzQ0IFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjODAwXHVjN2E1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gTiBcdWIyZThcdWFjYzRcdWI5N2MgXHVhYzcwXHVjZTVjIFx1ZDZjNCBcdWM4MTAgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTUpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOIFx1YjJlOFx1YWNjNFx1Yjk3YyBcdWFjNzBcdWNlNWMgXHVkNmM0XHVjNWQwIFx1YzgxMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTEFOSU5BIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBmaWxtaW5nIGEgbW92aWUgYWRhcHRhdGlvbiBvZiB0aGUgcG9wdWxhciBTRiBub3ZlbCAmcXVvdDtDaGlja3MgaW4gc3BhY2UgMTMmcXVvdDsuIFRoZSBzY3JpcHQgcmVxdWlyZXMgdGhlbSB0byBwcmVzZW50IGEgbG90IG9mIGRpZmZlcmVudCB3b3JsZHMgc28gdGhleSBkZWNpZGVkIHRvIGZpbG0gdGhlIGVudGlyZSBtb3ZpZSBpbiBmcm9udCBvZiBhIGdyZWVuIHNjcmVlbiBhbmQgYWRkIENHSSBiYWNrZ3JvdW5kcyBsYXRlci4gTWlya28gaGVhcmQgdGhhdCB0aGUgYmVzdCB3YXkgdG8gZ2VuZXJhdGUgYXJ0aWZpY2lhbCB0ZXJyYWluIGlzIHRvIHVzZSBtaWRwb2ludCBkaXNwbGFjZW1lbnQgYWxnb3JpdGhtLjxcL3A+XHJcblxyXG48cD5UbyBzdGFydCB0aGUgYWxnb3JpdGhtLCBNaXJrbyBzZWxlY3RzIDQgcG9pbnRzIGZvcm1pbmcgYSBwZXJmZWN0IHNxdWFyZS4gSGUgdGhlbiBwZXJmb3JtcyB0aGUgZm9sbG93aW5nIHN0ZXBzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPk9uIGVhY2ggc2lkZSBvZiB0aGUgc3F1YXJlLCBoZSBhZGRzIGEgbmV3IHBvaW50IGluIHRoZSBleGFjdCBtaWRkbGUgb2YgdGhlIHNpZGUuIFRoZSBoZWlnaHQgb2YgdGhpcyBuZXcgcG9pbnQgaXMgdGhlIGF2ZXJhZ2UgaGVpZ2h0IG9mIHRoZSB0d28gcG9pbnRzIG9uIHRoYXQgc2lkZS48XC9saT5cclxuXHQ8bGk+SW4gdGhlIGV4YWN0IGNlbnRlciBvZiB0aGUgc3F1YXJlIGhlIGFkZHMgYSBuZXcgcG9pbnQgd2hvc2UgaGVpZ2h0IGlzIHRoZSBhdmVyYWdlIGhlaWdodCBvZiBhbGwgNCBzcXVhcmUgdmVydGljZXMsIHBsdXMgYSBzbWFsbCByYW5kb20gdmFsdWUuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QWZ0ZXIgdGhvc2UgdHdvIHN0ZXBzIGFyZSBwZXJmb3JtZWQsIGhlIG5vdyBoYXMgNCBuZXcgc3F1YXJlcy4gSGUgcGVyZm9ybXMgdGhlIHNhbWUgc3RlcHMgb24gdGhlIG5ld2x5IGNyZWF0ZWQgc3F1YXJlcyBhZ2FpbiBhbmQgYWdhaW4gdW50aWwgaGUgaXMgcGxlYXNlZCB3aXRoIHRoZSByZXN1bHRzLiBUaGUgZm9sbG93aW5nIGRpYWdyYW0gaWxsdXN0cmF0ZXMgMiBpdGVyYXRpb25zIG9mIHRoZSBhbGdvcml0aG0uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjcxcHg7IHdpZHRoOjcxNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1pcmtvIG5vdGljZWQgdGhhdCBzb21lIG9mIHRoZSBwb2ludHMgYmVsb25nIHRvIG1vcmUgdGhhbiBvbmUgc3F1YXJlLiBJbiBvcmRlciB0byBkZWNyZWFzZSBtZW1vcnkgY29uc3VtcHRpb24sIGhlIHN0b3JlcyBjYWxjdWxhdGVzIGFuZCBzdG9yZXMgc3VjaCBwb2ludHMgb25seSBvbmNlLiBIZSBub3cgd29uZGVycyBob3cgbWFueSBwb2ludHMgaW4gdG90YWwgd2lsbCBoZSBuZWVkIHRvIHN0b3JlIGluIG1lbW9yeSBhZnRlciBOIGl0ZXJhdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDE1KSwgbnVtYmVyIG9mIGl0ZXJhdGlvbnM8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIG51bWJlciwgdGhlIG51bWJlciBvZiBwb2ludHMgc3RvcmVkIGFmdGVyIE4gaXRlcmF0aW9ucy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #4 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: corea