시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 312 | 37 | 36 | 20.225% |
크기가 서로 다른 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
ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2006 I번