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

문제

과학자들은 화성에서 특이한 박테리아를 발견했고, 열심히 조사하고 있다. 그들은 박테리아의 개수가 2의 제곱수인 것을 알아챘다. 그것은 이들이 1개의 박테리아에서 시작되고, 각 박테리아는 매 세대 2개의 박테리아로 분열하기 때문이다(원래의 박테리아는 없어지는 꼴이다).

즉, 1세대는 하나의 박테리아, 2세대는 첫 세대의 박테리아가 둘로 나누어진 두 박테리아, 3세대는 또 그것이 나누어진 네 개의 박테리아, 4세대는 여덟 개, 이런 식으로 K+1세대에는 2k개의 박테리아가 있는 것을 알게 되었다.

과학자들은 그들이 찾아낸 박테리아를 1부터 2K까지 다음과 같이 번호 붙였다.

  • 이전의 K세대의 박테리아들의 후손은: {1, 2}, {3, 4}, {5, 6}, ..., {2K-1, 2K}
  • 더욱 전의 (K-1)세대의 박테리아들의 후손은: {1, 2, 3, 4}, {5, 6, 7, 8}, ..., {2K-3, 2K-2, 2K-1, 2K}
  • 훨씬 더욱 전의 (K-2)세대의 박테리아들의 후손은: {1, 2, 3, 4, 5, 6, 7, 8}, ..., {2K-7, 2K-6, 2K-5, 2K-4, 2K-3, 2K-2, 2K-1, 2K}
  • ...
  • 2세대의 두 박테리아의 후손은: {1, 2, ..., 2K-1}와 {2K-1 + 1, 2K-1 + 2, ..., 2K}

중괄호는 이들이 한 박테리아의 후손들이라는 뜻이다. 즉 어떤 조상 박테리아의 후손도 연속된 번호를 가지고 있도록 번호붙여졌다.

이때 박테리아의 순서를 바꾸더라도 여전히 위의 규칙을 만족하게 할 수 있는데, 과학자들은 그런 순서들 중 '순열의 길이'를 최소화하는 규칙을 찾으려 한다. '순열의 길이'는 이웃한 박테리아 사이의 거리를 모두 합한 것으로 정의된다.

정확히는, 모든 두 박테리아 사이에는 반발력이 존재하는데, 이 반발력은 수치로 나타내어진다. 두 박테리아 사이의 반발력은 두 박테리아가 서로 이웃해 있을 때 떨어져야 하는 최소 길이이다(두 박테리아가 이웃하지 않는다면 반발력은 아무 효과도 미치지 않는다). 모든 박테리아 쌍들의 반발력이 주어질 때, 이들을 앞서 말한 규칙을 지키면서 나열할 수 있는 최소의 길이를 구하시오.

입력

입력의 첫 줄에는 문제에서 언급한 양수 K가 주어진다(1 ≤ K ≤ 9).

그 후의 2K개의 줄에는 [0, 106] 범위에 있는 2K개의 자연수가 주어진다. 2K × 2K개의 숫자는 박테리아 쌍들 사이의 반발력을 뜻한다: 여기서 (m, n)에 있는 숫자는 박테리아 m과 n 사이의 반발력을 뜻한다. (m, n)과 (n, m)에는 같은 숫자가 들어가고, m = n일 때는 0이다.

출력

조건을 만족하면서 박테리아를 나열하는 최소의 길이만을 출력하라.

예제 입력 1

2
0 7 2 1
7 0 4 3
2 4 0 5
1 3 5 0

예제 출력 1

13

예제 입력 2

3
0 2 6 3 4 7 1 3
2 0 7 10 9 1 3 6
6 7 0 3 5 6 5 5
3 10 3 0 9 8 9 7
4 9 5 9 0 9 8 4
7 1 6 8 9 0 8 7
1 3 5 9 8 8 0 10
3 6 5 7 4 7 10 0

예제 출력 2

32
W3sicHJvYmxlbV9pZCI6IjI3OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NTRcdWMxMzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWQ2NTRcdWMxMzFcdWM1ZDBcdWMxMWMgXHVkMmI5XHVjNzc0XHVkNTVjIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWFjZTAsIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWM4NzBcdWMwYWNcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NDAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCAyXHVjNzU4IFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc3OCBcdWFjODNcdWM3NDQgXHVjNTRjXHVjNTQ0XHVjYzU4XHViMmU0LiBcdWFkZjhcdWFjODNcdWM3NDAgXHVjNzc0XHViNGU0XHVjNzc0IDFcdWFjMWNcdWM3NTggXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1YjQxOFx1YWNlMCwgXHVhYzAxIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjI5NCBcdWI5ZTQgXHVjMTM4XHViMzAwIDJcdWFjMWNcdWM3NTggXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHViODVjIFx1YmQ4NFx1YzVmNFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQoXHVjNmQwXHViNzk4XHVjNzU4IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjI5NCBcdWM1YzZcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZjM0XHVjNzc0XHViMmU0KS48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCAxXHVjMTM4XHViMzAwXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDQsIDJcdWMxMzhcdWIzMDBcdWIyOTQgXHVjY2FiIFx1YzEzOFx1YjMwMFx1Yzc1OCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWFjMDAgXHViNDU4XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljNCBcdWI0NTAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0LCAzXHVjMTM4XHViMzAwXHViMjk0IFx1YjYxMCBcdWFkZjhcdWFjODNcdWM3NzQgXHViMDk4XHViMjA0XHVjNWI0XHVjOWM0IFx1YjEyNCBcdWFjMWNcdWM3NTggXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0LCA0XHVjMTM4XHViMzAwXHViMjk0IFx1YzVlY1x1YjM1ZiBcdWFjMWMsIFx1Yzc3NFx1YjdmMCBcdWMyZGRcdWM3M2NcdWI4NWMgSysxXHVjMTM4XHViMzAwXHVjNWQwXHViMjk0IDI8c3BhbiBzdHlsZT1cImZvbnQtc2l6ZToxMHB4XCI+PHN1cD5rPFwvc3VwPjxcL3NwYW4+XHVhYzFjXHVjNzU4IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWFkZjhcdWI0ZTRcdWM3NzQgXHVjYzNlXHVjNTQ0XHViMGI4IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yjk3YyAxXHViZDgwXHVkMTMwIDI8c3VwPks8XC9zdXA+XHVhZTRjXHVjOWMwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViYzg4XHVkNjM4IFx1YmQ5OVx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3NzRcdWM4MDRcdWM3NTggS1x1YzEzOFx1YjMwMFx1Yzc1OCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWI0ZTRcdWM3NTggXHVkNmM0XHVjMTkwXHVjNzQwOiB7MSwgMn0sIHszLCA0fSwgezUsIDZ9LCAuLi4sIHsyPHN1cD5LPFwvc3VwPi0xLCAyPHN1cD5LPFwvc3VwPn08XC9saT5cclxuXHQ8bGk+XHViMzU0XHVjNmIxIFx1YzgwNFx1Yzc1OCAoSy0xKVx1YzEzOFx1YjMwMFx1Yzc1OCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWI0ZTRcdWM3NTggXHVkNmM0XHVjMTkwXHVjNzQwOiB7MSwgMiwgMywgNH0sIHs1LCA2LCA3LCA4fSwgLi4uLCB7MjxzdXA+SzxcL3N1cD4tMywgMjxzdXA+SzxcL3N1cD4tMiwgMjxzdXA+SzxcL3N1cD4tMSwgMjxzdXA+SzxcL3N1cD59PFwvbGk+XHJcblx0PGxpPlx1ZDZlOFx1YzUyYyBcdWIzNTRcdWM2YjEgXHVjODA0XHVjNzU4IChLLTIpXHVjMTM4XHViMzAwXHVjNzU4IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YjRlNFx1Yzc1OCBcdWQ2YzRcdWMxOTBcdWM3NDA6IHsxLCAyLCAzLCA0LCA1LCA2LCA3LCA4fSwgLi4uLCB7MjxzdXA+SzxcL3N1cD4tNywgMjxzdXA+SzxcL3N1cD4tNiwgMjxzdXA+SzxcL3N1cD4tNSwgMjxzdXA+SzxcL3N1cD4tNCwgMjxzdXA+SzxcL3N1cD4tMywgMjxzdXA+SzxcL3N1cD4tMiwgMjxzdXA+SzxcL3N1cD4tMSwgMjxzdXA+SzxcL3N1cD59PFwvbGk+XHJcblx0PGxpPi4uLjxcL2xpPlxyXG5cdDxsaT4yXHVjMTM4XHViMzAwXHVjNzU4IFx1YjQ1MCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVkNmM0XHVjMTkwXHVjNzQwOiB7MSwgMiwgLi4uLCAyPHN1cD5LLTE8XC9zdXA+fVx1YzY0MCB7MjxzdXA+Sy0xPFwvc3VwPiZuYnNwOysgMSwgMjxzdXA+Sy0xPFwvc3VwPiZuYnNwOysgMiwgLi4uLCAyPHN1cD5LPFwvc3VwPn08XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM5MTFcdWFkMDRcdWQ2MzhcdWIyOTQgXHVjNzc0XHViNGU0XHVjNzc0IFx1ZDU1YyBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDRcdWM3NTggXHVkNmM0XHVjMTkwXHViNGU0XHVjNzc0XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjOTg5IFx1YzViNFx1YjVhNCBcdWM4NzBcdWMwYzEgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1ZDZjNFx1YzE5MFx1YjNjNCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViYzg4XHVkNjM4XHViZDk5XHVjNWVjXHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWIzNTRcdWI3N2NcdWIzYzQgXHVjNWVjXHVjODA0XHVkNzg4IFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHVhYzhjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjZmNcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAgXHVhZGY4XHViN2YwIFx1YzIxY1x1YzExY1x1YjRlNCBcdWM5MTEgJiMzOTtcdWMyMWNcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0JiMzOTtcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHViMjk0IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjQgXHVkNTVjXHViMmU0LiAmIzM5O1x1YzIxY1x1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQmIzM5O1x1YjI5NCBcdWM3NzRcdWM2YzNcdWQ1NWMgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViYWE4XHViNDUwIFx1ZDU2OVx1ZDU1YyBcdWFjODNcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWQ2NTVcdWQ3ODhcdWIyOTQsIFx1YmFhOFx1YjRlMCBcdWI0NTAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJjMThcdWJjMWNcdWI4MjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHViMzcwLCBcdWM3NzQgXHViYzE4XHViYzFjXHViODI1XHVjNzQwIFx1YzIxOFx1Y2U1OFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDQgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YmMxOFx1YmMxY1x1YjgyNVx1Yzc0MCBcdWI0NTAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM3NzRcdWM2YzNcdWQ1NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWI1YThcdWM1YjRcdWM4MzhcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQoXHViNDUwIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1YWMwMCBcdWM3NzRcdWM2YzNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1YmMxOFx1YmMxY1x1YjgyNVx1Yzc0MCBcdWM1NDRcdWJiMzQgXHVkNmE4XHVhY2ZjXHViM2M0IFx1YmJmOFx1Y2U1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpLiBcdWJhYThcdWI0ZTAgXHViYzE1XHVkMTRjXHViOWFjXHVjNTQ0IFx1YzMwZFx1YjRlNFx1Yzc1OCBcdWJjMThcdWJjMWNcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVjNzc0XHViNGU0XHVjNzQ0IFx1YzU1ZVx1YzExYyBcdWI5ZDBcdWQ1NWMgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWIwOThcdWM1ZjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM1YjhcdWFlMDlcdWQ1NWMgXHVjNTkxXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KDEgJmxlOyBLJm5ic3A7JmxlOyZuYnNwOzkpLjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVkNmM0XHVjNzU4IDI8c3VwPks8XC9zdXA+XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBbMCwgMTA8c3VwPjY8XC9zdXA+XSBcdWJjOTRcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IDI8c3VwPks8XC9zdXA+XHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDI8c3VwPks8XC9zdXA+ICZ0aW1lczsgMjxzdXA+SzxcL3N1cD5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViMjk0IFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NCBcdWMzMGRcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YmMxOFx1YmMxY1x1YjgyNVx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQ6IFx1YzVlY1x1YWUzMFx1YzExYyAobSwgbilcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJjMTVcdWQxNGNcdWI5YWNcdWM1NDQgbVx1YWNmYyBuIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWJjMThcdWJjMWNcdWI4MjVcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LiAobSwgbilcdWFjZmMgKG4sIG0pXHVjNWQwXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzAwXHVhY2UwLCBtID0gblx1Yzc3YyBcdWI1NGNcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjIFx1YmMxNVx1ZDE0Y1x1YjlhY1x1YzU0NFx1Yjk3YyBcdWIwOThcdWM1ZjRcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjljY1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc5NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BUlMiLCJkZXNjcmlwdGlvbiI6IjxwPlNjaWVudGlzdHMgaGF2ZSBkaXNjb3ZlcmVkIHNvbWUgc3RyYW5nZSBiYWN0ZXJpYSBvbiBNYXJzIGFuZCBhcmUgbm93IGJ1c3kgc3R1ZHlpbmcgdGhlbS4gVGhleSBoYXZlIG5vdGljZWQgdGhhdCB0aGUgbnVtYmVyIG9mIGJhY3RlcmlhIGlzIGEgcG93ZXIgb2YgMiwgc2luY2UgZWFjaCBiYWN0ZXJpdW0gb24gTWFycyBzcGxpdHMgaW50byB0d28gbmV3IGJhY3RlcmlhIChkeWluZyBpbiB0aGUgcHJvY2VzcyksIGFuZCBpdCBhbGwgc3RhcnRlZCBmcm9tIGEgc2luZ2xlIGJhY3Rlcml1bS48XC9wPlxyXG5cclxuPHA+VGh1cywgaW4gdGhlIGZpcnN0IGdlbmVyYXRpb24gdGhlcmUgd2FzIGEgc2luZ2xlIGJhY3Rlcml1bS4gSXQgc3BsaXQgaW50byB0d28gYmFjdGVyaWEgb2YgdGhlIHNlY29uZCBnZW5lcmF0aW9uLCB3aGljaCBzcGxpdCBpbnRvIGZvdXIgYmFjdGVyaWEgb2YgdGhlIHRoaXJkIGdlbmVyYXRpb24sIGFuZCBzbyBvbiAmbmRhc2g7IHVudGlsIHRoZSAyPHN1cD5LPFwvc3VwPiBiYWN0ZXJpYSBvZiBnZW5lcmF0aW9uIEsrMSB0aGF0IHRoZSBzY2llbnRpc3RzIGhhdmUgZGlzY292ZXJlZC4gVGhleSBoYXZlIG51bWJlcmVkIHRoZSBiYWN0ZXJpYSB1c2luZyBudW1iZXJzIGZyb20gMSB0byAyPHN1cD5LPFwvc3VwPiBpbiB0aGUgZm9sbG93aW5nIHdheTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5kZXNjZW5kYW50cyBvZiBiYWN0ZXJpYSBvZiB0aGUgcHJldmlvdXMgKEs8c3VwPnRoPFwvc3VwPikgZ2VuZXJhdGlvbiBhcmUsIGluIHRoaXMgb3JkZXI6IHsxLCAyfSwgezMsIDR9LCB7NSwgNn0sIC4uLiwgezI8c3VwPks8XC9zdXA+LTEsIDI8c3VwPks8XC9zdXA+fTxcL2xpPlxyXG5cdDxsaT5kZXNjZW5kYW50cyBvZiBiYWN0ZXJpYSBvZiB0aGUgb2xkZXIgKChLLTEpPHN1cD50aDxcL3N1cD4pIGdlbmVyYXRpb24gYXJlLCBpbiB0aGlzIG9yZGVyOiB7MSwgMiwgMywgNH0sIHs1LCA2LCA3LCA4fSwgLi4uLCB7MjxzdXA+SzxcL3N1cD4tMywgMjxzdXA+SzxcL3N1cD4tMiwgMjxzdXA+SzxcL3N1cD4tMSwgMjxzdXA+SzxcL3N1cD59PFwvbGk+XHJcblx0PGxpPmRlc2NlbmRhbnRzIG9mIGJhY3RlcmlhIG9mIHRoZSBldmVuIG9sZGVyICgoSy0yKTxzdXA+dGg8XC9zdXA+KSBnZW5lcmF0aW9uIGFyZSwgaW4gdGhpcyBvcmRlcjogezEsIDIsIDMsIDQsIDUsIDYsIDcsIDh9LCAuLi4sIHsyPHN1cD5LPFwvc3VwPi03LCAyPHN1cD5LPFwvc3VwPi02LCAyPHN1cD5LPFwvc3VwPi01LCAyPHN1cD5LPFwvc3VwPi00LCAyPHN1cD5LPFwvc3VwPi0zLCAyPHN1cD5LPFwvc3VwPi0yLCAyPHN1cD5LPFwvc3VwPi0xLCAyPHN1cD5LPFwvc3VwPn08XC9saT5cclxuXHQ8bGk+Li4uPFwvbGk+XHJcblx0PGxpPmRlc2NlbmRhbnRzIG9mIHRoZSB0d28gYmFjdGVyaWEgb2YgdGhlIHNlY29uZCBnZW5lcmF0aW9uIGFyZSwgaW4gdGhpcyBvcmRlcjogezEsIDIsIC4uLiwgMjxzdXA+Sy0xPFwvc3VwPn0gYW5kIHsyPHN1cD5LLTE8XC9zdXA+ICsgMSwgMjxzdXA+Sy0xPFwvc3VwPiArIDIsIC4uLiwgMjxzdXA+SzxcL3N1cD59PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+d2hlcmUgY3VybHkgYnJhY2VzIGRlbm90ZSBhIHNldCBvZiBkZXNjZW5kYW50cyBvZiBhIHNpbmdsZSBiYWN0ZXJpYS4gVGhhdCBpcywgdGhlIDI8c3VwPks8XC9zdXA+IGJhY3RlcmlhIG9mIHRoZSBjdXJyZW50IGdlbmVyYXRpb24gd2VyZSBudW1iZXJlZCBzdWNoIHRoYXQgZGVzY2VuZGFudHMgb2YgYW55IG9sZGVyIGJhY3Rlcml1bSBoYXZlIGNvbnNlY3V0aXZlIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPk5vdGljZSB0aGF0IHRoZXJlIGV4aXN0IG1hbnkgZGlmZmVyZW50IHBlcm11dGF0aW9ucyBvZiB0aGVzZSBiYWN0ZXJpYSB3aGljaCBzdGlsbCBzYXRpc2Z5IHRoZSBydWxlIHRoYXQgZGVzY2VuZGFudHMgb2YgYW55IG9sZGVyIGJhY3Rlcml1bSBoYXZlIGNvbnNlY3V0aXZlIHNlcXVlbmNlIG51bWJlcnMuIFNjaWVudGlzdHMgd2FudCB0byBhcnJhbmdlIHRoZSBiYWN0ZXJpYSBpbnRvIHN1Y2ggYSBzZXF1ZW5jZSB3aGljaCBhbHNvIGhhcyB0aGUgbWluaW11bSBwb3NzaWJsZSBsZW5ndGguIFRoZSBsZW5ndGggb2YgYSBiYWN0ZXJpYSBzZXF1ZW5jZSBpcyB0aGUgc3VtIG9mIGRpc3RhbmNlcyBiZXR3ZWVuIGFsbCBuZWlnaGJvdXJpbmcgYmFjdGVyaWEgcGFpcnMuPFwvcD5cclxuXHJcbjxwPlNwZWNpZmljYWxseSwgdGhlcmUgaXMgYSBjZXJ0YWluIHF1YW50aWZpYWJsZSByZXB1bHNpb24gYmV0d2VlbiBldmVyeSB0d28gYmFjdGVyaWEsIHdoaWNoIGlzIHRoZSBtaW5pbXVtIGRpc3RhbmNlIGJldHdlZW4gdGhlbSBpZiB0aGV5IGFyZSBuZXh0IHRvIGVhY2ggb3RoZXIgaW4gdGhlIHNlcXVlbmNlLiAoUmVwdWxzaW9uIHBsYXlzIG5vIHJvbGUgYmV0d2VlbiBiYWN0ZXJpYSB0aGF0IGFyZSBub3QgaW1tZWRpYXRlIG5laWdoYm91cnMgaW4gdGhlIHNlcXVlbmNlLikgR2l2ZW4gdGhlIHJlcHVsc2lvbiB2YWx1ZXMgZm9yIGFsbCBiYWN0ZXJpYSBwYWlycywgZmluZCB0aGUgbWluaW11bSBwb3NzaWJsZSBsZW5ndGggb2YgYSBiYWN0ZXJpYSBzZXF1ZW5jZSAocGVybXV0YXRpb24pIHNhdGlzZnlpbmcgdGhlIGRlc2NlbmRhbnQgcnVsZSBnaXZlbiBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIEsgKDEgJmxlOyBLICZsZTsgOSkgZnJvbSB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuRWFjaCBvZiB0aGUgZm9sbG93aW5nIDI8c3VwPks8XC9zdXA+IGxpbmVzIGNvbnRhaW5zIDI8c3VwPks8XC9zdXA+IGludGVnZXJzIGZyb20gdGhlIGludGVydmFsIFswLCAxMDxzdXA+NjxcL3N1cD5dLiBUaGVzZSAySyAmdGltZXM7IDI8c3VwPks8XC9zdXA+IG51bWJlcnMgcmVwcmVzZW50IHJlcHVsc2lvbiBiZXR3ZWVuIGJhY3RlcmlhIHBhaXJzOiB0aGUgbnVtYmVyIGluIHJvdyBtIGFuZCBjb2x1bW4gbiBpcyB0aGUgcmVwdWxzaW9uIGJldHdlZW4gYmFjdGVyaWEgbSBhbmQgbi4gVGhpcyBudW1iZXIgd2lsbCwgb2YgY291cnNlLCBiZSBlcXVhbCB0byB0aGUgbnVtYmVyIGluIHJvdyBuIGFuZCBjb2x1bW4gbS4gRm9yIG0gPSBuIHRoZSBudW1iZXIgd2lsbCBiZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwIHN0eWxlPVwibWFyZ2luLWxlZnQ6IDQwcHg7XCI+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGxlbmd0aCBvZiBhIGJhY3RlcmlhIHNlcXVlbmNlIHNhdGlzZnlpbmcgdGhlIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #1 6번

  • 문제를 번역한 사람: junie