시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB120141422.222%

문제

크기가 서로 다른 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+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIGhlaWdodD1cIjE0OVwiIHNyYz1cIlwvdXBsb2FkXC8yMDEwMDNcL3NxLkpQR1wiIHdpZHRoPVwiMjM2XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgUzFcdWM3NDQgeFx1Y2Q5NVx1YWNmYyB5XHVjZDk1XHVjNWQwIFx1YzgxMVx1ZDU1OFx1YWM4YyBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjdmNCBcdWI1NGMgeFx1Y2Q5NVx1YWNmYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViOWNjXHViMDk4XHViMjk0IFx1YzcwNFx1Y2U1OFx1Yjk3YyBiMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzExYyBTMlx1YmQ4MFx1ZDEzMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIxOTNcdWIyOTRcdWIzNzAsIGlcdWJjODhcdWM5ZjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFNpXHViOTdjIFx1YjE5M1x1Yzc0NCBcdWI1NGMsIGJpXHViMjk0IGJpLTFcdWJjZjRcdWIyZTRcdWIyOTQgXHVjZWU0XHVjNTdjIFx1ZDU1OFx1YjQxOCBcdWIyZTRcdWI5NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjIGJpXHVhYzAwIFx1Yzc5MVx1YWM4YyBcdWIxOTNcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzQ0IFx1YzljNFx1YzVmNFx1ZDU1OFx1YWNlMCBcdWIwOWMgXHViNGE0XHVjNWQwLCBcdWM2YjBcdWI5YWNcdWIyOTQgeVx1Y2Q5NSBcdWJjMjlcdWQ1YTVcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YjRlNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNzA0XHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQ1NWMgXHVjODEwXHVjNWQwXHVjMTFjIHlcdWNkOTUgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmMxOFx1YzljMVx1YzEyMFx1Yzc0NCBcdWFkZjhcdWI4MzhcdWM3NDQgXHViNTRjLCBcdWIyZTRcdWI5NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHViNGU0XHVhY2ZjIFx1YjljY1x1YjA5OFx1YzljMCBcdWM1NGFcdWIyOTQgXHViYzE4XHVjOWMxXHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAgJnF1b3Q7eVx1Y2Q5NSBcdWJjMjlcdWQ1YTVcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSZxdW90O1x1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDU1YyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgeVx1Y2Q5NSBcdWJjMjlcdWQ1YTVcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjExNjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLYWRqIFNxdWFyZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoaXMgcHJvYmxlbSwgeW91IGFyZSBnaXZlbiBhIHNlcXVlbmNlIFM8c3ViPjE8XC9zdWI+LCBTPHN1Yj4yPFwvc3ViPiwuLi4sIFM8c3ViPm48XC9zdWI+IG9mIHNxdWFyZXMgb2YgZGlmZmVyZW50IHNpemVzLiBUaGUgc2lkZXMgb2YgdGhlIHNxdWFyZXMgYXJlIGludGVnZXIgbnVtYmVycy4gV2UgbG9jYXRlIHRoZSBzcXVhcmVzIG9uIHRoZSBwb3NpdGl2ZSB4IC0geSBxdWFydGVyIG9mIHRoZSBwbGFuZSwgc3VjaCB0aGF0IHRoZWlyIHNpZGVzIG1ha2UgNDUgZGVncmVlcyB3aXRoIHggYW5kIHkgYXhlcywgYW5kIG9uZSBvZiB0aGVpciB2ZXJ0aWNlcyBhcmUgb24geSA9IDAgbGluZS4gTGV0IGI8c3ViPmk8XC9zdWI+IGJlIHRoZSB4IGNvb3JkaW5hdGVzIG9mIHRoZSBib3R0b20gdmVydGV4IG9mIFM8c3ViPmk8XC9zdWI+IC4gRmlyc3QsIHB1dCBTPHN1Yj4xPFwvc3ViPiBzdWNoIHRoYXQgaXRzIGxlZnQgdmVydGV4IGxpZXMgb24geCA9IDAgLiBUaGVuLCBwdXQgUzxzdWI+aTxcL3N1Yj4gLCAoaSAmZ3Q7IDEpIGF0IG1pbmltdW0gYjxzdWI+aTxcL3N1Yj4gc3VjaCB0aGF0PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+YjxzdWI+aTxcL3N1Yj4gJmd0OyBiPHN1Yj5pLTE8XC9zdWI+IGFuZDxcL2xpPlxyXG5cdDxsaT50aGUgaW50ZXJpb3Igb2YgUzxzdWI+aTxcL3N1Yj4gZG9lcyBub3QgaGF2ZSBpbnRlcnNlY3Rpb24gd2l0aCB0aGUgaW50ZXJpb3Igb2YgUzxzdWI+MTxcL3N1Yj4uLi5TPHN1Yj5pLTE8XC9zdWI+IC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC8yMDEwMDNcL3NxLkpQR1wiIHN0eWxlPVwiaGVpZ2h0OjE0OXB4OyB3aWR0aDoyMzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgZ29hbCBpcyB0byBmaW5kIHdoaWNoIHNxdWFyZXMgYXJlIHZpc2libGUsIGVpdGhlciBlbnRpcmVseSBvciBwYXJ0aWFsbHksIHdoZW4gdmlld2VkIGZyb20gYWJvdmUuIEluIHRoZSBleGFtcGxlIGFib3ZlLCB0aGUgc3F1YXJlcyBTPHN1Yj4xPFwvc3ViPiAsIFM8c3ViPjI8XC9zdWI+ICwgYW5kIFM8c3ViPjQ8XC9zdWI+IGhhdmUgdGhpcyBwcm9wZXJ0eS4gTW9yZSBmb3JtYWxseSwgUzxzdWI+aTxcL3N1Yj4gaXMgdmlzaWJsZSBmcm9tIGFib3ZlIGlmIGl0IGNvbnRhaW5zIGEgcG9pbnQgcCAsIHN1Y2ggdGhhdCBubyBzcXVhcmUgb3RoZXIgdGhhbiBTPHN1Yj5pPFwvc3ViPiBpbnRlcnNlY3QgdGhlIHZlcnRpY2FsIGhhbGYtbGluZSBkcmF3biBmcm9tIHAgdXB3YXJkcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBpcyBuICgxICZsZTsmbmJzcDtuICZsZTsmbmJzcDs1MCkgLCB0aGUgbnVtYmVyIG9mIHNxdWFyZXMuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIGludGVnZXJzIGJldHdlZW4gMSB0byAzMCwgd2hlcmUgdGhlIGktdGggbnVtYmVyIGlzIHRoZSBsZW5ndGggb2YgdGhlIHNpZGVzIG9mIFM8c3ViPmk8XC9zdWI+IC4gVGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSB6ZXJvIG51bWJlci48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBpbmRleCBvZiB0aGUgdmlzaWJsZSBzcXVhcmVzIGluIHRoZSBpbnB1dCBzZXF1ZW5jZSwgaW4gYXNjZW5kaW5nIG9yZGVyLCBzZXBhcmF0ZWQgYnkgYmxhbmsgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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

  • 문제를 번역한 사람: author5