시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 580 300 236 51.868%

문제

새로운 잠금 장치가 개발되었다.

이 장치는 열리거나 닫힌 상태를 갖는 여러 스위치(s1, s,.., si-1, si)들로 이루어져 있으며, 각각의 스위치는 0 또는 1의 상태를 갖는다. 따라서, 각 장치는 0과 1로 이루어진 스위치 배열로 나타낼 수 있다.

다음 표는 8개의 스위치를 가진 스위치 배열의 예제이다.

switch s1 s2 s3 s4 s5 s6 s7 s8
state 0 1 1 0 1 1 0 0

N개의 스위치를 가진 배열의 각 스위치를 작동시키는 규칙은 다음과 같다.

  • 규칙 1) SN은 아무 때나 토글하여 상태를 바꿀 수 있다.
  • 규칙 2) Si+1 = 1이며 Si+2, Si+3, ..., SN-1, SN은 모두 0일 때, Si를 토글하여 상태를 바꿀 수 있다. 이 규칙은 스위치 Si+2, Si+3, ..., SN-1, SN가 없을 때도 적용된다. 예를 들어, SN-1은 SN이 1이기만 하면 토글할 수 있다.
  • 규칙 3) 한 번에 하나의 스위치만 토글할 수 있다.

모든 스위치의 상태가 0일 때 이 장치는 열린다.

위의 규칙에 따라 배열을 모두 0으로 바꾸는 최소 토글 횟수를 구하는 것이 당신의 과제이다.

아래의 표는 배열 '1111' 을 '0000' 으로 바꾸는 최소 횟수의 연산을 나타낸 것이다. '1111' 의 경우, 최소 10번의 연산으로 배열을 '0000' 으로 만들 수 있다.

operation s1 s2 s3 s4
0 1 1 1 1
1 1 1 0 1
2 1 1 0 0
3 0 1 0 0
4 0 1 0 1
5 0 1 1 1
6 0 1 1 0
7 0 0 1 0
8 0 0 1 1
9 0 0 0 1
10 0 0 0 0

입력

입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 비트스트링 B가 한 줄에 주어지며, B의 첫 비트가 S1, 마지막 비트가 SN이다.

B의 길이는 2 ≤ |B| ≤ 31 을 만족한다.

출력

각 테스트 케이스마다 한 줄에 모든 스위치를 0으로 만들기 위한 최소의 연산 횟수를 출력한다.

예제 입력 1

5
1111
11111
1010101010
000
000000010

예제 출력 1

10
21
819
0
3
W3sicHJvYmxlbV9pZCI6IjEwMjU4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmE0XHVjNzA0XHVjZTU4IFx1YmMzMFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGM4XHViODVjXHVjNmI0IFx1YzdhMFx1YWUwOCBcdWM3YTVcdWNlNThcdWFjMDAgXHVhYzFjXHViYzFjXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjN2E1XHVjZTU4XHViMjk0IFx1YzVmNFx1YjlhY1x1YWM3MFx1YjA5OCBcdWIyZWJcdWQ3OGMgXHVjMGMxXHVkMGRjXHViOTdjIFx1YWMxNlx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVjMmE0XHVjNzA0XHVjZTU4KHM8c3ViPjE8XC9zdWI+LCZuYnNwO3M8c3ViPjImbmJzcDs8XC9zdWI+LC4uLCZuYnNwO3M8c3ViPmktMTxcL3N1Yj4sJm5ic3A7czxzdWI+aTxcL3N1Yj4pXHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgMCZuYnNwO1x1YjYxMFx1YjI5NCAxXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhYzAxIFx1YzdhNVx1Y2U1OFx1YjI5NCAwXHVhY2ZjIDFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzJhNFx1YzcwNFx1Y2U1OCZuYnNwO1x1YmMzMFx1YzVmNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1ZDQ1Y1x1YjI5NCA4XHVhYzFjXHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWFjMDBcdWM5YzQgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YmMzMFx1YzVmNFx1Yzc1OCZuYnNwO1x1YzYwOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjUwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPnN3aXRjaDxcL3RoPlxyXG5cdFx0XHQ8dGg+czxzdWI+MTxcL3N1Yj48XC90aD5cclxuXHRcdFx0PHRoPnM8c3ViPjI8XC9zdWI+PFwvdGg+XHJcblx0XHRcdDx0aD5zPHN1Yj4zPFwvc3ViPjxcL3RoPlxyXG5cdFx0XHQ8dGg+czxzdWI+NDxcL3N1Yj48XC90aD5cclxuXHRcdFx0PHRoPnM8c3ViPjU8XC9zdWI+PFwvdGg+XHJcblx0XHRcdDx0aD5zPHN1Yj42PFwvc3ViPjxcL3RoPlxyXG5cdFx0XHQ8dGg+czxzdWI+NzxcL3N1Yj48XC90aD5cclxuXHRcdFx0PHRoPnM8c3ViPjg8XC9zdWI+PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5zdGF0ZTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+Tlx1YWMxY1x1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzAwXHVjOWM0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1Yzc5MVx1YjNkOVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFkZGNcdWNlNTlcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFkZGNcdWNlNTkgMSkgUzxzdWI+TjxcL3N1Yj5cdWM3NDAgXHVjNTQ0XHViYjM0IFx1YjU0Y1x1YjA5OCBcdWQxYTBcdWFlMDBcdWQ1NThcdWM1ZWMgXHVjMGMxXHVkMGRjXHViOTdjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkZGNcdWNlNTkgMikgUzxzdWI+aSsxPFwvc3ViPiA9IDFcdWM3NzRcdWJhNzAgUzxzdWI+aSsyPFwvc3ViPiwgUzxzdWI+aSszPFwvc3ViPiwgLi4uLCBTPHN1Yj5OLTE8XC9zdWI+LCBTPHN1Yj5OPFwvc3ViPlx1Yzc0MCBcdWJhYThcdWI0NTAmbmJzcDswXHVjNzdjIFx1YjU0YywgUzxzdWI+aTxcL3N1Yj5cdWI5N2MgXHVkMWEwXHVhZTAwXHVkNTU4XHVjNWVjIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWMyYTRcdWM3MDRcdWNlNTgmbmJzcDtTPHN1Yj5pKzI8XC9zdWI+LCBTPHN1Yj5pKzM8XC9zdWI+LCAuLi4sIFM8c3ViPk4tMTxcL3N1Yj4sIFM8c3ViPk48XC9zdWI+XHVhYzAwIFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWIzYzQgXHVjODAxXHVjNmE5XHViNDFjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBTPHN1Yj5OLTE8XC9zdWI+XHVjNzQwIFM8c3ViPk48XC9zdWI+XHVjNzc0IDFcdWM3NzRcdWFlMzBcdWI5Y2MgXHVkNTU4XHViYTc0IFx1ZDFhMFx1YWUwMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkZGNcdWNlNTkgMykmbmJzcDtcdWQ1NWMgXHViYzg4XHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5Y2MgXHVkMWEwXHVhZTAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgMFx1Yzc3YyBcdWI1NGMgXHVjNzc0IFx1YzdhNVx1Y2U1OFx1YjI5NCBcdWM1ZjRcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViNTMwXHViNzdjIFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWJhYThcdWI0NTAgMFx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjZDVjXHVjMThjIFx1ZDFhMFx1YWUwMCZuYnNwO1x1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWFjZmNcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWQ0NWNcdWIyOTQgXHViYzMwXHVjNWY0ICYjMzk7MTExMSYjMzk7IFx1Yzc0NCAmIzM5OzAwMDAmIzM5OyBcdWM3M2NcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWM3NTgmbmJzcDtcdWM1ZjBcdWMwYjBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gJiMzOTsxMTExJiMzOTsmbmJzcDtcdWM3NTgmbmJzcDtcdWFjYmRcdWM2YjAsIFx1Y2Q1Y1x1YzE4YyAxMFx1YmM4OFx1Yzc1OCBcdWM1ZjBcdWMwYjBcdWM3M2NcdWI4NWMgXHViYzMwXHVjNWY0XHVjNzQ0ICYjMzk7MDAwMCYjMzk7IFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjUwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPm9wZXJhdGlvbjxcL3RoPlxyXG5cdFx0XHQ8dGg+czE8XC90aD5cclxuXHRcdFx0PHRoPnMyPFwvdGg+XHJcblx0XHRcdDx0aD5zMzxcL3RoPlxyXG5cdFx0XHQ8dGg+czQ8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjA8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjM8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjY8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+NzxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD44PFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjk8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MTA8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViZTQ0XHVkMmI4XHVjMmE0XHVkMmI4XHViOWMxIEJcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIEJcdWM3NTggXHVjY2FiIFx1YmU0NFx1ZDJiOFx1YWMwMCBTPHN1Yj4xPFwvc3ViPiwmbmJzcDtcdWI5YzhcdWM5YzBcdWI5YzkgXHViZTQ0XHVkMmI4XHVhYzAwIFM8c3ViPk48XC9zdWI+XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5CXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCZuYnNwOzIgJmxlOyB8QnwgJmxlOyAzMSBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyAwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjXHVjNzU4IFx1YzVmMFx1YzBiMCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMjU4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3dpdGNoIEFycmF5IiwiZGVzY3JpcHRpb24iOiI8cD5XZSBoYXZlIGEgbG9ja2luZyBzeXN0ZW0gd2l0aCBhIGxpbmVhciBzd2l0Y2ggYXJyYXkgczxzdWI+MTxcL3N1Yj5zPHN1Yj4yPFwvc3ViPnM8c3ViPjM8XC9zdWI+Li4uczxzdWI+aS0xPFwvc3ViPnM8c3ViPmk8XC9zdWI+IHdoZXJlIHNpIGlzIGEgdW5pdCBzd2l0Y2guIEVhY2ggdW5pdCBzd2l0Y2ggaGFzIG9uZSBvZiB0d28gZXhjbHVzaXZlIHN0YXRlcyB7MCwgMX0uIEluIHRoaXMgcHJvYmxlbSBzPHN1Yj5pPFwvc3ViPiA9IHggZGVub3RlcyB0aGUgdW5pdCBzd2l0Y2ggczxzdWI+aTxcL3N1Yj4gd2hpY2ggaGFzIGEgc3RhdGUgeCAmaXNpbjsgezAsIDF9IGV4Y2x1c2l2ZWx5LiBUaGUgZm9sbG93aW5nIFRhYmxlIHNob3dzIGEgc3RhdGUgb2Ygb25lIHN3aXRjaCBhcnJheSB3aXRoIDggdW5pdHMuPFwvcD5cclxuXHJcblxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUtYm9yZGVyZWQgdGFibGVcIiBzdHlsZT1cIndpZHRoOjUwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPnN3aXRjaDxcL3RoPlxyXG5cdFx0XHQ8dGg+czxzdWI+MTxcL3N1Yj48XC90aD5cclxuXHRcdFx0PHRoPnM8c3ViPjI8XC9zdWI+PFwvdGg+XHJcblx0XHRcdDx0aD5zPHN1Yj4zPFwvc3ViPjxcL3RoPlxyXG5cdFx0XHQ8dGg+czxzdWI+NDxcL3N1Yj48XC90aD5cclxuXHRcdFx0PHRoPnM8c3ViPjU8XC9zdWI+PFwvdGg+XHJcblx0XHRcdDx0aD5zPHN1Yj42PFwvc3ViPjxcL3RoPlxyXG5cdFx0XHQ8dGg+czxzdWI+NzxcL3N1Yj48XC90aD5cclxuXHRcdFx0PHRoPnM8c3ViPjg8XC9zdWI+PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5zdGF0ZTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+QXNzdW1lIHRoYXQgdGhlIG51bWJlciBvZiB1bml0IHN3aXRjaGVzIGlzIE4uIFlvdSBjYW4gY29udHJvbCB0aGUgdW5pdCBzd2l0Y2ggczxzdWI+aTxcL3N1Yj4gYWNjb3JkaW5nIHRvIHRoZSBmb2xsb3dpbmcgdHdvIG9wZXJhdGlvbiBydWxlcy4gTm90ZSB0aGF0IG9ubHkgb25lIHN3aXRjaCBjYW4gYmUgdG9nZ2xlZCBhdCBhIHRpbWUuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T3BlcmF0aW9uIFJ1bGUgMSkgWW91IGNhbiB0b2dnbGUgdGhlIHJpZ2h0bW9zdCBzd2l0Y2ggUzxzdWI+TjxcL3N1Yj4gYXQgYW55IHRpbWUuPFwvbGk+XHJcblx0PGxpPk9wZXJhdGlvbiBSdWxlIDIpIFlvdSBjYW4gdG9nZ2xlIHRoZSBzd2l0Y2ggc2kgb25seSBpZiBzPHN1Yj5pKzE8XC9zdWI+ID0gMSBhbmQgYWxsIGl0cyByaWdodCBzd2l0Y2hlcyBhcmUgMCwgdGhhdCBpcyBzPHN1Yj5pKzI8XC9zdWI+czxzdWI+aSszPFwvc3ViPi4uLnM8c3ViPk4tMTxcL3N1Yj5zPHN1Yj5OPFwvc3ViPiA9IDAwMC4uLjAwLiBUaGlzIHJ1bGUgd29ya3MgaWYgaSsxID0gTi4gVGhpcyBtZWFucyB0aGF0IFJ1bGUgMiB3b3JrcyBldmVuIGlmIHM8c3ViPmkrMjxcL3N1Yj5zPHN1Yj5pKzM8XC9zdWI+Li4uczxzdWI+Ti0xPFwvc3ViPnM8c3ViPk48XC9zdWI+IGRvZXMgbm90IGV4aXN0cy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgY2FuIHVubG9jayB0aGlzIHN5c3RlbSBpZiB3ZSBzZXQgczxzdWI+aTxcL3N1Yj4gPSAwIGZvciBhbGwgaSwgMSAmbGU7IGkgJmxlOyBOLiBGb3IgYSBzd2l0Y2ggYXJyYXkgZ2l2ZW4sIHlvdSBhcmUgcmVxdWlyZWQgdG8gdW5sb2NrIHRoaXMgc3lzdGVtIGJ5IG1hbmlwdWxhdGluZyBzPHN1Yj5pPFwvc3ViPiA9IDAgd2l0aCB0d28gb3BlcmF0aW9ucyBleHBsYWluZWQgYWJvdmUuIFRoZSBmb2xsb3dpbmcgdGFibGUgc2hvd3MgaG93IHRvIHVubG9jayBhIHN3aXRjaCBhcnJheSB3aXRoIHRoZSBzdGF0ZSAmIzM5OzExMTEmIzM5Oy4gSW4gdGhpcyBjYXNlIHlvdSBjYW4gdW5sb2NrIHRoaXMgc3lzdGVtIHVzaW5nIDEwIG9wZXJhdGlvbnMgd2hpY2ggaXMgdGhlIG1pbmltdW0gb3BlcmF0aW9ucyB0byB1bmxvY2suIFdlIHdhbnQgdG8ga25vdyB0aGUgbWluaW1hbCBudW1iZXIgb2Ygc3dpdGNoIG9wZXJhdGlvbiB0byB1bmxvY2sgZm9yIGEgc3dpdGNoIGFycmF5IGdpdmVuLjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NTAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+b3BlcmF0aW9uPFwvdGg+XHJcblx0XHRcdDx0aD5zMTxcL3RoPlxyXG5cdFx0XHQ8dGg+czI8XC90aD5cclxuXHRcdFx0PHRoPnMzPFwvdGg+XHJcblx0XHRcdDx0aD5zNDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MDxcL3RoPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjI8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjU8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+NjxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjg8XC90aD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+OTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4xMDxcL3RoPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgb25lIGJpbmFyeSBzdHJpbmcgQiB0byBkZW5vdGUgdGhlIHN3aXRjaCBhcnJheSBnaXZlbi4gVGhlIGZpcnN0KGxhc3QpIGNoYXJhY3RlciBvZiBCIGlzIHM8c3ViPjE8XC9zdWI+KHM8c3ViPk48XC9zdWI+KS4gVGhlIGxlbmd0aCBvZiBCIGlzIGJvdW5kZWQgYnkgMiAmbGU7IHxCfCAmbGU7IDMxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSBvZiBvcGVyYXRpb25zIHRvIHVubG9jayB0aGUgc3dpdGNoIGFycmF5IHdpdGggQiBzdGF0ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2014 J번