4532번
- The Screen Behind the Mirror
다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
문제
악마 박승원은 세계에서 가장 강력한 레이저를 찾기 위해 당신을 찾았다. 당신은 레이저 프로토타입이 있지만, 박승원에게 레이저 제작 예산을 받기 위해서는 시뮬레이션을 박승원에게 보여주어야 한다.
시뮬레이션은 2차원 평면 상에서 "거울", "광선 스플리터", "광선 감지기" 를 둠으로써 시작된다. 각 물체들은 선분으로 모델링된다.
- 거울 : 거울에 닿는 광선은 반대 방향으로 나아간다.
- 감지기 : 감지기는 들어오는 광선을 흡수한다.
- 스플리터 : 스플리터는 들어오는 광선을 두 광선으로 나눈다 - 한 광선은 스플리터를 관통하는 방향, 나머지 광선은 스플리터에 반사되는 방향이다.
시작점과 방향이 주어진 레이저가 발사되었을 때. 당신은 어떠한 감지기가 광선을 흡수했는지를 구해야 한다. 문제를 쉽게 하기 위해 다음과 같은 가정이 가능하다.
- 100 * 100 크기의 사각형 구역만 시뮬레이션하면 되며, 모든 물체는 해당 구역 안에 존재한다.
- 주어지는 선분들이 겹치거나 교점을 갖는 일은 없다.
- 사각형 구역의 가장자리에서 레이저는 발사된다.
- 시뮬레이션은 모든 광선이 테이블을 빠져나오거나 감지기에 흡수당했을 때 종료된다.
- 레이저 광선은 시뮬레이션을 통틀어 100번 이상 반사되지 않는다.
- 감지기는 1개 이상 존재한다.
- 시뮬레이션 과정에서 레이저 광선이 어떠한 물체와 한 직선 상에 놓여있는 일은 없다.
입력
첫 번째 줄에는 테스트 데이터의 수 N이 주어진다. 주어지는 데이터들은 다음과 같다 -
- 첫 번째 줄에는 "x,y i,j" 꼴로 테이블의 가장자리 중 하나인 시작점 (x,y) 와, 레이저 광선의 방향벡터 (i,j) 가 주어진다. (−1024 ≤ i,j ≤ 1024) 주어지는 수는 모두 정수이다.
- 두 번째 줄에는 물체의 수 P가 주어진다. (1 ≤ P ≤ 100)
- 이후 P개의 줄에 각각 물체들이 주어진다. "M"은 거울, "S"는 스플리터, "D"는 감지기를 뜻하며, 물체가 점유하는 각 끝점 두개가 "x,y" 꼴로 주어진다.
출력
각각의 테스트 케이스에 대해 먼저 첫 줄에 "DATA SET #k"를 출력하라. k는 테스트 케이스의 번호다.
만약 레이저 빔을 흡수한 감지기가 없다면, "NO BEAMS DETECTED"를 출력한다.
이외의 경우 레이저를 흡수한 감지기의 번호를 오름차순으로 출력하라.
제한
예제 입력 1
1 50,100 0,-1 6 D 0,40 20,20 M 40,20 60,40 D 80,20 100,40 D 0,70 20,90 S 40,90 60,70 D 80,90 100,70
예제 출력 1
DATA SET #1 1 6
힌트
Enigma - The Screen Behind The Mirror
W3sicHJvYmxlbV9pZCI6IjQ1MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUaGUgU2NyZWVuIEJlaGluZCB0aGUgTWlycm9yIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDVcdWI5YzggXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQwIFx1YzEzOFx1YWNjNFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhYzE1XHViODI1XHVkNTVjIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjk3YyBcdWNjM2VcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjJmOVx1YzJlMFx1Yzc0NCBcdWNjM2VcdWM1NThcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWI4MDhcdWM3NzRcdWM4MDAgXHVkNTA0XHViODVjXHVkMWEwXHVkMGMwXHVjNzg1XHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgXHViYzE1XHVjMmI5XHVjNmQwXHVjNWQwXHVhYzhjIFx1YjgwOFx1Yzc3NFx1YzgwMCBcdWM4MWNcdWM3OTEgXHVjNjA4XHVjMGIwXHVjNzQ0IFx1YmMxYlx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjMmRjXHViYmFjXHViODA4XHVjNzc0XHVjMTU4XHVjNzQ0IFx1YmMxNVx1YzJiOVx1YzZkMFx1YzVkMFx1YWM4YyBcdWJjZjRcdWM1ZWNcdWM4ZmNcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWJiYWNcdWI4MDhcdWM3NzRcdWMxNThcdWM3NDAgMlx1Y2MyOFx1YzZkMCBcdWQzYzlcdWJhNzQgXHVjMGMxXHVjNWQwXHVjMTFjICZxdW90O1x1YWM3MFx1YzZiOCZxdW90OywgJnF1b3Q7XHVhZDExXHVjMTIwIFx1YzJhNFx1ZDUwY1x1YjlhY1x1ZDEzMCZxdW90OywgJnF1b3Q7XHVhZDExXHVjMTIwIFx1YWMxMFx1YzljMFx1YWUzMCZxdW90OyBcdWI5N2MgXHViNDYwXHVjNzNjXHViODVjXHVjMzY4IFx1YzJkY1x1Yzc5MVx1YjQxY1x1YjJlNC4gXHVhYzAxIFx1YmIzY1x1Y2NiNFx1YjRlNFx1Yzc0MCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHViYWE4XHViMzc4XHViOWMxXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWM3MFx1YzZiOCA6IFx1YWM3MFx1YzZiOFx1YzVkMCBcdWIyZmZcdWIyOTQgXHVhZDExXHVjMTIwXHVjNzQwIFx1YmMxOFx1YjMwMCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViMDk4XHVjNTQ0XHVhYzA0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMTBcdWM5YzBcdWFlMzAgOiBcdWFjMTBcdWM5YzBcdWFlMzBcdWIyOTQgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IFx1YWQxMVx1YzEyMFx1Yzc0NCBcdWQ3NjFcdWMyMThcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJhNFx1ZDUwY1x1YjlhY1x1ZDEzMCA6IFx1YzJhNFx1ZDUwY1x1YjlhY1x1ZDEzMFx1YjI5NCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVhZDExXHVjMTIwXHVjNzQ0IFx1YjQ1MCBcdWFkMTFcdWMxMjBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4XHViMmU0IC0gXHVkNTVjIFx1YWQxMVx1YzEyMFx1Yzc0MCBcdWMyYTRcdWQ1MGNcdWI5YWNcdWQxMzBcdWI5N2MgXHVhZDAwXHVkMWI1XHVkNTU4XHViMjk0IFx1YmMyOVx1ZDVhNSwgXHViMDk4XHViYTM4XHVjOWMwIFx1YWQxMVx1YzEyMFx1Yzc0MCBcdWMyYTRcdWQ1MGNcdWI5YWNcdWQxMzBcdWM1ZDAgXHViYzE4XHVjMGFjXHViNDE4XHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9taXJyb3IucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAycHg7IHdpZHRoOjQ0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1Yzc5MVx1YzgxMFx1YWNmYyBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjgwOFx1Yzc3NFx1YzgwMFx1YWMwMCBcdWJjMWNcdWMwYWNcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjLiBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNWI0XHViNWEwXHVkNTVjIFx1YWMxMFx1YzljMFx1YWUzMFx1YWMwMCBcdWFkMTFcdWMxMjBcdWM3NDQgXHVkNzYxXHVjMjE4XHVkNTg4XHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWMyN2RcdWFjOGMgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWMwMFx1YzgxNVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MTAwICogMTAwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZDZjXHVjNWVkXHViOWNjIFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1YzE1OFx1ZDU1OFx1YmE3NCBcdWI0MThcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWIyOTQgXHVkNTc0XHViMmY5IFx1YWQ2Y1x1YzVlZCBcdWM1NDhcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMTIwXHViZDg0XHViNGU0XHVjNzc0IFx1YWNiOVx1Y2U1OFx1YWM3MFx1YjA5OCBcdWFkNTBcdWM4MTBcdWM3NDQgXHVhYzE2XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkNmNcdWM1ZWRcdWM3NTggXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YjI5NCBcdWJjMWNcdWMwYWNcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1YzE1OFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVhZDExXHVjMTIwXHVjNzc0IFx1ZDE0Y1x1Yzc3NFx1YmUxNFx1Yzc0NCBcdWJlNjBcdWM4MzhcdWIwOThcdWM2MjRcdWFjNzBcdWIwOTggXHVhYzEwXHVjOWMwXHVhZTMwXHVjNWQwIFx1ZDc2MVx1YzIxOFx1YjJmOVx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjODg1XHViOGNjXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI4MDhcdWM3NzRcdWM4MDAgXHVhZDExXHVjMTIwXHVjNzQwIFx1YzJkY1x1YmJhY1x1YjgwOFx1Yzc3NFx1YzE1OFx1Yzc0NCBcdWQxYjVcdWQyYzBcdWM1YjQgMTAwXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWJjMThcdWMwYWNcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMTBcdWM5YzBcdWFlMzBcdWIyOTQgMVx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyZGNcdWJiYWNcdWI4MDhcdWM3NzRcdWMxNTggXHVhY2ZjXHVjODE1XHVjNWQwXHVjMTFjIFx1YjgwOFx1Yzc3NFx1YzgwMCBcdWFkMTFcdWMxMjBcdWM3NzQgXHVjNWI0XHViNWEwXHVkNTVjIFx1YmIzY1x1Y2NiNFx1YzY0MCBcdWQ1NWMgXHVjOWMxXHVjMTIwIFx1YzBjMVx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI0ZTRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNCAtPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJnF1b3Q7eCx5IGksaiZxdW90OyBcdWFmMzRcdWI4NWMgXHVkMTRjXHVjNzc0XHViZTE0XHVjNzU4IFx1YWMwMFx1YzdhNVx1Yzc5MFx1YjlhYyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc4IFx1YzJkY1x1Yzc5MVx1YzgxMCAoeCx5KSBcdWM2NDAsIFx1YjgwOFx1Yzc3NFx1YzgwMCBcdWFkMTFcdWMxMjBcdWM3NTggXHViYzI5XHVkNWE1XHViY2ExXHVkMTMwIChpLGopIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgmbWludXM7MTAyNCAmbGU7IGksaiAmbGU7IDEwMjQpIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjNjXHVjY2I0XHVjNzU4IFx1YzIxOCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQICZsZTsgMTAwKTxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQgUFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxIFx1YmIzY1x1Y2NiNFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICZxdW90O00mcXVvdDtcdWM3NDAgXHVhYzcwXHVjNmI4LCAmcXVvdDtTJnF1b3Q7XHViMjk0IFx1YzJhNFx1ZDUwY1x1YjlhY1x1ZDEzMCwgJnF1b3Q7RCZxdW90O1x1YjI5NCBcdWFjMTBcdWM5YzBcdWFlMzBcdWI5N2MgXHViNzNiXHVkNTU4XHViYTcwLCBcdWJiM2NcdWNjYjRcdWFjMDAgXHVjODEwXHVjNzIwXHVkNTU4XHViMjk0IFx1YWMwMSBcdWIwNWRcdWM4MTAgXHViNDUwXHVhYzFjXHVhYzAwICZxdW90O3gseSZxdW90OyBcdWFmMzRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YmEzY1x1YzgwMCBcdWNjYWIgXHVjOTA0XHVjNWQwICZxdW90O0RBVEEgU0VUICNrJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4ga1x1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YjgwOFx1Yzc3NFx1YzgwMCBcdWJlNTRcdWM3NDQgXHVkNzYxXHVjMjE4XHVkNTVjIFx1YWMxMFx1YzljMFx1YWUzMFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQsICZxdW90O05PIEJFQU1TIERFVEVDVEVEJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI5N2MgXHVkNzYxXHVjMjE4XHVkNTVjIFx1YWMxMFx1YzljMFx1YWUzMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+RW5pZ21hIC0gVGhlIFNjcmVlbiBCZWhpbmQgVGhlIE1pcnJvcjxcL3A+XHJcblxyXG48cD48aWZyYW1lIGZyYW1lYm9yZGVyPVwiMFwiIGhlaWdodD1cIjMxNVwiIHNyYz1cImh0dHBzOlwvXC93d3cueW91dHViZS5jb21cL2VtYmVkXC9aY3hKRV9UT0dKWVwiIHdpZHRoPVwiNTYwXCI+PFwvaWZyYW1lPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDUzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBTY3JlZW4gQmVoaW5kIHRoZSBNaXJyb3IiLCJkZXNjcmlwdGlvbiI6IjxwPkRyLiBFdmlsIGhhcyBjb250cmFjdGVkIHlvdXIgdmFsdWFibGUgc2VydmljZXMgdG8gYnVpbGQgZm9yIGhpbSB0aGUgd29ybGQmIzM5O3MgbW9zdCBwb3dlcmZ1bCAmcXVvdDtsYXNlciZxdW90Oy4gT2YgY291cnNlIGJlZm9yZSB5b3Ugc3BlbmQgb25lIGJpbGxpb24gZG9sbGFycyBidWlsZGluZyB0aGUgdGhpbmcsIHlvdSB3YW50IHRvIHJ1biBzb21lIHNpbXVsYXRpb25zIGZpcnN0IHRvIG1ha2Ugc3VyZSBldmVyeXRoaW5nIHdpbGwgd29yayBhcyBkZXNpZ25lZC4gRm9yIHRoaXMgcGhhc2Ugb2YgdGhlIHByb2plY3QsIHlvdSB3aWxsIGJlIHNpbXVsYXRpbmcgcGFydCBvZiB0aGUgYWltaW5nIHN5c3RlbSB3aGljaCB1c2VzIG1pcnJvcnMgYW5kIG90aGVyIG9wdGljcyB0byBjaGFuZ2UgdGhlIGRpcmVjdGlvbiBvZiB0aGUgbGFzZXIgYmVhbS48XC9wPlxyXG5cclxuPHA+VGhlIHNpbXVsYXRpb24gY29uc2lzdHMgb2YgYSBmbGF0IHNxdWFyZSB0YWJsZSB3aXRoIG1pcnJvcnMsIGJlYW0gc3BsaXR0ZXJzLCBhbmQgYmVhbSBkZXRlY3RvcnMgYXJyYW5nZWQgb24gdGhlIHRhYmxldG9wLCBhbmQgd2l0aCBlYWNoIG9iamVjdCByZXByZXNlbnRlZCBieSBhIG9uZSBkaW1lbnNpb25hbCBsaW5lIHNlZ21lbnQuIFRoZSBsaXN0IGJlbG93IGRlc2NyaWJlcyBlYWNoIG9mIHRoZSBvYmplY3QgdHlwZXMgaW4gZGV0YWlsOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm1pcnJvciA6IEEgbWlycm9yIG9iamVjdCB3aWxsIHJlZmxlY3QgYW55IGxhc2VyIGJlYW0gc3RyaWtpbmcgaXRzIHN1cmZhY2UuIFRoZSByZWZsZWN0ZWQgYmVhbSBsZWF2ZXMgYXQgdGhlIHNhbWUgYW5nbGUgb2YgaW5jaWRlbmNlIGFzIHRoZSBpbmNvbWluZyBiZWFtLiBOb3RlIHRoYXQgYm90aCBzaWRlcyBvZiBhIG1pcnJvciBvYmplY3QgYXJlIHJlZmxlY3RpdmUuPFwvbGk+XHJcblx0PGxpPmRldGVjdG9yIDogQSBkZXRlY3RvciBpcyBhbiBvcGFxdWUgb2JqZWN0IHdoaWNoIGFic29yYnMgYW55IGxhc2VyIGJlYW0gc3RyaWtpbmcgaXQuIFRoZSBzaW11bGF0aW9uIG11c3QgYWxzbyBrZWVwIHRyYWNrIG9mIHdoaWNoIGRldGVjdG9ycyBhcmUgc3RydWNrIGJ5IGEgbGFzZXIgZm9yIHByb2dyYW0gb3V0cHV0IHB1cnBvc2VzLiBOb3RlIHRoYXQgYSBsYXNlciBiZWFtIHN0cmlrZSBvbiBlaXRoZXIgc2lkZSBvZiBhIGRldGVjdG9yIGNvdW50cyBhcyBhICZxdW90O2hpdCZxdW90Oy48XC9saT5cclxuXHQ8bGk+c3BsaXR0ZXIgOiBXaGVuIGEgbGFzZXIgYmVhbSBzdHJpa2VzIGEgc3BsaXR0ZXIsIGl0IGRpdmlkZXMgaW50byB0d28gYmVhbXMuIE9uZSBvZiB0aGUgbmV3IGJlYW1zIHdpbGwgcmVmbGVjdCBmcm9tIHRoZSBzcGxpdHRlciBzdXJmYWNlIChhcyB3aXRoIGEgbWlycm9yKSwgYW5kIHRoZSBvdGhlciBiZWFtIHdpbGwgcGFzcyB0aHJvdWdoIHRoZSBzcGxpdHRlciB3aXRob3V0IGNoYW5naW5nIGRpcmVjdGlvbi4gQSBzcGxpdHRlciB3aWxsIGZ1bmN0aW9uIHRoZSBzYW1lIHdheSByZWdhcmRsZXNzIHdoaWNoIHNpZGUgb2YgaXQgaXMgc3RydWNrIGJ5IGEgbGFzZXIgYmVhbS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5TZWUgdGhlIGZpZ3VyZXMgYmVsb3cgZm9yIGV4YW1wbGVzIG9mIGEgbGFzZXIgYmVhbSYjMzk7cyBpbnRlcmFjdGlvbiB3aXRoIGVhY2ggb2YgdGhlIHBvc3NpYmxlIG9iamVjdCB0eXBlczo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvbWlycm9yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwMnB4OyB3aWR0aDo0NDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBzaW11bGF0aW9uLCBhIHNpbmdsZSBsYXNlciBiZWFtIGVudGVycyB0aGUgdGFibGV0b3AgYXJlYS4gVGhlIHByb2dyYW0gbXVzdCBjb21wdXRlIHRoZSBwYXRoIHRha2VuIGJ5IHRoZSBsYXNlciBiZWFtIChpbmNsdWRpbmcgc2Vjb25kYXJ5IGJlYW1zIGR1ZSB0byBzcGxpdHRlcnMpLCBhbmQgaXQgbXVzdCBkZXRlcm1pbmUgd2hpY2ggZGV0ZWN0b3JzIGFyZSBzdHJ1Y2sgYnkgYSBsYXNlciBiZWFtLjxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIG1ha2UgdGhlIGZvbGxvd2luZyBhc3N1bXB0aW9ucyBpbiB0aGUgcHJvZ3JhbTo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGUgdGFibGV0b3Agc3VyZmFjZSBpcyBhIDEwMCBieSAxMDAgc3F1YXJlLCBhbmQgdW5sZXNzIG90aGVyd2lzZSBzcGVjaWZpZWQgYWxsIGNvb3JkaW5hdGVzIGluIHRoZSBwcm9ncmFtJiMzOTtzIGlucHV0IGFyZSBnaXZlbiBhcyBpbnRlZ2VycyB3aXRoaW4gdGhlIHRhYmxldG9wIGFyZWEgKGkuZS4gYmV0d2VlbiAwIGFuZCAxMDAgaW5jbHVzaXZlKS48XC9saT5cclxuXHQ8bGk+VGhlcmUgd2lsbCBiZSBubyBvdmVybGFwcyBiZXR3ZWVuIHRoZSBsaW5lIHNlZ21lbnQgb2JqZWN0cy48XC9saT5cclxuXHQ8bGk+VGhlIGxhc2VyIHdoaWNoIGVudGVycyB0aGUgdGFibGV0b3AgYXJlYSBhbHdheXMgc3RhcnRzIGZyb20gdGhlIGVkZ2Ugb2YgdGhlIHRhYmxlLjxcL2xpPlxyXG5cdDxsaT5UaGUgc2ltdWxhdGlvbiBvZiBlYWNoIGRhdGEgc2V0IGVuZHMgd2hlbiBhbGwgbGFzZXIgYmVhbXMgaGF2ZSBlaXRoZXIgZXhpdGVkIHRoZSB0YWJsZSB0b3AgYXJlYSBvciBoYXZlIHRlcm1pbmF0ZWQgYXQgYSBkZXRlY3Rvci48XC9saT5cclxuXHQ8bGk+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgd2lsbCBiZSBubyBtb3JlIHRoYW4gMTAwIHRvdGFsIHJlZmxlY3Rpb25zIGFtb25nIGFsbCBsYXNlciBiZWFtcyBpbiB0aGF0IGRhdGEgc2V0LjxcL2xpPlxyXG5cdDxsaT5BIGxhc2VyIGJlYW0gd2lsbCBuZXZlciBpbnRlcnNlY3QgYW55IG9iamVjdCBvbiBhIHZlcnRleCBhbmQgd2lsbCBuZXZlciBiZSBjb2xsaW5lYXIgd2l0aCBhbiBvYmplY3QmIzM5O3MgbGluZSBzZWdtZW50LjxcL2xpPlxyXG5cdDxsaT5FYWNoIGRhdGEgc2V0IHdpbGwgY29udGFpbiBhdCBsZWFzdCBvbmUgZGV0ZWN0b3Igb2JqZWN0LjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB0byB0aGlzIHByb2JsZW0gd2lsbCBiZWdpbiB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDApIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBkYXRhIHNldHMuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgdGhlIGZvbGxvd2luZyBjb21wb25lbnRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgc2luZ2xlIGxpbmUgd2l0aCBmb3VyIG51bWJlcnMgJnF1b3Q7eCx5IGksaiZxdW90OyB3aGVyZSB4LHkgaXMgYSBwb2ludCBhbG9uZyB0aGUgdGFibGUgZWRnZSBhdCB3aGljaCB0aGUgbGFzZXIgYmVhbSBlbnRlcnMsIGFuZCBpLGogaXMgYSB2ZWN0b3Igd2l0aCBpbnRlZ2VyIGNvbXBvbmVudHMgKCZtaW51czsxMDI0ICZsZTsgaSxqICZsZTsgMTAyNCkgc3BlY2lmeWluZyB0aGUgZGlyZWN0aW9uIG9mIHRoZSBpbmNvbWluZyBsYXNlciBiZWFtLCB3aGVyZSBpIGNvcnJlc3BvbmRzIHRvIHRoZSB4LWF4aXMgZGlyZWN0aW9uIGFuZCBqIGNvcnJlc3BvbmRzIHRvIHRoZSB5LWF4aXMgZGlyZWN0aW9uLjxcL2xpPlxyXG5cdDxsaT5BIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIFAgKDEgJmxlOyBQICZsZTsgMTAwKSBnaXZpbmcgdGhlIHRvdGFsIG51bWJlciBvZiBvYmplY3RzIGluIHRoaXMgZGF0YSBzZXQuPFwvbGk+XHJcblx0PGxpPkEgc2VyaWVzIG9mIFAgbGluZXMsIGVhY2ggcmVwcmVzZW50aW5nIG9uZSBvYmplY3QsIHdpdGggdGhlIGZpcnN0IGxpbmUgZGVzY3JpYmluZyBvYmplY3QgMSwgdGhlIHNlY29uZCBsaW5lIGRlc2NyaWJpbmcgb2JqZWN0IDIsIGFuZCBzbyBvbi4gRWFjaCBsaW5lIGJlZ2lucyB3aXRoIGEgc2luZ2xlIGxldHRlciBzcGVjaWZ5aW5nIHRoZSBvYmplY3QgdHlwZSB3aGVyZSBhICZxdW90O00mcXVvdDsgaW5kaWNhdGVzIGEgbWlycm9yIG9iamVjdCwgJnF1b3Q7UyZxdW90OyBhIHNwbGl0dGVyLCBhbmQgJnF1b3Q7RCZxdW90OyBhIGRldGVjdG9yLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IHR3byBjb29yZGluYXRlIHBhaXJzIG9mIHRoZSBmb3JtICZxdW90O3gseSZxdW90Oywgc3BlY2lmeWluZyB0aGUgdHdvIGVuZCBwb2ludHMgb2YgdGhlIG9iamVjdCYjMzk7cyBsaW5lIHNlZ21lbnQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCBpbiB0aGUgaW5wdXQsIG91dHB1dCB0aGUgaGVhZGluZyAmcXVvdDtEQVRBIFNFVCAjayZxdW90OyB3aGVyZSBrIGlzIDEgZm9yIHRoZSBmaXJzdCBkYXRhIHNldCwgMiBmb3IgdGhlIHNlY29uZCwgZXRjLiBJZiBpbiB0aGlzIGRhdGEgc2V0IG5vbmUgb2YgdGhlIGRldGVjdG9yIG9iamVjdHMgYXJlIHN0cnVjayBieSBhbnkgbGFzZXIgYmVhbXMsIG91dHB1dCB0aGUgbWVzc2FnZSAmcXVvdDtOTyBCRUFNUyBERVRFQ1RFRCZxdW90Oy4gT3RoZXJ3aXNlLCBvdXRwdXQgdGhlIG9iamVjdCBudW1iZXIsIG9uZSBwZXIgbGluZSwgb2YgZWFjaCBkZXRlY3RvciBzdHJ1Y2sgYnkgYSBsYXNlciBiZWFtLiBUaGUgbGlzdCBvZiBkZXRlY3RvcnMgc2hvdWxkIGJlIHNvcnRlZCBieSB0aGVpciBvYmplY3QgbnVtYmVycyBhbmQgb3V0cHV0IGluIGFzY2VuZGluZyBvcmRlci4gSWYgYSBkZXRlY3RvciBpcyBzdHJ1Y2sgYnkgbW9yZSB0aGFuIG9uZSBsYXNlciBiZWFtLCBpdCBzaG91bGQgb25seSBiZSBsaXN0ZWQgb25jZSBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=
출처
ICPC > Regionals > North America > South Central USA Regional > 2007 South Central USA Regional Programming Contest 3번
- 문제를 번역한 사람: koosaga
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호