시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 28 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축 방향에서 보이는 정사각형의 번호를 빈 칸을 사이에 두고 증가하는 순서로 출력한다.

예제 입력

4
3 5 1 4

예제 출력

1 2 4 

힌트

출처

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

  • 문제를 번역한 사람: author5