시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 323 107 84 42.211%

문제

자동차 여러 대가 그림 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+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjlweDsgd2lkdGg6NDYwcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAxLiBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMCBcdWMwYzlcdWMwYzFcdWM3NTggXHVjNzkwXHViM2Q5XHVjYzI4PFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwYzlcdWMwYzEgY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIGxvY2F0aW9uKGMpXHViMjk0IFx1YzBjOVx1YzBjMSBjXHViODVjIFx1YzBjOVx1Y2U2MFx1YjQxYyBcdWJhYThcdWI0ZTAgXHVjYzI4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMwYzlcdWMwYzFcdWM3NTggXHVhZTM4XHVjNzc0IEwoYylcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cXChMKGMpID0gbWF4IFxcbGVmdFxce2xvY2F0aW9uKGMpXFxyaWdodFxcfSZuYnNwOy0gbWluIFxcbGVmdFxce2xvY2F0aW9uKGMpXFxyaWdodFxcfVxcKTxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFkZjhcdWI5YmMgMVx1YzVkMFx1YzExYyBsb2NhdGlvbihHKSA9IHsxLDUsNn0sIGxvY2F0aW9uKFkpID0gezIsN30sIGxvY2F0aW9uKEIpID0gezN9LCBsb2NhdGlvbihSKSA9IHs0LDh9XHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVhYzAxIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViYWE4XHViNGUwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjI1JVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlx1YzBjOVx1YzBjMTxcL3RoPlxyXG5cdFx0XHQ8dGg+RzxcL3RoPlxyXG5cdFx0XHQ8dGg+WTxcL3RoPlxyXG5cdFx0XHQ8dGg+QjxcL3RoPlxyXG5cdFx0XHQ8dGg+UjxcL3RoPlxyXG5cdFx0XHQ8dGg+XHVkNTY5XHVhY2M0PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5MKGMpPFwvdGg+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD40PFwvdGQ+XHJcblx0XHRcdDx0ZD4xNDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVhY2JkXHVjOGZjXHVjMmRjXHVjNzU4IFx1YWM3MFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCA1MDBcdWIxNDQgXHVjODA0XHVjNWQwIFx1YWM3NFx1YzEyNFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViZTQ0XHVhYzAwIFx1YzYyOCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNWQwIFx1YmIzYyBcdWM2YzVcdWIzNjlcdWM3NzRcdWFjMDAgXHViOWNlXHVjNzc0IFx1YzBkZFx1YWUzMFx1YWNlMCwgXHVjNWVjXHVkNTg5XHVhYzFkXHVjNzQwIFx1YjNjNFx1Yjg1YyBcdWMwYzFcdWQ2NjlcdWM3NzQgXHVjODhiXHVjOWMwIFx1YzU0YVx1Yzc0Y1x1Yzc0NCBcdWM2MjRcdWI3OWMgXHVhZTMwXHVhYzA0IFx1ZDU2ZFx1Yzc1OFx1ZDU4OFx1YjJlNC4gXHVhY2JkXHVjOGZjXHVjMmRjXHViMjk0IFx1YmIzOFx1ZDY1NFx1YzdhYyBcdWJjZjRcdWQ2MzhcdWM1ZDAgXHViMzU0IFx1YzlkMVx1YzkxMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3NzRcdWJjODhcdWM1ZDAgXHViM2M0XHViODVjIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWMyMThcdWI5YWNcdWI5N2MgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViYzg4XHVjNWQwIFx1YWNlMFx1Y2U2MCBcdWIzYzRcdWI4NWNcdWIyOTQgNFx1Y2MyOFx1YzEyMCBcdWIzYzRcdWI4NWNcdWM3NzRcdWFjZTAsIFx1YWMwMSBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgMlx1Y2MyOFx1YzEyMCBcdWIzYzRcdWI4NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YjlhY1x1Yjk3YyBcdWQ1NThcdWIyOTQgXHViM2M0XHVjOTExXHVjNWQwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM2NDRcdWM4MDRcdWQ3ODggXHVkMWI1XHVjODFjXHVkNTU4XHViYTc0LCBcdWMyZGNcdWJiZmNcdWI0ZTRcdWM3NTggXHViZDg4XHVkM2I4XHVjNzQwIFx1YjllNFx1YzZiMCBcdWMyZWNcdWQ1NzRcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWMwMSBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1YzUyOSBcdWJhM2NcdWM4MDAgXHVkMWI1XHVjODFjXHVkNTU4XHVhY2UwIFx1YzIxOFx1YjlhY1x1Yjk3YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMyMThcdWI5YWNcdWI0MThcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNWQwXHVjMTFjIFx1YjNjNFx1Yjg1Y1x1YjI5NCAxXHVjYzI4XHVjMTIwXHVjNzNjXHViODVjIFx1Yzg4MVx1YzU0NFx1YzljMFx1YWM4YyBcdWI0MThcdWFjZTAsIDJcdWNjMjhcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMzU4IFx1Yzc5MFx1YjNkOVx1Y2MyOFx1YjI5NCAxXHVjYzI4XHVjMTIwXHVjNzNjXHViODVjIFx1ZDU2OVx1Y2NkMFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWRmOFx1YjliYyAyXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWI0NTAgXHVjYzI4XHVjMTIwXHVjNzc0IFx1YWRmOFx1YjliYyAzXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWQ1NWMgXHVjYzI4XHVjMTIwXHVjNzNjXHViODVjIFx1ZDU2OVx1Y2NkMFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWFjMTlcdWM3NDAgXHVjMGM5IFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yjk3YyBcdWFkNmNcdWJkODRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWFjMDEgXHVjYzI4XHVjNWQwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJkOTlcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NsMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTdweDsgd2lkdGg6MzIzcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAyLiBcdWNjMjhcdWMxMjBcdWM3NzQgXHVkNTY5XHVjY2QwXHVjOWMwXHVhZTMwIFx1YzgwNFx1YzVkMCBcdWI0NTAgXHVjYzI4XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWM3OTBcdWIzZDlcdWNjMjg8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWJjIDNcdWM3NDAgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWQ1NjlcdWNjZDBcdWM5YzBcdWIyOTQgXHViNDUwIFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YWRmOFx1YjliYyAzXHVjNWQwXHVjMTFjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViNGVmXHVjNzc0LCBcdWQ1NWMgXHVjYzI4XHVjMTIwXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWNjMjhcdWFjMDAgXHVjOWM0XHVjNzg1XHVkNTVjIFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjYzI4XHVjMTIwXHVjNzU4IFx1Y2MyOFx1YWMwMCBcdWM5YzRcdWM3ODVcdWQ1NjAgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC4gXHVjMTFjXHViODVjIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWQ1NWMgXHVjYzI4XHVjMTIwXHVjNzNjXHViODVjIFx1YzljNFx1Yzc4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NjlcdWNjZDBcdWM5YzQgXHVjNzc0XHVkNmM0XHVjNWQwXHViM2M0IFx1Yzc5MFx1YjNkOVx1Y2MyOCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU2OVx1Y2NkMFx1YzljNCBcdWM3NzRcdWQ2YzQgKFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNCAxKTo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2wzMS5wbmdcIiBzdHlsZT1cImhlaWdodDo1NXB4OyB3aWR0aDo1NzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1NjlcdWNjZDBcdWM5YzQgXHVjNzc0XHVkNmM0IChcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjQgMik6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NsMzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NTFweDsgd2lkdGg6NTczcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAzLiBcdWQ1NWMgXHVjYzI4XHVjMTIwXHVjNzNjXHViODVjIFx1ZDU2OVx1Y2NkMFx1YzljNCBcdWM3NzRcdWQ2YzRcdWM3NTggXHViM2M0XHViODVjIFx1YzBjMVx1ZDY2OSAoXHViNDUwIFx1YWMwMFx1YzljMCk8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWJjIDNcdWM1ZDAgXHViMDk4XHVjNjI4IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMwYzlcdWMwYzFcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWJhNzQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjM1JVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlx1YzBjOVx1YzBjMTxcL3RoPlxyXG5cdFx0XHQ8dGg+RzxcL3RoPlxyXG5cdFx0XHQ8dGg+WTxcL3RoPlxyXG5cdFx0XHQ8dGg+QjxcL3RoPlxyXG5cdFx0XHQ8dGg+UjxcL3RoPlxyXG5cdFx0XHQ8dGg+XHVkNTY5XHVhY2M0PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5MKGMpOiBcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjQgMTxcL3RoPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+TChjKTogXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0IDI8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWFkZjhcdWI5YmMgM1x1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1IFx1YjlkMFx1YWNlMFx1YjNjNCBcdWNjMjhcdWMxMjBcdWM3NDQgXHVkNTY5XHVjZTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTY5XHVjY2QwXHVjOWMwXHVhZTMwIFx1YzgwNCwgXHViNDUwIFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjMGM5XHVjMGMxIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVhYzhjIFx1Y2MyOFx1YzEyMFx1Yzc0NCBcdWQ1NjlcdWNlNThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFRcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjMGM5XHVjMGMxIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHViOTc4IFx1Y2MyOFx1YzEyMFx1Yzc1OCBcdWM3OTBcdWIzZDlcdWNjMjggXHVjMGM5XHVjMGMxIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMwYzlcdWMwYzFcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzk4OSwgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAyNlx1YWMxY1x1Yzc3NFx1YjJlNC4mbmJzcDtcdWQ1NWMgXHVjYzI4XHVjMTIwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWIzZDlcdWNjMjhcdWM3NTggXHVjMjE4XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YzczY1x1YmE3NCwgNSwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1ZDU1YyBcdWNjMjhcdWMxMjBcdWM3M2NcdWI4NWMgXHVkNTY5XHVjY2QwXHVjOWM0IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWMwYzlcdWMwYzEgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+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