안전한 철판 > 문제은행



실전대비 Level6

1506 : 안전한 철판

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 5 회    시도횟수: 8 회   



어떤 광선이 있다. 이 광선에 철판이 닿으면 철판이 녹는다. 광선의 세기를 올리면 앞선 철판을 녹이고 광선의 세기는 약해지며 그 다음에 부딪치는 철판까지도 녹일 수 있다. 아래 그림을 보자. 아래 그림은 위에서 본 그림이고 철판은 모두 세워져 있는 형태이다.

 

e3050b66a1b29a01767400d7560a4131_1449733
 

만일 광선의 세기가 1, 즉 하나의 철판을 녹일수 있는 정도라면 위의 그림에서와 같이 광선이 왼쪽에서 오른쪽으로 평행하게 나간다면, 광선과 조금도 접촉하지 않고 안전한 철판은 "2, 4"이다. "6"은 윗부분에서 닿아 철판이 녹는다. 만일 광선의 세기가 2라면, 즉 2개의 철판을 녹일 수 있다면 철판 "1"을 녹인 광선이 약해지고 2번 철판을 녹인다. 또 "1, 5, 2"번 철판에 닿지 않고 지나온 광선이 3번을 녹이면서 4번도 녹이므로 광선의 세기가 2에서는 안전한 철판이 아무것도 없다.

 

광선의 세기와 철판이 주어졌을 때 안전한 철판을 찾아라. 단, 각 철판은 그림과 같이 모두 수직방향으로 서 있다.




입력의 처음에는 10이하의 자연수인 광선의 세기가 주어진다. 그 다음줄에 철판의 개수가 주어진다. 철판의 개수는 50개 이하이다. 그 다음줄부터 한 줄에 각 철판의 정보 n, xn, ymin, ymax가 주어진다.

n은 철판의 번호이며 양의 정수이다. xn은 철판의 놓여진 x축의 좌표이다. ymin, ymax는 y축의 최저값과 최대값이다. x축과 y축의 좌표는 1,000이하의 자연수이다.




안전한 철판의 번호를 오름차순으로 정렬하여 한 줄에 공백으로 구분하여 모두 출력한다.
단 안전한 철판이 하나도 없다면 0을 출력한다.


1
6
1 3 6 10
2 6 7 9
3 8 4 8
4 10 2 9
5 4 1 4
6 11 9 15
2 4



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.