문제
상근이는 어렸을 때부터 항상 프로그래밍 캠프를 개최하고 싶어했다. 캠프를 개최할 때 가장 필요한 것은 장소이다. 지금까지 많은 사람들이 장소의 벽에 가로막혀 캠프를 주최할 수가 없었다.
상근이는 프로그래밍 캠프 전용 부지를 구입해 모든 사람의 장소 문제를 해결하려고 한다. 서울의 땅값은 매년 기하급수적으로 비싸진다. 예를 들어, 땅 i의 현재 땅값이 Li 인 경우, t년이 지난 후 땅값은 2×(Li )t 가 된다. 모든 땅값은 서로 다르다. 상근이는 일년에 땅 하나만 구입할 수 있다.
상근이가 구입하려고 하는 땅의 현재 가격이 주어졌을 때, 모든 땅을 구입하는데 드는 비용의 최솟값을 구하는 프로그램을 작성하시오. 상근이는 돈을 5×106 억원 가지고 있고, 1년이 지난 후부터 땅을 구입하기 시작한다. (누가 돈을 훔쳐가거나, 다른데에 돈을 쓰거나, 돈을 벌거나 하는 상황은 발생하지 않는다)
예를 들어, 땅의 가격이 7억, 2억, 10억일 때, 각 땅을 연속한 해에 구입하는데 필요한 금액은 다음과 같다.
(2×7) + (2×22 ) + (2×103 ) = 2022억
출력
각 테스트 케이스마다 모든 땅을 구입하는데 필요한 최소 금액을 출력한다. 만약, 돈이 부족해서 땅을 모두 구입하지 못하는 경우에는 "Too expensive"를 출력한다. (단위: 억)
예제 출력 1
복사
134
17744
Too expensive
W3sicHJvYmxlbV9pZCI6Ijk0MTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjIFx1YzgwNFx1YzZhOSBcdWJkODBcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1YjRcdWI4MzhcdWM3NDQgXHViNTRjXHViZDgwXHVkMTMwIFx1ZDU2ZFx1YzBjMSBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjZWEwXHVkNTA0XHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1ODhcdWIyZTQuIFx1Y2VhMFx1ZDUwNFx1Yjk3YyBcdWFjMWNcdWNkNWNcdWQ1NjAgXHViNTRjIFx1YWMwMFx1YzdhNSBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhYzgzXHVjNzQwIFx1YzdhNVx1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1YjljZVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjN2E1XHVjMThjXHVjNzU4IFx1YmNiZFx1YzVkMCBcdWFjMDBcdWI4NWNcdWI5YzlcdWQ2MDAgXHVjZWEwXHVkNTA0XHViOTdjIFx1YzhmY1x1Y2Q1Y1x1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1Y2VhMFx1ZDUwNCBcdWM4MDRcdWM2YTkgXHViZDgwXHVjOWMwXHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU3NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzdhNVx1YzE4YyBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMTFjXHVjNmI4XHVjNzU4IFx1YjU0NVx1YWMxMlx1Yzc0MCBcdWI5ZTRcdWIxNDQgXHVhZTMwXHVkNTU4XHVhZTA5XHVjMjE4XHVjODAxXHVjNzNjXHViODVjIFx1YmU0NFx1YzJmOFx1YzljNFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViNTQ1IGlcdWM3NTggXHVkNjA0XHVjN2FjIFx1YjU0NVx1YWMxMlx1Yzc3NCBMPHN1Yj5pPFwvc3ViPlx1Yzc3OCBcdWFjYmRcdWM2YjAsIHRcdWIxNDRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDZjNCBcdWI1NDVcdWFjMTJcdWM3NDAgMiZ0aW1lczsoTDxzdWI+aTxcL3N1Yj4pPHN1cD50PFwvc3VwPlx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWI1NDVcdWFjMTJcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3Y1x1YjE0NFx1YzVkMCBcdWI1NDUgXHVkNTU4XHViMDk4XHViOWNjIFx1YWQ2Y1x1Yzc4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZDZjXHVjNzg1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWI1NDVcdWM3NTggXHVkNjA0XHVjN2FjIFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViNTQ1XHVjNzQ0IFx1YWQ2Y1x1Yzc4NVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjNjOFx1Yzc0NCA1JnRpbWVzOzEwPHN1cD42PFwvc3VwPiBcdWM1YjVcdWM2ZDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgMVx1YjE0NFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHViZDgwXHVkMTMwIFx1YjU0NVx1Yzc0NCBcdWFkNmNcdWM3ODVcdWQ1NThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiAoXHViMjA0XHVhYzAwIFx1YjNjOFx1Yzc0NCBcdWQ2ZDRcdWNjZDBcdWFjMDBcdWFjNzBcdWIwOTgsIFx1YjJlNFx1Yjk3OFx1YjM3MFx1YzVkMCBcdWIzYzhcdWM3NDQgXHVjNGYwXHVhYzcwXHViMDk4LCBcdWIzYzhcdWM3NDQgXHViYzhjXHVhYzcwXHViMDk4IFx1ZDU1OFx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NDAgXHViYzFjXHVjMGRkXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViNTQ1XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc3NCA3XHVjNWI1LCAyXHVjNWI1LCAxMFx1YzViNVx1Yzc3YyBcdWI1NGMsIFx1YWMwMSZuYnNwO1x1YjU0NVx1Yzc0NCBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHVkNTc0XHVjNWQwIFx1YWQ2Y1x1Yzc4NVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhZTA4XHVjNTYxXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPigyJnRpbWVzOzcpICsgKDImdGltZXM7MjxzdXA+MjxcL3N1cD4pICsgKDImdGltZXM7MTA8c3VwPjM8XC9zdXA+KSA9IDIwMjJcdWM1YjU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoMSAmbGU7IFQgJmxlOyAxMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI1NDVcdWFjMTIgTDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCAwXHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjgyNFx1YjI5NCBcdWI1NDVcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDQwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWIyZThcdWM3MDRcdWIyOTQgXHVjNWI1XHViMmU4XHVjNzA0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YmFhOFx1YjRlMCBcdWI1NDVcdWM3NDQgXHVhZDZjXHVjNzg1XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVhZTA4XHVjNTYxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWIzYzhcdWM3NzQgXHViZDgwXHVjODcxXHVkNTc0XHVjMTFjIFx1YjU0NVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhZDZjXHVjNzg1XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7VG9vIGV4cGVuc2l2ZSZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWIyZThcdWM3MDQ6IFx1YzViNSk8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NDE0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQSBNaW5pbXVtIExhbmQgUHJpY2UiLCJkZXNjcmlwdGlvbiI6IjxwPk1hbmFnZXIgb2YgQUNNLUlDUEMgVGhhaWxhbmQgQ29udGVzdCBDb3VuY2lsIGlzIHBsYW5uaW5nIHRvIGJ1eSBsYW5kcyBpbiBQaHVrZXQgdG8gYnVpbGQgdGhlIG9mZmljZSBidWlsZGluZyBmb3IgbmF0aW9uYWwgcHJvZ3JhbW1pbmcgc2tpbGwgY2FtcCBhbmQgcHJvZ3JhbW1pbmcgY29udGVzdCB0aGF0IHdpbGwgYmUgaGVsZCBvbiBQaHVrZXQgcmVndWxhcmx5IGluIHRoZSBmdXR1cmUuIFRoZSBsYW5kIHByaWNlIGluIFBodWtldCBpcyBiZWNvbWluZyBtb3JlIGV4cGVuc2l2ZSBpbiBldmVyeSB5ZWFyLiBUaGUgcHJpY2UgaW5jcmVhc2VzIGluIHRoZSBleHBvbmVudGlhbCBncm93dGggY3VydmVzIGJ5IGEgZmFjdG9yIG9mIHllYXIuIElmIHRoZSBsYW5kIGkgd2hvc2UgaW5pdGlhbCBjb3N0IGlzIEw8c3ViPmk8XC9zdWI+IGJvdWdodCBpbiB0IHllYXJzIGZyb20gbm93LCBpdHMgcHJpY2Ugd2lsbCBiZSAyeCAoTDxzdWI+aTxcL3N1Yj4pPHN1cD50PFwvc3VwPi4gQWxsIGxhbmQgcHJpY2VzIGFyZSBkaWZmZXJlbnQuIEFDTS1JQ1BDIGNhbiBidXkgb25seSBvbmUgbGFuZCBwZXIgeWVhci4gWW91IGhhdmUgdG8gaGVscCB0aGUgbWFuYWdlciB0byBidXkgdGhlIGxhbmRzIGF0IGxvd2VzdCBwcmljZSB3aXRoaW4gdGhlIGJ1ZGdldCBvZiA1LDAwMCBiaWxsaW9ucyBiYWh0ICg1eDEwPHN1cD42PFwvc3VwPiBtaWxsaW9ucykuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkZvciBleGFtcGxlLCBpZiB3ZSB3YW50IHRvIGJ1eSAzIGxhbmRzIHdpdGggY29zdHMgNywgMiBhbmQgMTAgaW4gdGhyZWUgY29uc2VjdXRpdmUgeWVhcnMsIHRoZSB0b3RhbCBwcmljZSB3aWxsIGJlIGNhbGN1bGF0ZWQgYXMgZm9sbG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD4oMnggNykgKyAoMnggMjxzdXA+MjxcL3N1cD4pICsgKDIgeCAxMDxzdXA+MzxcL3N1cD4pID0gMjAyMiBtaWxsaW9ucyBiYWh0PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIFQgKDEgJmx0Oz0gVCAmbHQ7PSAxMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgaW50ZWdlciBMPHN1Yj5pPFwvc3ViPiB3aGljaCBpcyB0aGUgY29zdCBvZiBsYW5kIGluIG1pbGxpb24gYmFodC4gVGhlcmUgYXJlIGxlc3MgdGhhbiA0MCBsYW5kcyBpbiBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgY29udGFpbnMgMCAoemVybykgaW5kaWNhdGVzIHRoZSBlbmQgb2YgZWFjaCB0ZXN0IGNhc2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvdXQgdGhlIG1pbmltdW0gcHJpY2UgZm9yIHB1cmNoYXNpbmcgYWxsIGxhbmRzLiBJZiB0aGUgdG90YWwgcHJpY2UgZXhjZWVkcyB0aGUgYnVkZ2V0ICg1LDAwMCBiaWxsaW9ucyBiYWh0KSwgcHJpbnQgb3V0ICZsZHF1bztUb28gZXhwZW5zaXZlJnJkcXVvOy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d