6498번 - 엘리어스 감마 코드 다국어

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

문제

엘리어스 감마 코드는 양의 정수로 이루어진 수열을 인코딩 하는데 사용하는 코드이다. 이 문제에서는 0도 인코딩할 수 있게 변형한 코드를 사용한다.

정수 n을 인코딩하는 과정은 다음과 같다.

  1. n의 비트의 개수를 k라고 한다.
  2. 0을 k-1개 쓰고, 그 뒤에 1을 쓴다.
  3. 그 다음 n을 이진수로 쓴다.

0부터 8까지 숫자를 인코딩한 결과는 아래와 같다.

숫자 이진수 비트의 수 Prefix 코드
0 0 1 1 10
1 1 1 1 11
2 10 2 01 0110
3 11 2 01 0111
4 100 3 001 001100
5 101 3 001 001101
6 110 3 001 001110
7 111 3 001 001111
8 1000 4 0001 00011000

정수 수열을 인코딩하려면, 수열의 각 숫자를 코드로 변환한 뒤, 수열에서 나온 순서와 동일하게 이어 붙이면 된다.

각각의 인코딩된 코드를 원래 숫자로 디코딩하려면, 이진수 표현 앞에 붙는 k개의 비트는 매우 중요하다. 인코딩된 수열을 읽을 때, 1을 읽기 전에 k-1개의 0을 읽었다면, 다음 k개의 비트가 인코딩된 숫자라는 뜻이다.

인코딩된 정수 수열의 길이를 줄이려면, 다음과 같은 두 가지 최적화를 생각해 볼 수 있다. 

  1. Prefix가 k비트를 나타내는데, 수열에 비트의 길이가 k인 숫자가 없는 경우가 있다. 이 경우에는, 이 prefix는 k+1비트를 나타내는 것으로 사용할 수 있다. 만약, k+1비트를 나타내는 prefix가 이미 있는 경우에는 k+2비트를 나타내는 prefix로 사용하고, 이와 같은 식으로 계속 한다.
  2. 비트의 길이가 k인 모든 숫자의 앞에 0을 붙이면, 그 숫자는 모두 k+1개 비트를 가지게 만들고 첫 번째 최적화를 사용하는 방법도 있다. 이 방법은 k비트 숫자가 매우 적고, k비트 이상 숫자가 많은 경우에 효과적이다.

정수 수열을 인코딩한 결과의 길이를 최소로 하려고 한다. 수열의 숫자가 주어지지 않으며, 수열에서 비트의 개수가 i인 수의 개수를 ci라고 한다.

예를 들어, c1=2, c2=4, c3=0, c4=1인 경우를 생각해보자. (수열 2,1,3,8,0,2,3이 이 경우에 해당한다) 최적화를 하지 않은 엘리어스 감마 코딩의 길이는 2×(1+1) + 4×(2+2) + 0×(3+3) + 1×(4+4) = 28이 된다. 1번 최적화를 사용해 prefix 001을 4비트 숫자를 나타내는 것으로 사용해 1비트를 줄일 수 있다. 또, 최적화 2번을 사용해 1비트 앞에 0을 붙여 2비트로 만들 수 있다. 여기서 다시 최적화 1번을 사용해 prefix 1은 2비트 숫자에 사용하고, prefix 01은 4비트 숫자에 사용하면, 인코딩된 문자열의 길이는 6×(1+2) + 1×(2+4) = 24가 된다.

두 최적화 방법은 여러 번 사용할 수 있다. 두 방법을 적절히 사용해 가능한 길이중 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. (1 ≤ n ≤ 128) 둘째 줄에는 c1부터 cn까지 값이 주어진다. (0 ≤ ci ≤ 10000) 입력은 n=0으로 끝난다.

출력

각 테스트 케이스 마다 입력으로 주어진 수열의 최소 엘리어스 감마 인코딩 길이를 출력한다.

예제 입력 1 

4
2 4 0 1
5
9 4 2 4 3
11
44 56 96 26 73 80 77 50 33 16 78
0

예제 출력 1 

24
99
5494
W3sicHJvYmxlbV9pZCI6IjY0OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDhcdWI5YWNcdWM1YjRcdWMyYTQgXHVhYzEwXHViOWM4IFx1Y2Y1NFx1YjRkYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWQ4XHViOWFjXHVjNWI0XHVjMmE0IFx1YWMxMFx1YjljOCBcdWNmNTRcdWI0ZGNcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3OFx1Y2Y1NFx1YjUyOSBcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1Y2Y1NFx1YjRkY1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCAwXHViM2M0IFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhYzhjIFx1YmNjMFx1ZDYxNVx1ZDU1YyBcdWNmNTRcdWI0ZGNcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWMyMTggblx1Yzc0NCBcdWM3NzhcdWNmNTRcdWI1MjlcdWQ1NThcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+blx1Yzc1OCBcdWJlNDRcdWQyYjhcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIGtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4wXHVjNzQ0IGstMVx1YWMxYyBcdWM0ZjBcdWFjZTAsIFx1YWRmOCBcdWI0YTRcdWM1ZDAgMVx1Yzc0NCBcdWM0ZjRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOCBcdWIyZTRcdWM3NGMgblx1Yzc0NCBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHVjNGY0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPjBcdWJkODBcdWQxMzAgOFx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzc4XHVjZjU0XHViNTI5XHVkNTVjIFx1YWNiMFx1YWNmY1x1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NTAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+XHVjMjJiXHVjNzkwPFwvdGg+XHJcblx0XHRcdDx0aD5cdWM3NzRcdWM5YzRcdWMyMTg8XC90aD5cclxuXHRcdFx0PHRoPlx1YmU0NFx1ZDJiOFx1Yzc1OCBcdWMyMTg8XC90aD5cclxuXHRcdFx0PHRoPlByZWZpeDxcL3RoPlxyXG5cdFx0XHQ8dGg+XHVjZjU0XHViNGRjPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDE8XC90ZD5cclxuXHRcdFx0PHRkPjAxMTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMTExPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjEwMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDExMDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDE8XC90ZD5cclxuXHRcdFx0PHRkPjAwMTEwMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMTA8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjAwMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAxMTEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjExMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDExMTE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTAwMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAwMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAwMTEwMDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc4XHVjZjU0XHViNTI5XHVkNTU4XHViODI0XHViYTc0LCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNmNTRcdWI0ZGNcdWI4NWMgXHViY2MwXHVkNjU4XHVkNTVjIFx1YjRhNCwgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyOCBcdWMyMWNcdWMxMWNcdWM2NDAgXHViM2Q5XHVjNzdjXHVkNTU4XHVhYzhjIFx1Yzc3NFx1YzViNCBcdWJkOTlcdWM3NzRcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNzc4XHVjZjU0XHViNTI5XHViNDFjIFx1Y2Y1NFx1YjRkY1x1Yjk3YyBcdWM2ZDBcdWI3OTggXHVjMjJiXHVjNzkwXHViODVjIFx1YjUxNFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjgyNFx1YmE3NCwgXHVjNzc0XHVjOWM0XHVjMjE4IFx1ZDQ1Y1x1ZDYwNCBcdWM1NWVcdWM1ZDAgXHViZDk5XHViMjk0IGtcdWFjMWNcdWM3NTggXHViZTQ0XHVkMmI4XHViMjk0IFx1YjllNFx1YzZiMCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1YjQxYyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzdkXHVjNzQ0IFx1YjU0YywgMVx1Yzc0NCBcdWM3N2RcdWFlMzAgXHVjODA0XHVjNWQwIGstMVx1YWMxY1x1Yzc1OCAwXHVjNzQ0IFx1Yzc3ZFx1YzVjOFx1YjJlNFx1YmE3NCwgXHViMmU0XHVjNzRjIGtcdWFjMWNcdWM3NTggXHViZTQ0XHVkMmI4XHVhYzAwIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1YjQxYyBcdWMyMmJcdWM3OTBcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzhcdWNmNTRcdWI1MjlcdWI0MWMgXHVjODE1XHVjMjE4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjOTA0XHVjNzc0XHViODI0XHViYTc0LCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjZDVjXHVjODAxXHVkNjU0XHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5QcmVmaXhcdWFjMDAga1x1YmU0NFx1ZDJiOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTRcdWIzNzAsIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWJlNDRcdWQyYjhcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIGtcdWM3NzggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWM3NzQgcHJlZml4XHViMjk0IGsrMVx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QsIGsrMVx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgcHJlZml4XHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGsrMlx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgcHJlZml4XHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWNlMCwgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVhY2M0XHVjMThkIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZTQ0XHVkMmI4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBrXHVjNzc4IFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNTVlXHVjNWQwIDBcdWM3NDQgXHViZDk5XHVjNzc0XHViYTc0LCBcdWFkZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBrKzFcdWFjMWMgXHViZTQ0XHVkMmI4XHViOTdjIFx1YWMwMFx1YzljMFx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNkNWNcdWM4MDFcdWQ2NTRcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NDAga1x1YmU0NFx1ZDJiOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViOWU0XHVjNmIwIFx1YzgwMVx1YWNlMCwga1x1YmU0NFx1ZDJiOCBcdWM3NzRcdWMwYzEgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjljZVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNmE4XHVhY2ZjXHVjODAxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc4XHVjZjU0XHViNTI5XHVkNTVjIFx1YWNiMFx1YWNmY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YmU0NFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgaVx1Yzc3OCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIGM8c3ViPmk8XC9zdWI+XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgYzxzdWI+MTxcL3N1Yj49MiwgYzxzdWI+MjxcL3N1Yj49NCwgYzxzdWI+MzxcL3N1Yj49MCwgYzxzdWI+NDxcL3N1Yj49MVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiAoXHVjMjE4XHVjNWY0IDIsMSwzLDgsMCwyLDNcdWM3NzQgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NWNcdWIyZTQpIFx1Y2Q1Y1x1YzgwMVx1ZDY1NFx1Yjk3YyBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzVkOFx1YjlhY1x1YzViNFx1YzJhNCBcdWFjMTBcdWI5YzggXHVjZjU0XHViNTI5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyJnRpbWVzOygxKzEpICsgNCZ0aW1lczsoMisyKSArIDAmdGltZXM7KDMrMykgKyAxJnRpbWVzOyg0KzQpID0gMjhcdWM3NzQgXHViNDFjXHViMmU0LiAxXHViYzg4IFx1Y2Q1Y1x1YzgwMVx1ZDY1NFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NzQgcHJlZml4IDAwMVx1Yzc0NCA0XHViZTQ0XHVkMmI4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU3NCAxXHViZTQ0XHVkMmI4XHViOTdjIFx1YzkwNFx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Y2Q1Y1x1YzgwMVx1ZDY1NCAyXHViYzg4XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NCAxXHViZTQ0XHVkMmI4IFx1YzU1ZVx1YzVkMCAwXHVjNzQ0IFx1YmQ5OVx1YzVlYyAyXHViZTQ0XHVkMmI4XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgXHViMmU0XHVjMmRjIFx1Y2Q1Y1x1YzgwMVx1ZDY1NCAxXHViYzg4XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NCBwcmVmaXggMVx1Yzc0MCAyXHViZTQ0XHVkMmI4IFx1YzIyYlx1Yzc5MFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWFjZTAsIHByZWZpeCAwMVx1Yzc0MCA0XHViZTQ0XHVkMmI4IFx1YzIyYlx1Yzc5MFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQsIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1YjQxYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDYmdGltZXM7KDErMikgKyAxJnRpbWVzOygyKzQpID0gMjRcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjZDVjXHVjODAxXHVkNjU0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWUzOFx1Yzc3NFx1YzkxMSBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEyOCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBjPHN1Yj4xPFwvc3ViPlx1YmQ4MFx1ZDEzMCBjPHN1Yj5uPFwvc3ViPlx1YWU0Y1x1YzljMCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IGM8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDApIFx1Yzc4NVx1YjgyNVx1Yzc0MCBuPTBcdWM3M2NcdWI4NWMgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVjNWQ4XHViOWFjXHVjNWI0XHVjMmE0IFx1YWMxMFx1YjljOCBcdWM3NzhcdWNmNTRcdWI1MjkgXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2NDk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWxpYXMgZ2FtbWEgY29kaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgRWxpYXMgZ2FtbWEgY29kZSBpcyBhIHNpbXBsZSBjb2RlIHdoaWNoIGNhbiBiZSB1c2VkIHRvIGVuY29kZSBhIHNlcXVlbmNlIG9mIHBvc2l0aXZlIGludGVnZXJzLiBXZSB3aWxsIHVzZSBhIG1vZGlmaWVkIGNvZGUgd2hpY2ggaXMgYWxzbyBhYmxlIHRvIGVuY29kZSB6ZXJvcy4gVG8gZW5jb2RlIGFuIGludGVnZXIgbiwgZG8gdGhlIGZvbGxvd2luZzo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5MZXQgayBiZSB0aGUgbnVtYmVyIG9mIGJpdHMgb2YgbjxcL2xpPlxyXG5cdDxsaT5Xcml0ZSBrLTEgemVyb3MgZm9sbG93ZWQgYnkgYSAxPFwvbGk+XHJcblx0PGxpPldyaXRlIG4gaW4gYmluYXJ5PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjYwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPk51bWJlcjxcL3RoPlxyXG5cdFx0XHQ8dGg+QmluYXJ5PFwvdGg+XHJcblx0XHRcdDx0aD5OdW1iZXIgb2YgYml0czxcL3RoPlxyXG5cdFx0XHQ8dGg+UHJlZml4PFwvdGg+XHJcblx0XHRcdDx0aD5Db2RlPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDE8XC90ZD5cclxuXHRcdFx0PHRkPjAxMTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMTExPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjEwMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDExMDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDE8XC90ZD5cclxuXHRcdFx0PHRkPjAwMTEwMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMTA8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjAwMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAxMTEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjExMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDExMTE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTAwMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAwMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAwMTEwMDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPkEgc2VxdWVuY2Ugb2YgaW50ZWdlcnMgaXMgZW5jb2RlZCBieSB3cml0aW5nIHRoZSBjb2RlcyBvZiB0aGUgaW5kaXZpZHVhbCBpbnRlZ2VycyBvZiB0aGUgc2VxdWVuY2UgaW4gdGhlIHNhbWUgb3JkZXIgYXMgdGhlIGludGVnZXJzIGFwcGVhciBpbiB0aGUgc2VxdWVuY2UuIFRoZSBwcmVmaXggb2YgayBhZGRpdGlvbmFsIGJpdHMgYmVmb3JlIHRoZSBiaW5hcnkgcmVwcmVzZW50YXRpb24gb2YgZWFjaCBpbnRlZ2VyIGlzIG5lZWRlZCB0byBiZSBhYmxlIHRvIGRlY29kZSB0aGUgZW5jb2RlZCBpbnRlZ2Vycy4gU28gd2hlbiByZWFkaW5nIHRoZSBlbmNvZGluZyBvZiBhIHNlcXVlbmNlIG9mIGludGVnZXJzLCBpZiB3ZSByZWFkIGstMSB6ZXJvcyBmb2xsb3dlZCBieSBhIG9uZSwgaXQgbWVhbnMgdGhhdCB0aGVyZSBhcmUgayBiaXRzIGZvbGxvd2luZyB3aGljaCBhcmUgdGhlIGJpbmFyeSByZXByZXNlbnRhdGlvbiBvZiB0aGUgbmV4dCBlbmNvZGVkIGludGVnZXIuPFwvcD5cclxuXHJcbjxwPklmIHdlIHdhbnQgdG8gc2hvcnRlbiB0aGUgbGVuZ3RoIG9mIHRoZSBlbmNvZGluZyBvZiBhIHNlcXVlbmNlIG9mIGludGVnZXJzLCB0aGVyZSBtYXkgYmUgc3RpbGwgc29tZSByb29tIGZvciBpbXByb3ZlbWVudDsgd2Ugd2lsbCBjb25zaWRlciB0aGUgZm9sbG93aW5nIHR3byBvcHRpbWl6YXRpb25zOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPklmIHRoZXJlIGlzIGEgcHJlZml4IHdoaWNoIGluZGljYXRlcyB0aGF0IGsgYml0cyBhcmUgZm9sbG93aW5nLCBidXQgdGhlcmUgaXMgbm8gaW50ZWdlciBpbiB0aGUgc2VxdWVuY2Ugd2l0aCBrIGJpdHMsIHdlIGNhbiB1c2UgdGhpcyBwcmVmaXggdG8gaW5kaWNhdGUgdGhhdCBrKzEgYml0cyBhcmUgZm9sbG93aW5nLiBJZiB0aGVyZSBhbHJlYWR5IHdhcyBhIHByZWZpeCB3aGljaCBpbmRpY2F0ZXMgdGhhdCBrKzEgYml0cyBhcmUgZm9sbG93aW5nLCB0aGlzIHByZWZpeCBpcyBub3QgbmVlZGVkIGFueW1vcmUsIGFuZCBpdCBjYW4gYmUgdXNlZCB0byBpbmRpY2F0ZSB0aGF0IGsrMiBiaXRzIGFyZSBmb2xsb3dpbmcsIGFuZCBzbyBvbi48XC9saT5cclxuXHQ8bGk+V2UgY2FuIGFkZCBhIGxlYWRpbmcgemVybyB0byB0aGUgYmluYXJ5IHJlcHJlc2VudGF0aW9uIG9mIGFsbCBpbnRlZ2VycyBpbiB0aGUgc2VxdWVuY2Ugd2l0aCBrIGJpdHMsIHdoaWNoIHRoZW4gYmVjb21lIGludGVnZXJzIHdpdGggaysxIGJpdHMsIGFuZCB0aGVuIHRoZSBmaXJzdCBvcHRpbWl6YXRpb24gY2FuIGJlIHVzZWQuIFRoaXMgb3B0aW1pemF0aW9uIHNlZW1zIGVzcGVjaWFsbHkgdXNlZnVsIGlmIHRoZXJlIGFyZSBmZXcgaW50ZWdlcnMgd2l0aCBrIGJpdHMsIGJ1dCBtYW55IGludGVnZXJzIHdpdGggbW9yZSB0aGFuIGsgYml0cy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5XaGVuIHdlIGFyZSBtaW5pbWl6aW5nIHRoZSBsZW5ndGggb2YgdGhlIGVuY29kaW5nIG9mIGEgc2VxdWVuY2Ugb2YgaW50ZWdlcnMsIHdlIG9ubHkgY2FyZSBhYm91dCBob3cgbWFueSBpbnRlZ2VycyBpbiB0aGUgc2VxdWVuY2UgaGF2ZSBhIGNlcnRhaW4gbnVtYmVyIG9mIGJpdHMuIExldCBjPHN1Yj5pPFwvc3ViPiBkZW5vdGUgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiBhIHNlcXVlbmNlIHdpdGggaSBiaXRzLjxcL3A+XHJcblxyXG48cD5MZXQgdXMgbG9vayBhdCB0aGUgZm9sbG93aW5nIGV4YW1wbGU6IGM8c3ViPjE8XC9zdWI+ID0gMiwgYzxzdWI+MjxcL3N1Yj4gPSA0LCBjPHN1Yj4zPFwvc3ViPiA9IDAsIGM8c3ViPjQ8XC9zdWI+ID0gMSAod2hpY2gsIGZvciBleGFtcGxlLCBjb3VsZCBjb3JyZXNwb25kIHRvIGEgc2VxdWVuY2UgMiwgMSwgMywgOCwgMCwgMiwgMykuIFdpdGggdGhlIG9yaWdpbmFsIGVsaWFzIGdhbW1hIGNvZGluZywgdGhlIGVuY29kaW5nIG9mIHRoZSBzZXF1ZW5jZSB3b3VsZCBoYXZlIGxlbmd0aCAyICZ0aW1lczsgKDEgKyAxKSArIDQgJnRpbWVzOyAoMiArIDIpICsgMCAmdGltZXM7ICgzICsgMykgKyAxICZ0aW1lczsgKDQgKyA0KSA9IDI4LiBCeSB1c2luZyBvcHRpbWl6YXRpb24gMSB3ZSBjYW4gc2F2ZSAxIGJpdCBieSB1c2luZyBwcmVmaXggMDAxIGZvciB0aGUgaW50ZWdlciB3aXRoIDQgYml0cy4gVGhlbiwgd2UgY291bGQgdXNlIG9wdGltaXphdGlvbiAyIGFuZCBhZGQgbGVhZGluZyB6ZXJvcyB0byB0aGUgaW50ZWdlcnMgd2l0aCAxIGJpdCwgbWFraW5nIHRoZW0gdXNlIDIgYml0cy4gVGhlbiwgd2UgdXNlIG9wdGltaXphdGlvbiAxIGFuZCB1c2UgcHJlZml4IDEgZm9yIHRoZSBpbnRlZ2VycyB3aXRoIDIgYml0cywgcHJlZml4IDAxIGZvciB0aGUgaW50ZWdlciB3aXRoIDQgYml0cywgYW5kIHdlIGdldCB0aGUgbmV3IGxlbmd0aCBvZiA2ICZ0aW1lczsgKDEgKyAyKSArIDEgJnRpbWVzOyAoMiArIDQpID0gMjQuPFwvcD5cclxuXHJcbjxwPkJvdGggb3B0aW1pemF0aW9ucyBjYW4gcG9zc2libHkgYmUgdXNlZCBzZXZlcmFsIHRpbWVzLiBOb3RlIHRoYXQgZm9yIHRoZSBzZWNvbmQgb3B0aW1pemF0aW9uLCBpdCBpcyBub3QgZWFzeSB0byBkZWNpZGUgd2hlbiBhbmQgaG93IHRvIHVzZSBpdC4gVGhlIGdvYWwgaXMgdG8gY29tYmluZSB0aGVzZSB0d28gb3B0aW1pemF0aW9ucyBpbiB0aGUgYmVzdCBwb3NzaWJsZSB3YXksIHRoYXQgbWVhbnMgd2Ugd2FudCB0byBmaW5kIGFuIGVuY29kaW5nIG9mIGEgZ2l2ZW4gc2VxdWVuY2Ugb2YgaW50ZWdlcnMgdGhhdCBoYXMgbWluaW11bSBsZW5ndGggYW1vbmcgYWxsIGVuY29kaW5ncyB1c2luZyBlbGlhcyBnYW1tYSBjb2Rpbmcgd2l0aCBhbnkgY29tYmluYXRpb24gb2YgdGhlc2UgdHdvIG9wdGltaXphdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiwgKDEgJmxlOyBuICZsZTsgMTI4KS4gVGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgdmFsdWVzIGM8c3ViPjE8XC9zdWI+LCAuLi4sIGM8c3ViPm48XC9zdWI+ICgwICZsZTsgYzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCkuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgbj0wLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgb25lIGxpbmUgd2l0aCB0aGUgbWluaW11bSBsZW5ndGggb2YgYW4gZW5jb2Rpbmcgb2YgdGhlIGdpdmVuIGlucHV0IHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2009 E번

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

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

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

한국어 | English (Beta)