시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 330 108 85 42.079%

문제

자동차 여러 대가 그림 1과 같이 한 줄로 이동하고 있다. 각 자동차의 색상은 한 글자로 나타내며, 인접한 두 차 사이의 거리는 1이다. 그림 1에는 각 차의 위치도 적혀져 있다.

그림 1. 도로를 이동하는 여러 가지 색상의 자동차

각각의 색상 c에 대해서, location(c)는 색상 c로 색칠된 모든 차의 위치의 집합을 나타낸다. 색상의 길이 L(c)는 다음과 같이 정의한다.

\(L(c) = max \left\{location(c)\right\} - min \left\{location(c)\right\}\)

예를 들어, 그림 1에서 location(G) = {1,5,6}, location(Y) = {2,7}, location(B) = {3}, location(R) = {4,8}이 되고, 각 색상의 길이와 모든 길이의 합은 아래와 같다.

색상 G Y B R 합계
L(c) 5 5 0 4 14

경주시의 거의 모든 도로는 적어도 500년 전에 건설되었다. 비가 온 이후에는 도로에 물 웅덩이가 많이 생기고, 여행객은 도로 상황이 좋지 않음을 오랜 기간 항의했다. 경주시는 문화재 보호에 더 집중하고 있기 때문에, 이번에 도로 하나만 수리를 하려고 한다. 이번에 고칠 도로는 4차선 도로이고, 각 방향으로 2차선 도로이다.

수리를 하는 도중에 도로를 완전히 통제하면, 시민들의 불편은 매우 심해지게 된다. 따라서, 각 방향으로 한 차선씩 먼저 통제하고 수리를 하려고 한다. 수리되는 구간에서 도로는 1차선으로 좁아지게 되고, 2차선으로 이동하던 자동차는 1차선으로 합쳐져야 한다.

예를 들어, 그림 2와 같이 두 차선이 그림 3과 같이 한 차선으로 합쳐지는 경우를 생각해보자. 같은 색 자동차를 구분하기 위해, 각 차에 숫자를 붙였다.

그림 2. 차선이 합쳐지기 전에 두 차선을 이동하는 자동차

그림 3은 한 차선으로 합쳐지는 두 시나리오를 나타낸다. 그림 3에서 볼 수 있듯이, 한 차선의 모든 차가 진입한 이후에 다른 차선의 차가 진입할 필요는 없다. 서로 번갈아가면서 한 차선으로 진입할 수 있다. 합쳐진 이후에도 자동차 사이의 거리는 1이다.

합쳐진 이후 (시나리오 1):

합쳐진 이후 (시나리오 2):

그림 3. 한 차선으로 합쳐진 이후의 도로 상황 (두 가지)

그림 3에 나온 각각의 시나리오에 대해서, 색상의 길이와 합을 구해보면 아래와 같다.

색상 G Y B R 합계
L(c): 시나리오 1 7 3 7 2 19
L(c): 시나리오 2 1 7 3 1 12

그림 3에 나와있는 방법 말고도 차선을 합치는 방법은 여러 가지가 있다.

합쳐지기 전, 두 차선의 자동차 색상 정보가 주어진다. 이때, 색상의 길이의 합이 가장 최소가 되게 차선을 합치는 방법을 찾는 프로그램을 작성하시오.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 한 차선의 자동차 색상 정보가 주어지며, 둘째 줄에는 다른 차선의 자동차 색상 정보가 주어진다. 각 색상은 알파벳 대문자로 나타낸다. 즉, 색상의 개수는 26개이다. 한 차선에 있는 자동차의 수는 1보다 크거나 같으면, 5,000을 넘지 않는다.

출력

각 테스트 케이스 마다, 한 차선으로 합쳐진 이후의 색상 길이의 합의 최솟값을 출력한다.

예제 입력 1

2
AAABBCY
ABBBCDEEY
GBBY
YRRGB

예제 출력 1

10
12
W3sicHJvYmxlbV9pZCI6Ijg5MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzlcdWMwYzFcdWM3NTggXHVhZTM4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3OTBcdWIzZDlcdWNjMjggXHVjNWVjXHViN2VjIFx1YjMwMFx1YWMwMCBcdWFkZjhcdWI5YmMgMVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjNzkwXHViM2Q5XHVjYzI4XHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc0MCBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWNjMjggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI5YmMgMVx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjYzI4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjNjNCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjlweDsgd2lkdGg6NDYwcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAxLiBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1Yzc5MFx1YjNkOVx1Y2MyODxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjMGM5XHVjMGMxIGNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBsb2NhdGlvbihjKVx1YjI5NCBcdWMwYzlcdWMwYzEgY1x1Yjg1YyBcdWMwYzlcdWNlNjBcdWI0MWMgXHViYWE4XHViNGUwIFx1Y2MyOFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjMGM5XHVjMGMxXHVjNzU4IFx1YWUzOFx1Yzc3NCBMKGMpXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XFwoTChjKSA9IG1heCBcXGxlZnRcXHtsb2NhdGlvbihjKVxccmlnaHRcXH0mbmJzcDstIG1pbiBcXGxlZnRcXHtsb2NhdGlvbihjKVxccmlnaHRcXH1cXCk8XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhZGY4XHViOWJjIDFcdWM1ZDBcdWMxMWMgbG9jYXRpb24oRykgPSB7MSw1LDZ9LCBsb2NhdGlvbihZKSA9IHsyLDd9LCBsb2NhdGlvbihCKSA9IHszfSwgbG9jYXRpb24oUikgPSB7NCw4fVx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YWMwMSBcdWMwYzlcdWMwYzFcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyNSVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWMwYzlcdWMwYzE8XC90aD5cclxuXHRcdFx0PHRoPkc8XC90aD5cclxuXHRcdFx0PHRoPlk8XC90aD5cclxuXHRcdFx0PHRoPkI8XC90aD5cclxuXHRcdFx0PHRoPlI8XC90aD5cclxuXHRcdFx0PHRoPlx1ZDU2OVx1YWNjNDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+TChjKTxcL3RoPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YWNiZFx1YzhmY1x1YzJkY1x1Yzc1OCBcdWFjNzBcdWM3NTggXHViYWE4XHViNGUwIFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgNTAwXHViMTQ0IFx1YzgwNFx1YzVkMCBcdWFjNzRcdWMxMjRcdWI0MThcdWM1YzhcdWIyZTQuIFx1YmU0NFx1YWMwMCBcdWM2MjggXHVjNzc0XHVkNmM0XHVjNWQwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWJiM2MgXHVjNmM1XHViMzY5XHVjNzc0XHVhYzAwIFx1YjljZVx1Yzc3NCBcdWMwZGRcdWFlMzBcdWFjZTAsIFx1YzVlY1x1ZDU4OVx1YWMxZFx1Yzc0MCBcdWIzYzRcdWI4NWMgXHVjMGMxXHVkNjY5XHVjNzc0IFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWM3NGNcdWM3NDQgXHVjNjI0XHViNzljIFx1YWUzMFx1YWMwNCBcdWQ1NmRcdWM3NThcdWQ1ODhcdWIyZTQuIFx1YWNiZFx1YzhmY1x1YzJkY1x1YjI5NCBcdWJiMzhcdWQ2NTRcdWM3YWMgXHViY2Y0XHVkNjM4XHVjNWQwIFx1YjM1NCBcdWM5ZDFcdWM5MTFcdWQ1NThcdWFjZTAgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc0XHViYzg4XHVjNWQwIFx1YjNjNFx1Yjg1YyBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjMjE4XHViOWFjXHViOTdjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWFjZTBcdWNlNjAgXHViM2M0XHViODVjXHViMjk0IDRcdWNjMjhcdWMxMjAgXHViM2M0XHViODVjXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIDJcdWNjMjhcdWMxMjAgXHViM2M0XHViODVjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWI5YWNcdWI5N2MgXHVkNTU4XHViMjk0IFx1YjNjNFx1YzkxMVx1YzVkMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNjQ0XHVjODA0XHVkNzg4IFx1ZDFiNVx1YzgxY1x1ZDU1OFx1YmE3NCwgXHVjMmRjXHViYmZjXHViNGU0XHVjNzU4IFx1YmQ4OFx1ZDNiOFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjMmVjXHVkNTc0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFjMDEgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1ZDU1YyBcdWNjMjhcdWMxMjBcdWM1MjkgXHViYTNjXHVjODAwIFx1ZDFiNVx1YzgxY1x1ZDU1OFx1YWNlMCBcdWMyMThcdWI5YWNcdWI5N2MgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMjE4XHViOWFjXHViNDE4XHViMjk0IFx1YWQ2Y1x1YWMwNFx1YzVkMFx1YzExYyBcdWIzYzRcdWI4NWNcdWIyOTQgMVx1Y2MyOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM4ODFcdWM1NDRcdWM5YzBcdWFjOGMgXHViNDE4XHVhY2UwLCAyXHVjYzI4XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjM1OCBcdWM3OTBcdWIzZDlcdWNjMjhcdWIyOTQgMVx1Y2MyOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWQ1NjlcdWNjZDBcdWM4MzhcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFkZjhcdWI5YmMgMlx1YzY0MCBcdWFjMTlcdWM3NzQgXHViNDUwIFx1Y2MyOFx1YzEyMFx1Yzc3NCBcdWFkZjhcdWI5YmMgM1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWQ1NjlcdWNjZDBcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVhYzE5XHVjNzQwIFx1YzBjOSBcdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHVhZDZjXHViZDg0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhYzAxIFx1Y2MyOFx1YzVkMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViZDk5XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE3cHg7IHdpZHRoOjMyM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdWFkZjhcdWI5YmMgMi4gXHVjYzI4XHVjMTIwXHVjNzc0IFx1ZDU2OVx1Y2NkMFx1YzljMFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViNDUwIFx1Y2MyOFx1YzEyMFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAzXHVjNzQwIFx1ZDU1YyBcdWNjMjhcdWMxMjBcdWM3M2NcdWI4NWMgXHVkNTY5XHVjY2QwXHVjOWMwXHViMjk0IFx1YjQ1MCBcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFkZjhcdWI5YmMgM1x1YzVkMFx1YzExYyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjRlZlx1Yzc3NCwgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjYzI4XHVhYzAwIFx1YzljNFx1Yzc4NVx1ZDU1YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHViMmU0XHViOTc4IFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWNjMjhcdWFjMDAgXHVjOWM0XHVjNzg1XHVkNTYwIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWJjODhcdWFjMDhcdWM1NDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM5YzRcdWM3ODVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTY5XHVjY2QwXHVjOWM0IFx1Yzc3NFx1ZDZjNFx1YzVkMFx1YjNjNCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NjlcdWNjZDBcdWM5YzQgXHVjNzc0XHVkNmM0IChcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjQgMSk6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NsMzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NTVweDsgd2lkdGg6NTc2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTY5XHVjY2QwXHVjOWM0IFx1Yzc3NFx1ZDZjNCAoXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0IDIpOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbDMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjUxcHg7IHdpZHRoOjU3M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdWFkZjhcdWI5YmMgMy4gXHVkNTVjIFx1Y2MyOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWQ1NjlcdWNjZDBcdWM5YzQgXHVjNzc0XHVkNmM0XHVjNzU4IFx1YjNjNFx1Yjg1YyBcdWMwYzFcdWQ2NjkgKFx1YjQ1MCBcdWFjMDBcdWM5YzApPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAzXHVjNWQwIFx1YjA5OFx1YzYyOCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozNSVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWMwYzlcdWMwYzE8XC90aD5cclxuXHRcdFx0PHRoPkc8XC90aD5cclxuXHRcdFx0PHRoPlk8XC90aD5cclxuXHRcdFx0PHRoPkI8XC90aD5cclxuXHRcdFx0PHRoPlI8XC90aD5cclxuXHRcdFx0PHRoPlx1ZDU2OVx1YWNjNDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+TChjKTogXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0IDE8XC90aD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjE5PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkwoYyk6IFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNCAyPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVhZGY4XHViOWJjIDNcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NSBcdWI5ZDBcdWFjZTBcdWIzYzQgXHVjYzI4XHVjMTIwXHVjNzQ0IFx1ZDU2OVx1Y2U1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU2OVx1Y2NkMFx1YzljMFx1YWUzMCBcdWM4MDQsIFx1YjQ1MCBcdWNjMjhcdWMxMjBcdWM3NTggXHVjNzkwXHViM2Q5XHVjYzI4IFx1YzBjOVx1YzBjMSBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVhYzhjIFx1Y2MyOFx1YzEyMFx1Yzc0NCBcdWQ1NjlcdWNlNThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFRcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjMGM5XHVjMGMxIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHViOTc4IFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjMGM5XHVjMGMxIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMwYzlcdWMwYzFcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzk4OSwgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAyNlx1YWMxY1x1Yzc3NFx1YjJlNC4mbmJzcDtcdWQ1NWMgXHVjYzI4XHVjMTIwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWIzZDlcdWNjMjhcdWM3NTggXHVjMjE4XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YzczY1x1YmE3NCwgNSwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1ZDU1YyBcdWNjMjhcdWMxMjBcdWM3M2NcdWI4NWMgXHVkNTY5XHVjY2QwXHVjOWM0IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWMwYzlcdWMwYzEgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb2xvciBMZW5ndGgiLCJkZXNjcmlwdGlvbiI6IjxwPkNhcnMgcGFpbnRlZCBpbiBkaWZmZXJlbnQgY29sb3JzIGFyZSBtb3ZpbmcgaW4gYSByb3cgb24gdGhlIHJvYWQgYXMgc2hvd24gaW4gRmlndXJlIDEuIFRoZSBjb2xvciBvZiBlYWNoIGNhciBpcyByZXByZXNlbnRlZCBieSBhIHNpbmdsZSBjaGFyYWN0ZXIgYW5kIHRoZSBkaXN0YW5jZSBvZiB0d28gYWRqYWNlbnQgY2FycyBpcyBhc3N1bWVkIHRvIGJlIDEuIEZpZ3VyZSAxIHNob3dzIGFuIGV4YW1wbGUgb2Ygc3VjaCBjYXJzIG9uIHRoZSByb2FkLiBGb3IgY29udmVuaWVuY2UsIHRoZSBudW1iZXJzIGluIEZpZ3VyZSAxIHJlcHJlc2VudCB0aGUgbG9jYXRpb25zIG9mIGVhY2ggY2FyLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjlweDsgdGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjQ2MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5GaWd1cmUgMS4gQ2FycyBpbiBkaWZmZXJlbnQgY29sb3JzIG9uIHRoZSByb2FkJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBhbnkgY29sb3IgYywgbG9jYXRpb24oYykgcmVwcmVzZW50cyBzZXQgb2YgdGhlIGxvY2F0aW9ucyBvZiB0aGUgY2FycyBwYWludGVkIGluIGNvbG9yIGMgYW5kIGNvbG9yIGxlbmd0aCBMKGMpIGlzIGRlZmluZWQgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XFwoTChjKSA9IG1heCBcXGxlZnRcXHtsb2NhdGlvbihjKVxccmlnaHRcXH0mbmJzcDstIG1pbiBcXGxlZnRcXHtsb2NhdGlvbihjKVxccmlnaHRcXH1cXCk8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGFjY29yZGluZyB0byBGaWd1cmUgMSwgbG9jYXRpb24oRykgPSB7MSw1LDZ9LCBsb2NhdGlvbihZKSA9IHsyLDd9LCBsb2NhdGlvbihCKSA9IHszfSwgYW5kIGxvY2F0aW9uKFIpID17NCwgOH0uIEhlbmNlIHRoZSBjb2xvciBsZW5ndGggb2YgZWFjaCBjb2xvciBhbmQgdGhlIHN1bSBvZiB0aGUgY29sb3IgbGVuZ3RocyBhcmUgYXMgZm9sbG93cy4mbmJzcDs8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjI1JVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkNvbG9yPFwvdGg+XHJcblx0XHRcdDx0aD5HPFwvdGg+XHJcblx0XHRcdDx0aD5ZPFwvdGg+XHJcblx0XHRcdDx0aD5CPFwvdGg+XHJcblx0XHRcdDx0aD5SPFwvdGg+XHJcblx0XHRcdDx0aD5TdW08XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkwoYyk8XC90aD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjE0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5JbiBHeWVvbmdqdSBDaXR5LCBhbG1vc3QgYWxsIHRoZSByb2FkcyBpbmNsdWRpbmcgdGhlIG1haW4gc3RyZWV0IG9mIHRoZSBjaXR5IHdlcmUgY29uc3RydWN0ZWQgbW9yZSB0aGFuIDUwMCB5ZWFycyBhZ28uIFRoZSByb2FkcyBhcmUgc28gb2xkIHRoYXQgdGhlcmUgYXJlIGEgbG90IG9mIHB1ZGRsZXMgYWZ0ZXIgcmFpbi4gVmlzaXRvcnMgaGF2ZSBjb21wbGFpbmVkIGFib3V0IHRoZSBiYWQgY29uZGl0aW9uIG9mIHRoZSByb2FkcyBmb3IgbWFueSB5ZWFycy4gRHVlIHRvIHRoZSBsaW1pdGVkIGJ1ZGdldCwgdGhlIG1heW9yIG9mIHRoZSBjaXR5IGRlY2lkZWQgdG8gcmVwYWlyIGZpcnN0bHkgdGhlIG1haW4gc3RyZWV0IG9mIHRoZSBjaXR5LCB3aGljaCBpcyBhIGZvdXItbGFuZSByb2FkLCB0d28gbGFuZXMgZm9yIGVhY2ggZGlyZWN0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCBzaW5jZSB0aGUgbWFpbiBzdHJlZXQgaXMgYSBiYWNrYm9uZSBvZiB0aGUgY2l0eSwgaXQgc2hvdWxkIG5vdCBiZSBibG9ja2VkIGNvbXBsZXRlbHkgd2hpbGUgaXQgaXMgdW5kZXIgcmVwYWlyLCBvciBpdCBpcyBleHBlY3RlZCB0aGF0IHNlcmlvdXMgdHJhZmZpYyBqYW1zIHdpbGwgb2NjdXIgb24gYWxtb3N0IGFsbCB0aGUgb3RoZXIgcm9hZHMgaW4gdGhlIGNpdHkuIFRvIGFsbG93IGNhcnMgdG8gdXNlIHRoZSBtYWluIHN0cmVldCBkdXJpbmcgdGhlIHJlcGFpciBwZXJpb2QsIHRoZSBjaXR5IGRlY2lkZWQgdG8gYmxvY2sgb25seSB0d28gbGFuZXMsIG9uZSBsYW5lIGZvciBlYWNoIGRpcmVjdGlvbi4gSGVuY2UsIHRoZSBjYXJzIGluIHRoZSB0d28gbGFuZXMgZm9yIGVhY2ggZGlyZWN0aW9uIHNob3VsZCBtZXJnZSBpbnRvIGEgc2luZ2xlIGxhbmUgYmVmb3JlIHRoZSBibG9ja2VkIHpvbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgYXMgc2hvd24gaW4gRmlndXJlIDIsIGNhcnMgaW4gdGhlIHR3byBsYW5lcyBtZXJnZSBpbnRvIGEgc2luZ2xlIGxhbmUgYXMgc2hvd24gaW4gRmlndXJlIDMuIFRvIGRpZmZlcmVudGlhdGUgdGhlIGNhcnMgaW4gdGhlIHNhbWUgY29sb3IsIGEgdW5pcXVlIGlkZW50aWZpZXIgaXMgYXNzaWduZWQgdG8gZWFjaCBjYXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NsMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTdweDsgdGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjMyM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5GaWd1cmUgMi4gQ2FycyBtb3ZpbmcgaW4gdHdvIGxhbmVzIGJlZm9yZSBtZXJnaW5nJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAzIHNob3dzIHR3byBkaWZmZXJlbnQgbWVyZ2luZyBzY2VuYXJpb3MgYWZ0ZXIgbWVyZ2luZyB0aGUgY2FycyBmcm9tIHRoZSB0d28gbGFuZXMuIEFzIHNob3duIGluIEZpZ3VyZSAzLCBjYXJzIGluIHRoZSB0d28gbGFuZXMgZG8gbm90IG5lY2Vzc2FyaWx5IG1lcmdlIG9uZSBieSBvbmUgZnJvbSBlYWNoIGxhbmUuIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBhZGphY2VudCBjYXJzIGFmdGVyIG1lcmdpbmcgaXMgYWxzbyBhc3N1bWVkIDEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIG1lcmdpbmcgKFNjZW5hcmlvIDEpOiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbDMxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjU1cHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo1NzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BZnRlciBtZXJnaW5nIChTY2VuYXJpbyAyKTombmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2wzMi5wbmdcIiBzdHlsZT1cImhlaWdodDo1MXB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NTczcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPkZpZ3VyZSAzLiBUd28gZGlmZmVyZW50IG1lcmdpbmcgc2NlbmFyaW9zJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIG1lcmdpbmcgc2NlbmFyaW8gc2hvd24gaW4gRmlndXJlIDMsIHRoZSBjb2xvciBsZW5ndGggZm9yIGVhY2ggY29sb3IgYW5kIHRoZSBzdW0gb2YgdGhlIGNvbG9yIGxlbmd0aHMgYXJlIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozNSVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5Db2xvcjxcL3RoPlxyXG5cdFx0XHQ8dGg+RzxcL3RoPlxyXG5cdFx0XHQ8dGg+WTxcL3RoPlxyXG5cdFx0XHQ8dGg+QjxcL3RoPlxyXG5cdFx0XHQ8dGg+UjxcL3RoPlxyXG5cdFx0XHQ8dGg+U3VtPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5MKGMpOiBTY2VuYXJpbyAxPFwvdGg+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4xOTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5MKGMpOiBTY2VuYXJpbyAyPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+QXMgeW91IGNhbiBpbWFnaW5lLCB0aGVyZSBhcmUgbWFueSBkaWZmZXJlbnQgd2F5cyBvZiBtZXJnaW5nIG90aGVyIHRoYW4gdGhlIHR3byBleGFtcGxlcyBzaG93biBpbiBGaWd1cmUgMy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdHdvIGNoYXJhY3RlciBzdHJpbmdzIHdoaWNoIHJlcHJlc2VudCB0aGUgY29sb3IgaW5mb3JtYXRpb24gb2YgdGhlIGNhcnMgaW4gdGhlIHR3byBsYW5lcyBiZWZvcmUgbWVyZ2luZywgd3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIHN1bSBvZiBjb2xvciBsZW5ndGhzIG9idGFpbmVkIGZyb20gdGhlIGNoYXJhY3RlciBzdHJpbmcsIHdoaWNoIGlzIHRoZSBjb2xvciBpbmZvcm1hdGlvbiBvZiBjYXJzIGFmdGVyIG1lcmdpbmcsIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIGNvbG9yIGxlbmd0aHMgaXMgbWluaW1pemVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gbGluZXMuIEluIHRoZSBmaXJzdCBsaW5lLCBhIGNoYXJhY3RlciBzdHJpbmcgb2YgbGVuZ3RoIG4gKDEgJmxlOyBuICZsZTsgNSwwMDApIHRoYXQgaXMgdGhlIGNvbG9yIGluZm9ybWF0aW9uIG9mIHRoZSBjYXJzIGluIG9uZSBsYW5lIGJlZm9yZSBtZXJnaW5nIGlzIGdpdmVuLiBJbiB0aGUgc2Vjb25kIGxpbmUsIGEgY2hhcmFjdGVyIHN0cmluZyBvZiBsZW5ndGggbSAoMSAmbGU7IG0gJmxlOyA1LDAwMCkgdGhhdCBpcyB0aGUgY29sb3IgaW5mb3JtYXRpb24gb2YgdGhlIGNhcnMgaW4gdGhlIG90aGVyIGxhbmUgaXMgZ2l2ZW4uIEV2ZXJ5IGNvbG9yIGlzIHJlcHJlc2VudGVkIGFzIGFuIHVwcGVyY2FzZSBsZXR0ZXIgaW4gRW5nbGlzaCwgaGVuY2UgdGhlIG51bWJlciBvZiBjb2xvcnMgaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDI2LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgc3VtIG9mIGNvbG9yIGxlbmd0aHMgYWZ0ZXIgbWVyZ2luZyB0aGUgY2FycyBpbiB0aGUgdHdvIGxhbmVzIG9wdGltYWxseSBhcyBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 C번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: shgmldbs