시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1073 509 356 51.371%

문제

각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치들의 총합을 최소화 하려고 한다.

예를 들어, 그림 1(a)에 있는 높이 2 인 포화이진트리를 살펴보자. 에지 옆에 있는 수는 그 에지의 가중치를 나타낸다. 이 경우에 대한 답이 그림 1(b)에 나타나 있다. 즉, 루트에서 모든 리프까지의 거리가 5 이고, 에지 가중치들의 총합은 이 경우에 가능한 최소값인 15 이다. 

그림 1. 에지 가중치를 증가시키는 예.

포화이진트리에 들어 있는 모든 에지들의 가중치가 주어졌을 때, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같게 하면서 에지 가중치들의 총합이 최소가 되도록 하는 프로그램을 작성하시오.

입력

입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가중치는 루트에서 가까운 레벨에 있는 것부터, 같은 레벨에 있는 경우는 왼쪽부터 오른쪽의 순서로 주어진다. 각 에지의 가중치는 1 이상 1,000 이하인 정수로 주어진다.

출력

출력은 표준출력을 사용한다. 에지들의 가중치를 증가시킨 다음에 얻어지는 트리에 있는 모든 에지들의 가중치들의 총합을 한 줄에 출력한다. 어떤 에지의 가중치는 경우에 따라 1,000 이상의 값으로 증가될 수도 있다는 점에 유의하시오.

예제 입력 1

2
2 2 2 1 1 3

예제 출력 1

15

예제 입력 2

1
1 1000

예제 출력 2

2000

예제 입력 3

3
1 2 1 3 2 4 1 1 1 1 1 1 1 1

예제 출력 3

27

예제 입력 4

2
1 1000 1 1 1000 1000

예제 출력 4

5001

힌트

W3sicHJvYmxlbV9pZCI6IjEzMzI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhYzAxIFx1YzVkMFx1YzljMFx1YzVkMCBcdWM1OTFcdWMyMThcdWM3NzggXHVhYzAwXHVjOTExXHVjZTU4XHVhYzAwIFx1YmQ4MFx1YzVlY1x1YjQxYyBcdWIxOTJcdWM3NzRcdWFjMDAga1x1Yzc3OCBcdWQzZWNcdWQ2NTRcdWM3NzRcdWM5YzRcdWQyYjhcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMTkyXHVjNzc0IGtcdWM3NzggXHVkM2VjXHVkNjU0XHVjNzc0XHVjOWM0XHVkMmI4XHViOWFjXHViMjk0IDI8c3VwPms8XC9zdXA+XHVhYzFjXHVjNzU4IFx1YjlhY1x1ZDUwNFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM1ZWMgKDI8c3VwPmsrMTxcL3N1cD4gJm1pbnVzOyAxKVx1YWMxY1x1Yzc1OCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVhYzAwXHVjOWM0XHViMmU0LiBcdWI4ZThcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjNWI0XHViNWE0IFx1YjlhY1x1ZDUwNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWRmOCBcdWI5YWNcdWQ1MDRcdWFlNGNcdWM5YzBcdWM3NTggXHVhY2JkXHViODVjXHVjMGMxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNWQwXHVjOWMwXHViNGU0XHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWIzNTRcdWQ1NWMgXHVhYzEyXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0LCBcdWM1YjRcdWI1YTQgXHVjNWQwXHVjOWMwXHViNGU0XHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWM5OWRcdWFjMDBcdWMyZGNcdWNmMWNcdWMxMWMgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWI5YWNcdWQ1MDRcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIFx1YWMxOVx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWFjZTAsIFx1YjYxMFx1ZDU1YyBcdWM1ZDBcdWM5YzAgXHVhYzAwXHVjOTExXHVjZTU4XHViNGU0XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCBcdWNkNWNcdWMxOGNcdWQ2NTQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhZGY4XHViOWJjIDEoYSlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjE5Mlx1Yzc3NCAyIFx1Yzc3OCBcdWQzZWNcdWQ2NTRcdWM3NzRcdWM5YzRcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLiBcdWM1ZDBcdWM5YzAgXHVjNjA2XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWIyOTQgXHVhZGY4IFx1YzVkMFx1YzljMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NzQgXHVhZGY4XHViOWJjIDEoYilcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWI4ZThcdWQyYjhcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YjlhY1x1ZDUwNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgNSBcdWM3NzRcdWFjZTAsIFx1YzVkMFx1YzljMCBcdWFjMDBcdWM5MTFcdWNlNThcdWI0ZTRcdWM3NTggXHVjZDFkXHVkNTY5XHVjNzQwIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc3OCAxNSBcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMzMyNVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODNweDsgd2lkdGg6NDUzcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAxLiBcdWM1ZDBcdWM5YzAgXHVhYzAwXHVjOTExXHVjZTU4XHViOTdjIFx1Yzk5ZFx1YWMwMFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWM2MDguPFwvcD5cclxuXHJcbjxwPlx1ZDNlY1x1ZDY1NFx1Yzc3NFx1YzljNFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM1ZDBcdWM5YzBcdWI0ZTRcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWM1ZDBcdWM5YzBcdWI0ZTRcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViOTdjIFx1Yzk5ZFx1YWMwMFx1YzJkY1x1Y2YxY1x1YzExYyBcdWI4ZThcdWQyYjhcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YjlhY1x1ZDUwNFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVhYzE5XHVhYzhjIFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM1ZDBcdWM5YzAgXHVhYzAwXHVjOTExXHVjZTU4XHViNGU0XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzZWNcdWQ2NTRcdWM3NzRcdWM5YzRcdWQyYjhcdWI5YWNcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IGsoMSAmbGU7IGsgJmxlOyAyMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNWQwXHVjOWMwXHViNGU0XHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVkMFx1YzljMFx1YjRlNFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWI4MDhcdWJjYThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWM4M1x1YmQ4MFx1ZDEzMCwgXHVhYzE5XHVjNzQwIFx1YjgwOFx1YmNhOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NTggXHVjMjFjXHVjMTFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzVkMFx1YzljMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgMSBcdWM3NzRcdWMwYzEgMSwwMDAgXHVjNzc0XHVkNTU4XHVjNzc4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YzVkMFx1YzljMFx1YjRlNFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGE4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM1YmJcdWM1YjRcdWM5YzBcdWIyOTQgXHVkMmI4XHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNWQwXHVjOWMwXHViNGU0XHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjRlNFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM1ZDBcdWM5YzBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWI1MzBcdWI3N2MgMSwwMDAgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWMxMlx1YzczY1x1Yjg1YyBcdWM5OWRcdWFjMDBcdWI0MjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWM4MTBcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEzMzI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmluYXJ5IFRyZWUiLCJkZXNjcmlwdGlvbiI6IjxwPldlIGFyZSBnaXZlbiBhIGZ1bGwgYmluYXJ5IHRyZWUgb2YgaGVpZ2h0IGssIHdoZXJlIGVhY2ggZWRnZSBoYXMgYSBwb3NpdGl2ZSB3ZWlnaHQuIFRoZSBmdWxsIGJpbmFyeSB0cmVlIG9mIGhlaWdodCBrIGhhcyAoMjxzdXA+aysxPFwvc3VwPiAmbWludXM7IDEpIG5vZGVzIGNvbnRhaW5pbmcgMjxzdXA+azxcL3N1cD4gbGVhdmVzLiBUaGUgZGlzdGFuY2UgZnJvbSB0aGUgcm9vdCB0byBhIGxlYWYgaXMgdGhlIHN1bSBvZiB3ZWlnaHRzIG9mIGFsbCB0aGUgZWRnZXMgb24gdGhlIHBhdGggZnJvbSB0aGUgcm9vdCB0byB0aGUgbGVhZi4gSW4gdGhpcyBwcm9ibGVtLCB3ZSB3b3VsZCBsaWtlIHRvIGluY3JlYXNlIHRoZSB3ZWlnaHRzIG9mIGNlcnRhaW4gZWRnZXMgc28gdGhhdCBhbGwgcm9vdC10by1sZWFmIHBhdGhzIGhhdmUgdGhlIHNhbWUgZGlzdGFuY2UgYW5kIGtlZXAgdGhlIHN1bSBvZiBhbGwgdGhlIGVkZ2Ugd2VpZ2h0cyBhcyBzbWFsbCBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGNvbnNpZGVyIGEgZnVsbCBiaW5hcnkgdHJlZSBvZiBoZWlnaHQgMiBpbiBGaWd1cmUgMShhKS4gQSBudW1iZXIgYWxvbmdzaWRlIGFuIGVkZ2UgaW5kaWNhdGVzIHRoZSB3ZWlnaHQgb2YgdGhlIGVkZ2UuIFRoZSBzb2x1dGlvbiBvZiB0aGlzIGluc3RhbmNlIGlzIHNob3duIGluIEZpZ3VyZSAxKGIpLiBUaGF0IGlzLCBhbGwgcm9vdC10by1sZWFmIHBhdGhzIGhhdmUgdGhlIHNhbWUgZGlzdGFuY2UgNSwgYW5kIHRoZSBzdW0gb2YgYWxsIHRoZSBlZGdlIHdlaWdodHMgaXMgMTUgd2hpY2ggaXMgdGhlIG1pbmltdW0gcG9zc2libGUgdmFsdWUgaW4gdGhpcyBjYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTMzMjVcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgzcHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo0NTNweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS4gSWxsdXN0cmF0aW9uIG9mIGluY3JlYXNpbmcgZWRnZSB3ZWlnaHRzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgd2VpZ2h0cyBvZiBhbGwgZWRnZXMgaW4gYSBmdWxsIGJpbmFyeSB0cmVlLCB5b3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGluY3JlYXNlcyB0aGUgd2VpZ2h0cyBvZiBjZXJ0YWluIGVkZ2VzIHNvIHRoYXQgYWxsIHJvb3QtdG8tbGVhZiBwYXRocyBoYXZlIHRoZSBzYW1lIGRpc3RhbmNlIGFuZCB0aGUgdG90YWwgZWRnZSB3ZWlnaHRzIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlciBrICgxICZsZTsgayAmbGU7IDIwKSB3aGljaCByZXByZXNlbnRzIHRoZSBoZWlnaHQgb2YgYSBmdWxsIGJpbmFyeSB0cmVlLiBJbiB0aGUgc2Vjb25kIGxpbmUsIGFsbCB0aGUgZWRnZSB3ZWlnaHRzIGFyZSBnaXZlbi4gVGhlIGVkZ2Ugd2VpZ2h0cyBhcmUgZ2l2ZW4gYnkgbGV2ZWwtYnktbGV2ZWwsIGFuZCBsZWZ0LXRvLXJpZ2h0IG9yZGVyIGluIGEgbGV2ZWwuIFRoZSB3ZWlnaHQgb2YgYW55IGVkZ2UgaXMgYmV0d2VlbiAxIGFuZCAxLDAwMCwgaW5jbHVzaXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgd2hpY2ggY29udGFpbnMgdGhlIHRvdGFsIGVkZ2Ugd2VpZ2h0cyBvZiB0aGUgdHJlZSBvYnRhaW5lZCBhZnRlciBpbmNyZWFzaW5nIGVkZ2Ugd2VpZ2h0cy4gTm90ZSB0aGF0IHRoZSB3ZWlnaHQgb2YgYSBjZXJ0YWluIGVkZ2UgY2FuIGJlIGluY3JlYXNlZCB0byBhIHZhbHVlIGxhcmdlciB0aGFuIDEsMDAwIGluIHNvbWUgY2FzZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d