시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 32 5 5 31.250%

문제

크기가 서로 다른 N개의 정사각형이 있다. 모든 정사각형의 한 변의 길이는 자연수이다. 이제 이 정사각형들을 아래와 같이 45도 기울여서 진열하려고 한다.

먼저, 첫 번째 정사각형 S1을 x축과 y축에 접하게 놓는다. 이럴 때 x축과 정사각형이 만나는 위치를 b1이라고 생각한다.

이어서 S2부터 정사각형을 하나씩 순서대로 놓는데, i번째 정사각형 Si를 놓을 때, bi는 bi-1보다는 커야 하되 다른 정사각형과 겹치지 않으면서 최대한 bi가 작게 놓아야 한다.

이렇게 정사각형들을 진열하고 난 뒤에, 우리는 y축 방향에서 보이는 정사각형들을 구하고 싶다. 정사각형 위의 임의의 한 점에서 y축 방향으로 반직선을 그렸을 때, 다른 정사각형들과 만나지 않는 반직선이 존재하는 경우 "y축 방향에서 보이는 정사각형"으로 정의한다.

입력

첫째 줄에 정사각형의 개수 N(1≤N≤100)이 주어진다. 이어서 둘째 줄에 각 정사각형의 한 변의 길이를 나타내는 N개의 자연수가 순서대로 주어진다. 각 정사각형의 길이는 1,000을 넘지 않는다.

출력

첫째 줄에 y축 방향에서 보이는 정사각형의 번호를 빈 칸을 사이에 두고 증가하는 순서로 출력한다.

예제 입력 1

4
3 5 1 4

예제 출력 1

1 2 4 
W3sicHJvYmxlbV9pZCI6IjExNjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjOWM0XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNzc0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YjRlNFx1Yzc0NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDQ1XHViM2M0IFx1YWUzMFx1YzZiOFx1YzVlY1x1YzExYyBcdWM5YzRcdWM1ZjRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPjxpbWcgd2lkdGg9XCIyMzZcIiBoZWlnaHQ9XCIxNDlcIiBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvMjAxMDAzXC9zcS5KUEdcIiBcLz48XC9wPlxyXG48cD5cdWJhM2NcdWM4MDAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFMxXHVjNzQ0IHhcdWNkOTVcdWFjZmMgeVx1Y2Q5NVx1YzVkMCBcdWM4MTFcdWQ1NThcdWFjOGMgXHViMTkzXHViMjk0XHViMmU0LiBcdWM3NzRcdWI3ZjQgXHViNTRjIHhcdWNkOTVcdWFjZmMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjljY1x1YjA5OFx1YjI5NCBcdWM3MDRcdWNlNThcdWI5N2MgYjFcdWM3NzRcdWI3N2NcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlx1Yzc3NFx1YzViNFx1YzExYyBTMlx1YmQ4MFx1ZDEzMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIxOTNcdWIyOTRcdWIzNzAsIGlcdWJjODhcdWM5ZjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFNpXHViOTdjIFx1YjE5M1x1Yzc0NCBcdWI1NGMsIGJpXHViMjk0IGJpLTFcdWJjZjRcdWIyZTRcdWIyOTQgXHVjZWU0XHVjNTdjIFx1ZDU1OFx1YjQxOCBcdWIyZTRcdWI5NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjIGJpXHVhYzAwIFx1Yzc5MVx1YWM4YyBcdWIxOTNcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NDQgXHVjOWM0XHVjNWY0XHVkNTU4XHVhY2UwIFx1YjA5YyBcdWI0YTRcdWM1ZDAsIFx1YzZiMFx1YjlhY1x1YjI5NCB5XHVjZDk1IFx1YmMyOVx1ZDVhNVx1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM3MDRcdWM3NTggXHVjNzg0XHVjNzU4XHVjNzU4IFx1ZDU1YyBcdWM4MTBcdWM1ZDBcdWMxMWMgeVx1Y2Q5NSBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViYzE4XHVjOWMxXHVjMTIwXHVjNzQ0IFx1YWRmOFx1YjgzOFx1Yzc0NCBcdWI1NGMsIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWFjZmMgXHViOWNjXHViMDk4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWJjMThcdWM5YzFcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMCAmcXVvdDt5XHVjZDk1IFx1YmMyOVx1ZDVhNVx1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1JnF1b3Q7XHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC4gPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEmbGU7TiZsZTsxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ1NWMgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMSwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgeVx1Y2Q5NSBcdWJjMjlcdWQ1YTVcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS2FkaiBTcXVhcmVzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGlzIHByb2JsZW0sIHlvdSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBTPHN1Yj4xPFwvc3ViPiwgUzxzdWI+MjxcL3N1Yj4sLi4uLCBTPHN1Yj5uPFwvc3ViPiBvZiBzcXVhcmVzIG9mIGRpZmZlcmVudCBzaXplcy4gVGhlIHNpZGVzIG9mIHRoZSBzcXVhcmVzIGFyZSBpbnRlZ2VyIG51bWJlcnMuIFdlIGxvY2F0ZSB0aGUgc3F1YXJlcyBvbiB0aGUgcG9zaXRpdmUgeCAtIHkgcXVhcnRlciBvZiB0aGUgcGxhbmUsIHN1Y2ggdGhhdCB0aGVpciBzaWRlcyBtYWtlIDQ1IGRlZ3JlZXMgd2l0aCB4IGFuZCB5IGF4ZXMsIGFuZCBvbmUgb2YgdGhlaXIgdmVydGljZXMgYXJlIG9uIHkgPSAwIGxpbmUuIExldCBiPHN1Yj5pPFwvc3ViPiBiZSB0aGUgeCBjb29yZGluYXRlcyBvZiB0aGUgYm90dG9tIHZlcnRleCBvZiBTPHN1Yj5pPFwvc3ViPiAuIEZpcnN0LCBwdXQgUzxzdWI+MTxcL3N1Yj4gc3VjaCB0aGF0IGl0cyBsZWZ0IHZlcnRleCBsaWVzIG9uIHggPSAwIC4gVGhlbiwgcHV0IFM8c3ViPmk8XC9zdWI+ICwgKGkgJmd0OyAxKSBhdCBtaW5pbXVtIGI8c3ViPmk8XC9zdWI+IHN1Y2ggdGhhdDxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPmI8c3ViPmk8XC9zdWI+ICZndDsgYjxzdWI+aS0xPFwvc3ViPiBhbmQ8XC9saT5cclxuXHQ8bGk+dGhlIGludGVyaW9yIG9mIFM8c3ViPmk8XC9zdWI+IGRvZXMgbm90IGhhdmUgaW50ZXJzZWN0aW9uIHdpdGggdGhlIGludGVyaW9yIG9mIFM8c3ViPjE8XC9zdWI+Li4uUzxzdWI+aS0xPFwvc3ViPiAuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvMjAxMDAzXC9zcS5KUEdcIiBzdHlsZT1cImhlaWdodDoxNDlweDsgd2lkdGg6MjM2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGdvYWwgaXMgdG8gZmluZCB3aGljaCBzcXVhcmVzIGFyZSB2aXNpYmxlLCBlaXRoZXIgZW50aXJlbHkgb3IgcGFydGlhbGx5LCB3aGVuIHZpZXdlZCBmcm9tIGFib3ZlLiBJbiB0aGUgZXhhbXBsZSBhYm92ZSwgdGhlIHNxdWFyZXMgUzxzdWI+MTxcL3N1Yj4gLCBTPHN1Yj4yPFwvc3ViPiAsIGFuZCBTPHN1Yj40PFwvc3ViPiBoYXZlIHRoaXMgcHJvcGVydHkuIE1vcmUgZm9ybWFsbHksIFM8c3ViPmk8XC9zdWI+IGlzIHZpc2libGUgZnJvbSBhYm92ZSBpZiBpdCBjb250YWlucyBhIHBvaW50IHAgLCBzdWNoIHRoYXQgbm8gc3F1YXJlIG90aGVyIHRoYW4gUzxzdWI+aTxcL3N1Yj4gaW50ZXJzZWN0IHRoZSB2ZXJ0aWNhbCBoYWxmLWxpbmUgZHJhd24gZnJvbSBwIHVwd2FyZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgaXMgbiAoMSAmbGU7Jm5ic3A7biAmbGU7Jm5ic3A7NTApICwgdGhlIG51bWJlciBvZiBzcXVhcmVzLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgbiBpbnRlZ2VycyBiZXR3ZWVuIDEgdG8gMzAsIHdoZXJlIHRoZSBpLXRoIG51bWJlciBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBzaWRlcyBvZiBTPHN1Yj5pPFwvc3ViPiAuIFRoZSBpbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIGEgemVybyBudW1iZXIuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgaW5kZXggb2YgdGhlIHZpc2libGUgc3F1YXJlcyBpbiB0aGUgaW5wdXQgc2VxdWVuY2UsIGluIGFzY2VuZGluZyBvcmRlciwgc2VwYXJhdGVkIGJ5IGJsYW5rIGNoYXJhY3RlcnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2006 I번

  • 문제를 번역한 사람: author5