1993번 - 경주 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB29151365.000%

문제

n개의 체크포인트가 있고, 원점에서 출발하여 체크포인트들을 순서대로 방문하고 원점으로 돌아오는 경주가 진행된다. 이때 모든 체크포인트를 방문할 필요는 없지만 반드시 주어진 순서를 지키면서 방문해야 한다. 체크포인트 번호가 순서대로 1~n이라 할 때, 1, 2, 5번 순서대로 방문할 수는 있지만 4, 2번 순서대로는 방문할 수 없다.

원점이나 체크포인트 사이를 이동할 때는 반드시 직선 경로로 이동하는데, 이때 경로 위에 다른 체크포인트가 존재할 수도 있다. 이때는 방문해도 되고 방문하지 않아도 된다. 그리고 각각의 체크포인트에는 방문할 시 얻는 점수가 있는데, 우승자는 방문한 체크포인트의 점수 합이 가장 높은 사람이 된다. 물론 하나의 체크포인트에서는 점수를 한 번만 획득할 수 있다.

그러나 경주에 참여한 사람들이 모두 남규와 그 친구들이라 하나같이 약골이다. 그들은 각각 달릴 수 있는 거리 한계가 명확해서 그 안에 돌아오지 못하면 대회를 완주할 수 없다. 그들은 약골인데다 근성도 없어서 절대 그 거리보다 많이 뛸 수 없다. 다행히 각자는 자신이 얼마나 달릴 수 있는지 알고 있기 때문에, 한도 안에서 완주하면서 얻을 수 있는 점수가 최대 몇 점인지를 미리 계산해보려고 한다. 남규와 친구들을 위해 이를 구해 주는 프로그램을 작성해보자!

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같이 이루어져 있으며, 전체 입력의 끝에는 0 하나가 주어진다.

  • 첫째 줄에 체크포인트의 개수 n이 주어진다(1 ≤ n ≤ 30).
  • 이어서 n개의 줄에 각 체크포인트의 좌표 x, y, 점수 s를 의미하는 정수 3개가 순서대로 주어진다(−5000 ≤ x, y ≤ 5000, 10 ≤ s ≤ 200).
  • 이어서 여러 줄에 각 선수의 이름과 최대한 달릴 수 있는 거리의 한계를 의미하는 정수 d가 공백으로 구분되어 줄마다 주어진다(0 ≤ d ≤ 10000). 선수의 이름은 60글자를 넘지 않으며 공백을 포함하지 않는다. 마지막 줄에는 선수 이름 대신 '# 0'이 주어지며, 이 줄은 각 테스트 케이스의 끝을 의미한다.

각 선수들은 원점(0, 0)에서 출발하여 몇몇 체크포인트를 방문했다가 다시 원점으로 돌아와야 한다. 아무것도 방문하지 않을 수도 있다. 경주가 이루어지는 공간은 완전히 평평한 2차원 공간이라고 가정한다.

출력

각 테스트 케이스마다 첫째 줄에 ‘Race r’을 출력한다. r에는 테스트 케이스의 번호가 들어간다. 이어서 각 줄마다 선수 정보를 입력받은 순서대로 선수의 이름과 얻을 수 있는 최대 점수를 출력 양식 ‘이름: 점수’에 맞게 출력한다.

예제 입력 1 

5
750 -800 30
1500 0 50
750 750 60
-1250 750 70
-1000 -500 50
Chris 7000
Karl 6500
Tania 5000
# 0
4
500 0 10
0 500 10
-500 0 10
0 -500 10
Hanny 2100
Lizzie 1800
# 0
0

예제 출력 1 

Race 1
Chris: 230
Karl: 180
Tania: 140
Race 2
Hanny: 20
Lizzie: 20
W3sicHJvYmxlbV9pZCI6IjE5OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYmRcdWM4ZmMiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVjNmQwXHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI0ZTRcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWNlMCBcdWM2ZDBcdWM4MTBcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1YWNiZFx1YzhmY1x1YWMwMCBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWJhYThcdWI0ZTAgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHVjOWMwXHViOWNjIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViOTdjIFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWJjMjlcdWJiMzhcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAxfm5cdWM3NzRcdWI3N2MgXHVkNTYwIFx1YjU0YywgMSwgMiwgNVx1YmM4OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM3ODhcdWM5YzBcdWI5Y2MgNCwgMlx1YmM4OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWNcdWIyOTQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzgxMFx1Yzc3NFx1YjA5OCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjggXHVjMGFjXHVjNzc0XHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGNcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YzljMVx1YzEyMCBcdWFjYmRcdWI4NWNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwLCBcdWM3NzRcdWI1NGMgXHVhY2JkXHViODVjIFx1YzcwNFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGNcdWIyOTQgXHViYzI5XHViYjM4XHVkNTc0XHViM2M0IFx1YjQxOFx1YWNlMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM1ZDBcdWIyOTQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzJkYyBcdWM1YmJcdWIyOTQgXHVjODEwXHVjMjE4XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNmIwXHVjMmI5XHVjNzkwXHViMjk0IFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM3NTggXHVjODEwXHVjMjE4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWQ1NThcdWIwOThcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNWQwXHVjMTFjXHViMjk0IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHViYzg4XHViOWNjIFx1ZDY4ZFx1YjRkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIwOTggXHVhY2JkXHVjOGZjXHVjNWQwIFx1Y2MzOFx1YzVlY1x1ZDU1YyBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViYWE4XHViNDUwIFx1YjBhOFx1YWRkY1x1YzY0MCBcdWFkZjggXHVjZTVjXHVhZDZjXHViNGU0XHVjNzc0XHViNzdjIFx1ZDU1OFx1YjA5OFx1YWMxOVx1Yzc3NCBcdWM1N2RcdWFjZThcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWFjMDFcdWFjMDEgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjIFx1ZDU1Y1x1YWNjNFx1YWMwMCBcdWJhODVcdWQ2NTVcdWQ1NzRcdWMxMWMgXHVhZGY4IFx1YzU0OFx1YzVkMCBcdWIzY2NcdWM1NDRcdWM2MjRcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0IFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWM2NDRcdWM4ZmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIFx1YzU3ZFx1YWNlOFx1Yzc3OFx1YjM3MFx1YjJlNCBcdWFkZmNcdWMxMzFcdWIzYzQgXHVjNWM2XHVjNWI0XHVjMTFjIFx1YzgwOFx1YjMwMCBcdWFkZjggXHVhYzcwXHViOWFjXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc3NCBcdWI2ZjggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViMmU0XHVkNTg5XHVkNzg4IFx1YWMwMVx1Yzc5MFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1YjJlY1x1YjliNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NWNcdWIzYzQgXHVjNTQ4XHVjNWQwXHVjMTFjIFx1YzY0NFx1YzhmY1x1ZDU1OFx1YmE3NFx1YzExYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWM4MTBcdWM3NzhcdWM5YzBcdWI5N2MgXHViYmY4XHViOWFjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjBhOFx1YWRkY1x1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDQgXHVjNzA0XHVkNTc0IFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NzQgXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NzRcdWJjZjRcdWM3OTAhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjODA0XHVjY2I0IFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM1ZDBcdWIyOTQgMCBcdWQ1NThcdWIwOThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgxICZsZTsgbiAmbGU7IDMwKS48XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVjNWI0XHVjMTFjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM3NTggXHVjODhjXHVkNDVjIHgsIHksIFx1YzgxMFx1YzIxOCBzXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggM1x1YWMxY1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KCZtaW51czs1MDAwICZsZTsgeCwgeSAmbGU7IDUwMDAsIDEwICZsZTsgcyAmbGU7IDIwMCkuPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1YzViNFx1YzExYyBcdWM1ZWNcdWI3ZWMgXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWMxMjBcdWMyMThcdWM3NTggXHVjNzc0XHViOTg0XHVhY2ZjIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWIyZWNcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkNTVjXHVhY2M0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggZFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzkwNFx1YjljOFx1YjJlNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoMCAmbGU7IGQgJmxlOyAxMDAwMCkuIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgNjBcdWFlMDBcdWM3OTBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWMyMTggXHVjNzc0XHViOTg0IFx1YjMwMFx1YzJlMCAmIzM5OyMgMCYjMzk7XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzkwNFx1Yzc0MCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWIwNWRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMSBcdWMxMjBcdWMyMThcdWI0ZTRcdWM3NDAgXHVjNmQwXHVjODEwKDAsIDApXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyBcdWJhODdcdWJhODcgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU4OFx1YjJlNFx1YWMwMCBcdWIyZTRcdWMyZGMgXHVjNmQwXHVjODEwXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1YmIzNFx1YWM4M1x1YjNjNCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YWNiZFx1YzhmY1x1YWMwMCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2Y1XHVhYzA0XHVjNzQwIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWQzYzlcdWQzYzlcdWQ1NWMgMlx1Y2MyOFx1YzZkMCBcdWFjZjVcdWFjMDRcdWM3NzRcdWI3N2NcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJmxzcXVvO1JhY2UgciZyc3F1bztcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiByXHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YjRlNFx1YzViNFx1YWMwNFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjMTIwXHVjMjE4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWFjZmMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjUgXHVjNTkxXHVjMmRkICZsc3F1bztcdWM3NzRcdWI5ODQ6IFx1YzgxMFx1YzIxOCZyc3F1bztcdWM1ZDAgXHViOWRlXHVhYzhjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxOTkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGFsZi1TY29yZSBPcmllbnRlZXJpbmciLCJkZXNjcmlwdGlvbiI6IjxwPk9yaWVudGVlcmluZyBpbnZvbHZlcyBydW5uaW5nIHRocm91Z2ggdW5mYW1pbGlhciB0ZXJyaXRvcnksIHVzaW5nIG1hcCBhbmQgY29tcGFzcyB0byBuYXZpZ2F0ZSB0byB2YXJpb3VzICZsc3F1bztjb250cm9sIHBvaW50cyZyc3F1bzsgbWFya2VkIG9uIHRoZSBtYXAuIEluIHRoZSBtb3N0IGNvbW1vbiBmb3JtIG9mIHRoZSBzcG9ydCwgdGhlIG9yZGVyIGluIHdoaWNoIHRoZSBjb250cm9sIHNpdGVzIG11c3QgYmUgdmlzaXRlZCBpcyBzZXQgaW4gYWR2YW5jZSBieSB0aGUgcmFjZSBvcmdhbmlzZXJzLCBhbmQgdGhlIHdpbm5lciBvZiBhIHJhY2UgaXMgdGhlIHJ1bm5lciB3aG8gdmlzaXRzIGFsbCB0aGUgY29udHJvbHMgaW4gdGhlIHByZXNjcmliZWQgb3JkZXIgYW5kIGFycml2ZXMgYXQgdGhlIGZpbmlzaCBsaW5lIGluIHRoZSBzaG9ydGVzdCBhbW91bnQgb2YgdGltZS4gVGh1cyB0aGUgZ29hbCBpcyB0byB2aXNpdCBhbGwgY29udHJvbHMgKGluIG9yZGVyKSBhcyBmYXN0IGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Bbm90aGVyIGRpc2NpcGxpbmUgaXMgU2NvcmUgT3JpZW50ZWVyaW5nLCBpbiB3aGljaCB0aGUgZ29hbCBpcyB0aGUgY29udmVyc2U6IHRvIG1heGltaXNlIHlvdXIgc2NvcmUgYnkgdmlzaXRpbmcgYXMgbWFueSBjb250cm9scyBhcyBwb3NzaWJsZSBpbiBhIHNldCBhbW91bnQgb2YgdGltZS4gSGVyZSB0aGUgb3JnYW5pc2VycyBjaG9vc2UgYSB0aW1lIGxpbWl0IGFuZCBhc3NpZ24gYSBwb2ludHMgdmFsdWUgdG8gZWFjaCBjb250cm9sLCBnZW5lcmFsbHkgY29ycmVsYXRlZCB0byBpdHMgZGlmZmljdWx0eSBhbmQgZGlzdGFuY2UgZnJvbSB0aGUgc3RhcnQuIEEgcnVubmVyJnJzcXVvO3Mgc2NvcmUgaXMgdGhlIHN1bSBvZiB0aGUgc2NvcmVzIG9mIGFsbCB0aGUgY29udHJvbHMgdmlzaXRlZCwgbGVzcyBhIHBlbmFsdHkgZm9yIGFycml2aW5nIGF0IHRoZSBmaW5pc2ggbGluZSBpbiBleGNlc3Mgb2YgdGhlIHByZXNjcmliZWQgdGltZSBsaW1pdC4gKE5vdGUgdGhhdCB3aGlsZSB2aXNpdGluZyBvciBwYXNzaW5nIHRocm91Z2ggYSBjb250cm9sIHNpdGUgbW9yZSB0aGFuIG9uY2UgaXMgYWxsb3dlZCwgaXRzIHNjb3JlIG9ubHkgY291bnRzIHRvd2FyZHMgdGhlIHJ1bm5lciZyc3F1bztzIHNjb3JlIG9uY2UsIHNvIHRoZXJlJnJzcXVvO3Mgbm8gYWR2YW50YWdlIGluIHJldmlzaXRpbmcgY29udHJvbHMuKTxcL3A+XHJcblxyXG48cD5UaHVzIHJ1bm5lcnMgYmVnaW4gdGhpcyBraW5kIG9mIHJhY2UgYnkgZXN0aW1hdGluZyBob3cgZmFyIHRoZXkgY2FuIHJ1biBpbiB0aGUgdGltZSBhdmFpbGFibGUgYW5kIGNob29zaW5nIGEgc3Vic2V0IG9mIChpZGVhbGx5IGhpZ2gtc2NvcmluZykgY29udHJvbHMgdGhhdCBjYW4gYmUgYXJyYW5nZWQgaW50byBhIHJvdXRlIHdpdGggYSB0b3RhbCBsZW5ndGggdmVyeSBjbG9zZSB0bywgYnV0IG5vdCBleGNlZWRpbmcsIHRoZWlyIGRpc3RhbmNlIGVzdGltYXRlLjxcL3A+XHJcblxyXG48cD5GaW5hbGx5LCBhbiBvYnNjdXJlIHZhcmlhbnQgb2YgdGhlIHNjb3JlIGRpc2NpcGxpbmUgaXMgSGFsZi1TY29yZSBPcmllbnRlZXJpbmcsIGluIHdoaWNoIHRoZSBvcmdhbmlzZXJzIGRlZmluZSB0aGUgb3JkZXIgaW4gd2hpY2ggdGhlIGNvbnRyb2wgc2l0ZXMgbXVzdCBiZSB2aXNpdGVkLCBidXQgdGhlIHJ1bm5lcnMgY2hvb3NlIGEgc3Vic2V0IG9mIHRoZSBjb250cm9scyZtZGFzaDthaW1pbmcgZm9yIGEgaGlnaC1zY29yaW5nIHN1YnNlcXVlbmNlIHRoYXQgZm9ybXMgYSByb3V0ZSBmb2xsb3dpbmcgdGhlIGdlbmVyYWwgb3V0bGluZSBvZiB0aGUgb3JnYW5pc2VycyZyc3F1bzsgY291cnNlIChhbmQgb3JkZXJpbmcpIGJ1dCBza2lwcGluZyB1bmRlc2lyZWQgY29udHJvbHMsIHdpdGggYSB0b3RhbCBsZW5ndGggY2xvc2UgdG8gYnV0IG5vdCBleGNlZWRpbmcgdGhlaXIgZGlzdGFuY2UgZXN0aW1hdGUuPFwvcD5cclxuXHJcbjxwPkFmdGVyIGEgcmFjZSwgdGhleSBhcmUgYWx3YXlzIGN1cmlvdXMgYXMgdG8gd2hldGhlciB0aGV5IGNvdWxkIGhhdmUgZG9uZSBiZXR0ZXIgYnkgYWltaW5nIGZvciBhIGRpZmZlcmVudCBzdWJzZXF1ZW5jZSBvZiB0aGUgYXZhaWxhYmxlIGNvbnRyb2xzLiBZb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB0aGUgbWF4aW11bSBzY29yZSBhdmFpbGFibGUgdG8gZWFjaCBydW5uZXIgaW4gZWFjaCBvZiBhIHNlcmllcyBvZiByYWNlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBhIG51bWJlciBvZiByYWNlIHNjZW5hcmlvcy4gRWFjaCBzY2VuYXJpbyBjb25zaXN0cyBvZjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyLCBuLCB0aGUgbnVtYmVyIG9mIGNvbnRyb2xzIGluIHRoZSByYWNlICgxICZsZTsgbiAmbGU7IDMwKS48XC9saT5cclxuXHQ8bGk+biBsaW5lcyBvZiBjb250cm9sIGRhdGEsIGVhY2ggY29udGFpbmluZyB0aHJlZSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc3BhY2VzOiAmbHNxdW87eCB5IHMmcnNxdW87LCB3aGVyZSAoeCwgeSkgYXJlIHRoZSBjb29yZGluYXRlcyBpbiBtZXRyZXMgb2YgdGhlIGNvbnRyb2wgc2l0ZSAoJm1pbnVzOzUwMDAgJmxlOyB4LCB5ICZsZTsgNTAwMCkgYW5kIHMgaXMgdGhlIGNvbnRyb2wmcnNxdW87cyBzY29yZSAoMTAgJmxlOyBzICZsZTsgMjAwKS48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgZm9yIGVhY2ggcnVubmVyIGluIHRoZSByYWNlLCB0ZXJtaW5hdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIG9ubHkgJmxzcXVvOyMgMCZyc3F1bzsuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgdGhlIHJ1bm5lciZyc3F1bztzIG5hbWUgYW5kIGFuIGludGVnZXIgZCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBuYW1lIGlzIGEgc2luZ2xlIHdvcmQgb2YgdXAgdG8gNjAgY2hhcmFjdGVycywgYW5kIGQgaXMgdGhlIGRpc3RhbmNlIGluIG1ldHJlcyB0aGF0IHRoZSBydW5uZXIgY2FuIHRyYXZlbCBpbiB0aGUgdGltZSBhdmFpbGFibGUgKDAgJmxlOyBkICZsZTsgMTAwMDApLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgd2lsbCBiZSBhICZsc3F1bzswJnJzcXVvOyBvbiBhIGxpbmUgYnkgaXRzZWxmLiBUaGlzIGxpbmUgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuXHJcbjxwPlRoZSBzdGFydCBhbmQgZmluaXNoIHBvaW50cyBmb3IgZWFjaCByYWNlIGFyZSBhdCB0aGUgb3JpZ2luICgwLCAwKS4gQXNzdW1lIHRoYXQgZWFjaCBtYXAgYXJlYSBpcyBmbGF0LCBhbmQgdGhhdCB0aGUgcnVubmVycyBuYXZpZ2F0ZSBwZXJmZWN0bHkgYWxvbmcgc3RyYWlnaHQtbGluZSBwYXRocyBiZXR3ZWVuIGNvbnRyb2wgcG9pbnRzIChhbmQgdG9cL2Zyb20gdGhlIHN0YXJ0IGFuZCBmaW5pc2gpLiBUaGVuIHZpYWJsZSByb3V0ZXMgZm9yIGEgcnVubmVyIHN0YXJ0IGF0IHRoZSBvcmlnaW4sIHBhc3MgdGhyb3VnaCB0aGUgY29vcmRpbmF0ZXMgb2Ygc29tZSBzdWJzZXF1ZW5jZSBvZiB0aGUgYXZhaWxhYmxlIGNvbnRyb2xzIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IGFwcGVhciBpbiB0aGUgaW5wdXQsIGFuZCByZXR1cm4gdG8gdGhlIG9yaWdpbiwgYWxsIHdpdGggYSB0b3RhbCBsZW5ndGggJmxlOyBkLjxcL3A+XHJcblxyXG48cD4oQSByb3V0ZSBsb25nZXIgdGhhbiBkIG1pZ2h0IHNjb3JlIGVub3VnaCBleHRyYSBwb2ludHMgdG8gb3V0d2VpZ2ggdGhlIGxhdGVuZXNzIHBlbmFsdHksIGJ1dCB0aGUgcnVubmVycyBmaW5kIGxhdGUgZmluaXNoZXMgc28gZW1iYXJyYXNzaW5nIHRoYXQgbm9uZSBvZiB0aGVtIHdpbGwgY29uc2lkZXIgc3VjaCByb3V0ZXMgdG8gYmUgdmlhYmxlLik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZm9yIGVhY2ggc2NlbmFyaW8gd2lsbCBzdGFydCB3aXRoIGEgbGluZSAmbHNxdW87UmFjZSByJnJzcXVvOyBzdGF0aW5nIHRoZSByYWNlIG51bWJlciwgc3RhcnRpbmcgd2l0aCAxLiBUaGlzIHdpbGwgYmUgZm9sbG93ZWQgYnkgb25lIGxpbmUgZm9yIGVhY2ggb2YgdGhlIHJ1bm5lcnMgaW4gdGhlIHJhY2UsIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IGFwcGVhciBpbiB0aGUgcmFjZSBzY2VuYXJpbywgY29udGFpbmluZyB0aGUgcnVubmVyJnJzcXVvO3MgbmFtZSBhbmQgdGhlIHNjb3JlIG9mIHRoZSBoaWdoZXN0IHNjb3JpbmcgdmlhYmxlIHJvdXRlIGF2YWlsYWJsZSB0byB0aGF0IHJ1bm5lciwgZm9ybWF0dGVkIGFzICZsc3F1bztuYW1lOiBzY29yZSZyc3F1bzsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2006 O번

  • 문제를 번역한 사람: kks227

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)