시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 4 4 28.571%

문제

크기가 서로 다른 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+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkthZGogU3F1YXJlcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhpcyBwcm9ibGVtLCB5b3UgYXJlIGdpdmVuIGEgc2VxdWVuY2UgUzxzdWI+MTxcL3N1Yj4sIFM8c3ViPjI8XC9zdWI+LC4uLiwgUzxzdWI+bjxcL3N1Yj4gb2Ygc3F1YXJlcyBvZiBkaWZmZXJlbnQgc2l6ZXMuIFRoZSBzaWRlcyBvZiB0aGUgc3F1YXJlcyBhcmUgaW50ZWdlciBudW1iZXJzLiBXZSBsb2NhdGUgdGhlIHNxdWFyZXMgb24gdGhlIHBvc2l0aXZlIHggLSB5IHF1YXJ0ZXIgb2YgdGhlIHBsYW5lLCBzdWNoIHRoYXQgdGhlaXIgc2lkZXMgbWFrZSA0NSBkZWdyZWVzIHdpdGggeCBhbmQgeSBheGVzLCBhbmQgb25lIG9mIHRoZWlyIHZlcnRpY2VzIGFyZSBvbiB5ID0gMCBsaW5lLiBMZXQgYjxzdWI+aTxcL3N1Yj4gYmUgdGhlIHggY29vcmRpbmF0ZXMgb2YgdGhlIGJvdHRvbSB2ZXJ0ZXggb2YgUzxzdWI+aTxcL3N1Yj4gLiBGaXJzdCwgcHV0IFM8c3ViPjE8XC9zdWI+IHN1Y2ggdGhhdCBpdHMgbGVmdCB2ZXJ0ZXggbGllcyBvbiB4ID0gMCAuIFRoZW4sIHB1dCBTPHN1Yj5pPFwvc3ViPiAsIChpICZndDsgMSkgYXQgbWluaW11bSBiPHN1Yj5pPFwvc3ViPiBzdWNoIHRoYXQ8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5iPHN1Yj5pPFwvc3ViPiAmZ3Q7IGI8c3ViPmktMTxcL3N1Yj4gYW5kPFwvbGk+XHJcblx0PGxpPnRoZSBpbnRlcmlvciBvZiBTPHN1Yj5pPFwvc3ViPiBkb2VzIG5vdCBoYXZlIGludGVyc2VjdGlvbiB3aXRoIHRoZSBpbnRlcmlvciBvZiBTPHN1Yj4xPFwvc3ViPi4uLlM8c3ViPmktMTxcL3N1Yj4gLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcLzIwMTAwM1wvc3EuSlBHXCIgc3R5bGU9XCJoZWlnaHQ6MTQ5cHg7IHdpZHRoOjIzNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBnb2FsIGlzIHRvIGZpbmQgd2hpY2ggc3F1YXJlcyBhcmUgdmlzaWJsZSwgZWl0aGVyIGVudGlyZWx5IG9yIHBhcnRpYWxseSwgd2hlbiB2aWV3ZWQgZnJvbSBhYm92ZS4gSW4gdGhlIGV4YW1wbGUgYWJvdmUsIHRoZSBzcXVhcmVzIFM8c3ViPjE8XC9zdWI+ICwgUzxzdWI+MjxcL3N1Yj4gLCBhbmQgUzxzdWI+NDxcL3N1Yj4gaGF2ZSB0aGlzIHByb3BlcnR5LiBNb3JlIGZvcm1hbGx5LCBTPHN1Yj5pPFwvc3ViPiBpcyB2aXNpYmxlIGZyb20gYWJvdmUgaWYgaXQgY29udGFpbnMgYSBwb2ludCBwICwgc3VjaCB0aGF0IG5vIHNxdWFyZSBvdGhlciB0aGFuIFM8c3ViPmk8XC9zdWI+IGludGVyc2VjdCB0aGUgdmVydGljYWwgaGFsZi1saW5lIGRyYXduIGZyb20gcCB1cHdhcmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGlzIG4gKDEgJmxlOyZuYnNwO24gJmxlOyZuYnNwOzUwKSAsIHRoZSBudW1iZXIgb2Ygc3F1YXJlcy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG4gaW50ZWdlcnMgYmV0d2VlbiAxIHRvIDMwLCB3aGVyZSB0aGUgaS10aCBudW1iZXIgaXMgdGhlIGxlbmd0aCBvZiB0aGUgc2lkZXMgb2YgUzxzdWI+aTxcL3N1Yj4gLiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHplcm8gbnVtYmVyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGluZGV4IG9mIHRoZSB2aXNpYmxlIHNxdWFyZXMgaW4gdGhlIGlucHV0IHNlcXVlbmNlLCBpbiBhc2NlbmRpbmcgb3JkZXIsIHNlcGFyYXRlZCBieSBibGFuayBjaGFyYWN0ZXJzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2006 I번

  • 문제를 번역한 사람: author5