시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 61 19 9 18.750%

문제

지금껏 문제를 풀면서 시간 초과 메시지를 본 적이 있을 것이다.

시간 초과의 이유엔 여러 가지가 있지만, 주로 제출한 코드의 시간복잡도가 문제에서 요구하는 최대 한도의 시간복잡도를 상회했을 때 발생한다.

이번 문제를 풀면서 시간복잡도에 대한 이해도를 높이고 시간 초과 메시지를 덜 받도록 해보자.

어떤 소스 코드가 주어지면 이 소스 코드의 시간복잡도를 계산하면 된다.

물론 그냥 계산하기엔 너무 어려우므로, 다음과 같은 간소화된 방식으로 계산해보도록 하자.

프로그램은 단 네 개의 명령어만을 가진다고 가정한다. 목록은 아래와 같다.

  • basic : 사칙연산 혹은 값 할당 등의 기초적인 코드
  • loop : 반복문의 시작
  • endloop : 반복문의 끝
  • endprogram : 프로그램의 종료

프로그램 분석은 아래의 규칙에 따라 시행한다.

  • 위에 주어진 네가지 명령어만이 프로그램에 존재한다.
  • loop문은 항상 하나의 전달 인자를 가지며, 대응되는 하나의 endloop문(loop의 시작 이후로 만나는 첫 endloop문)과 묶여 하나의 반복문이 된다.
  • loop의 전달 인자는 x, y, 또는 양의 정수가 될 수 있으며, x, y는 상수이다. 프로그램 실행 도중 재할당되지 않는다. 이 전달인자만큼 루프를 반복하게 된다.
  • 만일 어떤 loop문 내에 basic 코드가 하나도 존재하지 않는다면 의미없는 루프이므로 전달인자의 값에 관계없이 그 loop를 즉시 종료하게 된다.
  • 만일 어떤 loop문 내에 basic 코드가 여러 개 존재하더라도 한 개의 basic 코드가 있는 것과 같이 생각해도 된다.
  • basic 코드는 실행에 상수 시간이 걸린다.

시간복잡도는 basic 구문의 실행 횟수를 함수로 나타낸 뒤 빅오 표기법을 사용하여 분석한다.

빅오 표기법의 정의는 다음과 같다.

어떤 임의의 양의 상수 c와 d를 잘 골라, 1 이상인 모든 x에 대하여 c*g(x) ≤ f(x) ≤ d*g(x)를 만족하게 할 수 있다면 f(x)의 빅오 표기는 O(g)이다.

좀 더 쉽게 설명하면, 모든 상수부는 떼어내버릴 수 있다는 의미이다.

예를 들면 4x 3의 빅오 표기는 x3가 된다.

또한, 어떤 항보다 낮은 차수를 가지는 항들은 통째로 제거하는 것이 가능하다.

예를 들어, x 3 + x2의 빅오 표기는 x3이 되며, x2 + 7의 빅오 표기는 x2가 된다.

하지만 여러 서로 다른 변수가 섞여있다면 다른 항보다 작다고 확신할 수 없는 항들은 모두 표기해야 한다.

예를 들어, x 2y + y2x + xy + x2 의 빅오 표기는 x2y + y2x가 되며, x2 + 17xy + y2 의 빅오 표기는 x2 + y2이 된다.

입력

첫 줄에 테스트 케이스의 수 K가 주어진다.

각 테스트 케이스는 빈 줄로 구분한다.

프로그램은 문제에서 설명한 네 가지의 명령어로만 구성되어 있으며, endprogram은 항상 가장 바깥의 loop문보다 더 아래에 단 하나 존재한다.

loop와 전달인자 x 사이에는 단 한개의 공백이 있으며, 이 경우를 제외하고는 프로그램 내에 어떤 공백이나 이상한 문자가 주어지는 경우는 없다.

loop문의 최대 중첩 횟수는 50회이다.

출력

각 테스트 케이스마다 Data Set K: 를 출력한 뒤, 입력으로 주어진 프로그램의 시간복잡도를 출력한다.

각 항은 x의 차수가 높은 것부터, x의 차수가 같다면 y의 차수가 높은 것부터 차례대로 출력한다.

각 항을 출력할 땐 최대한 축약해야 한다. 예를 들어, x^1y^1을 출력하는 대신에 xy를 출력해야 하며, x^1y^0을 출력하는 대신에 x를 출력해야 한다.

그 외의 출력 형식에 대한 내용은 예제 출력을 보면 된다.

각 테스트 케이스의 사이엔 빈 줄을 하나 출력한다.

예제 입력 1

3
loop x
endloop
endprogram

basic
basic
endprogram

loop y
basic
loop y
basic
basic
endloop
endloop
loop x
loop y
basic
endloop
loop x
basic
endloop
endloop
endprogram

예제 출력 1

Data Set 1:
0

Data Set 2:
1

Data Set 3:
x^2 + y^2
W3sicHJvYmxlbV9pZCI6IjUxNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWFjMDQgXHVjZDA4XHVhY2ZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWFlMDhcdWFlY2YgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YmE3NFx1YzExYyBcdWMyZGNcdWFjMDQgXHVjZDA4XHVhY2ZjIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWJjZjggXHVjODAxXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1YWMwNCBcdWNkMDhcdWFjZmNcdWM3NTggXHVjNzc0XHVjNzIwXHVjNWQ0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWM4ZmNcdWI4NWMgXHVjODFjXHVjZDljXHVkNTVjIFx1Y2Y1NFx1YjRkY1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWJjZjVcdWM3YTFcdWIzYzRcdWFjMDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzY5NFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTVjXHViM2M0XHVjNzU4IFx1YzJkY1x1YWMwNFx1YmNmNVx1YzdhMVx1YjNjNFx1Yjk3YyBcdWMwYzFcdWQ2OGNcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YmMxY1x1YzBkZFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYzg4IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWJhNzRcdWMxMWMgXHVjMmRjXHVhYzA0XHViY2Y1XHVjN2ExXHViM2M0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM3NzRcdWQ1NzRcdWIzYzRcdWI5N2MgXHViMTkyXHVjNzc0XHVhY2UwIFx1YzJkY1x1YWMwNCBcdWNkMDhcdWFjZmMgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YjM1YyBcdWJjMWJcdWIzYzRcdWI4NWQgXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjMThjXHVjMmE0IFx1Y2Y1NFx1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgXHVjNzc0IFx1YzE4Y1x1YzJhNCBcdWNmNTRcdWI0ZGNcdWM3NTggXHVjMmRjXHVhYzA0XHViY2Y1XHVjN2ExXHViM2M0XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzY1x1Yjg2MCBcdWFkZjhcdWIwZTUgXHVhY2M0XHVjMGIwXHVkNTU4XHVhZTMwXHVjNWQ0IFx1YjEwOFx1YmIzNCBcdWM1YjRcdWI4MjRcdWM2YjBcdWJiYzBcdWI4NWMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhYzA0XHVjMThjXHVkNjU0XHViNDFjIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWJjZjRcdWIzYzRcdWI4NWQgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHViMmU4IFx1YjEyNCBcdWFjMWNcdWM3NTggXHViYTg1XHViODM5XHVjNWI0XHViOWNjXHVjNzQ0IFx1YWMwMFx1YzljNFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuIFx1YmFhOVx1Yjg1ZFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmJhc2ljIDogXHVjMGFjXHVjZTU5XHVjNWYwXHVjMGIwIFx1ZDYzOVx1Yzc0MCBcdWFjMTIgXHVkNTYwXHViMmY5IFx1YjRmMVx1Yzc1OCBcdWFlMzBcdWNkMDhcdWM4MDFcdWM3NzggXHVjZjU0XHViNGRjPFwvbGk+XHJcblx0PGxpPmxvb3AgOiBcdWJjMThcdWJjZjVcdWJiMzhcdWM3NTggXHVjMmRjXHVjNzkxPFwvbGk+XHJcblx0PGxpPmVuZGxvb3AgOiBcdWJjMThcdWJjZjVcdWJiMzhcdWM3NTggXHViMDVkPFwvbGk+XHJcblx0PGxpPmVuZHByb2dyYW0gOiBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjODg1XHViOGNjPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YmQ4NFx1YzExZFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM3NTggXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWMyZGNcdWQ1ODlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWIxMjRcdWFjMDBcdWM5YzAgXHViYTg1XHViODM5XHVjNWI0XHViOWNjXHVjNzc0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPmxvb3BcdWJiMzhcdWM3NDAgXHVkNTZkXHVjMGMxIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MDRcdWIyZWMgXHVjNzc4XHVjNzkwXHViOTdjIFx1YWMwMFx1YzljMFx1YmE3MCwgXHViMzAwXHVjNzUxXHViNDE4XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBlbmRsb29wXHViYjM4KGxvb3BcdWM3NTggXHVjMmRjXHVjNzkxIFx1Yzc3NFx1ZDZjNFx1Yjg1YyBcdWI5Y2NcdWIwOThcdWIyOTQgXHVjY2FiIGVuZGxvb3BcdWJiMzgpXHVhY2ZjIFx1YmIzNlx1YzVlYyBcdWQ1NThcdWIwOThcdWM3NTggXHViYzE4XHViY2Y1XHViYjM4XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+bG9vcFx1Yzc1OCBcdWM4MDRcdWIyZWMgXHVjNzc4XHVjNzkwXHViMjk0IHgsIHksIFx1YjYxMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YjQyMCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCB4LCB5XHViMjk0IFx1YzBjMVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YzJlNFx1ZDU4OSBcdWIzYzRcdWM5MTEgXHVjN2FjXHVkNTYwXHViMmY5XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0IFx1YzgwNFx1YjJlY1x1Yzc3OFx1Yzc5MFx1YjljY1x1ZDA3YyBcdWI4ZThcdWQ1MDRcdWI5N2MgXHViYzE4XHViY2Y1XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNzdjIFx1YzViNFx1YjVhNCBsb29wXHViYjM4IFx1YjBiNFx1YzVkMCBiYXNpYyBcdWNmNTRcdWI0ZGNcdWFjMDAgXHVkNTU4XHViMDk4XHViM2M0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgXHVjNzU4XHViYmY4XHVjNWM2XHViMjk0IFx1YjhlOFx1ZDUwNFx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWM4MDRcdWIyZWNcdWM3NzhcdWM3OTBcdWM3NTggXHVhYzEyXHVjNWQwIFx1YWQwMFx1YWNjNFx1YzVjNlx1Yzc3NCBcdWFkZjggbG9vcFx1Yjk3YyBcdWM5ODlcdWMyZGMgXHVjODg1XHViOGNjXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNzdjIFx1YzViNFx1YjVhNCBsb29wXHViYjM4IFx1YjBiNFx1YzVkMCBiYXNpYyBcdWNmNTRcdWI0ZGNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWIzNTRcdWI3N2NcdWIzYzQgXHVkNTVjIFx1YWMxY1x1Yzc1OCBiYXNpYyBcdWNmNTRcdWI0ZGNcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWM4M1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjMGRkXHVhYzAxXHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+YmFzaWMgXHVjZjU0XHViNGRjXHViMjk0IFx1YzJlNFx1ZDU4OVx1YzVkMCBcdWMwYzFcdWMyMTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMyZGNcdWFjMDRcdWJjZjVcdWM3YTFcdWIzYzRcdWIyOTQgYmFzaWMgXHVhZDZjXHViYjM4XHVjNzU4IFx1YzJlNFx1ZDU4OSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVkNTY4XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWI0YTQgXHViZTQ1XHVjNjI0IFx1ZDQ1Y1x1YWUzMFx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgXHViZDg0XHVjMTFkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJlNDVcdWM2MjQgXHVkNDVjXHVhZTMwXHViYzk1XHVjNzU4IFx1YzgxNVx1Yzc1OFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWMwYzFcdWMyMTggY1x1YzY0MCBkXHViOTdjIFx1Yzc5OCBcdWFjZThcdWI3N2MsIDEgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YmFhOFx1YjRlMCB4XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBjKmcoeCkgJmxlOyBmKHgpICZsZTsgZCpnKHgpXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCBmKHgpXHVjNzU4IFx1YmU0NVx1YzYyNCBcdWQ0NWNcdWFlMzBcdWIyOTQgTyhnKVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODgwIFx1YjM1NCBcdWMyN2RcdWFjOGMgXHVjMTI0XHViYTg1XHVkNTU4XHViYTc0LCBcdWJhYThcdWI0ZTAgXHVjMGMxXHVjMjE4XHViZDgwXHViMjk0IFx1YjViY1x1YzViNFx1YjBiNFx1YmM4NFx1YjliNCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCA0eCA8c3VwPjM8XC9zdXA+XHVjNzU4IFx1YmU0NVx1YzYyNCBcdWQ0NWNcdWFlMzBcdWIyOTQgeDxzdXA+MzxcL3N1cD5cdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI2MTBcdWQ1NWMsIFx1YzViNFx1YjVhNCBcdWQ1NmRcdWJjZjRcdWIyZTQgXHViMGFlXHVjNzQwIFx1Y2MyOFx1YzIxOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVkNTZkXHViNGU0XHVjNzQwIFx1ZDFiNVx1YzlmOFx1Yjg1YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgeCA8c3VwPjM8XC9zdXA+ICsgeDxzdXA+MjxcL3N1cD5cdWM3NTggXHViZTQ1XHVjNjI0IFx1ZDQ1Y1x1YWUzMFx1YjI5NCB4PHN1cD4zPFwvc3VwPlx1Yzc3NCBcdWI0MThcdWJhNzAsIHg8c3VwPjI8XC9zdXA+ICsgN1x1Yzc1OCBcdWJlNDVcdWM2MjQgXHVkNDVjXHVhZTMwXHViMjk0IHg8c3VwPjI8XC9zdXA+XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzVlY1x1YjdlYyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmNjMFx1YzIxOFx1YWMwMCBcdWMxMWVcdWM1ZWNcdWM3ODhcdWIyZTRcdWJhNzQgXHViMmU0XHViOTc4IFx1ZDU2ZFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTRcdWFjZTAgXHVkNjU1XHVjMmUwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVkNTZkXHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWQ0NWNcdWFlMzBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCB4IDxzdXA+MjxcL3N1cD55ICsgeTxzdXA+MjxcL3N1cD54ICsgeHkgKyB4PHN1cD4yPFwvc3VwPiBcdWM3NTggXHViZTQ1XHVjNjI0IFx1ZDQ1Y1x1YWUzMFx1YjI5NCB4PHN1cD4yPFwvc3VwPnkgKyB5PHN1cD4yPFwvc3VwPnhcdWFjMDAgXHViNDE4XHViYTcwLCB4PHN1cD4yPFwvc3VwPiArIDE3eHkgKyB5PHN1cD4yPFwvc3VwPiBcdWM3NTggXHViZTQ1XHVjNjI0IFx1ZDQ1Y1x1YWUzMFx1YjI5NCB4PHN1cD4yPFwvc3VwPiArIHk8c3VwPjI8XC9zdXA+XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmU0OCBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWIxMjQgXHVhYzAwXHVjOWMwXHVjNzU4IFx1YmE4NVx1YjgzOVx1YzViNFx1Yjg1Y1x1YjljYyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBlbmRwcm9ncmFtXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWFjMDBcdWM3YTUgXHViYzE0XHVhZTY1XHVjNzU4IGxvb3BcdWJiMzhcdWJjZjRcdWIyZTQgXHViMzU0IFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWIyZTggXHVkNTU4XHViMDk4IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+bG9vcFx1YzY0MCBcdWM4MDRcdWIyZWNcdWM3NzhcdWM3OTAgeCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViMmU4IFx1ZDU1Y1x1YWMxY1x1Yzc1OCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHViMGI0XHVjNWQwIFx1YzViNFx1YjVhNCBcdWFjZjVcdWJjMzFcdWM3NzRcdWIwOTggXHVjNzc0XHVjMGMxXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+bG9vcFx1YmIzOFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVjOTExXHVjY2E5IFx1ZDY5Zlx1YzIxOFx1YjI5NCA1MFx1ZDY4Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBEYXRhIFNldCBLOiBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjIFx1YjRhNCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjMmRjXHVhYzA0XHViY2Y1XHVjN2ExXHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDU2ZFx1Yzc0MCB4XHVjNzU4IFx1Y2MyOFx1YzIxOFx1YWMwMCBcdWIxOTJcdWM3NDAgXHVhYzgzXHViZDgwXHVkMTMwLCB4XHVjNzU4IFx1Y2MyOFx1YzIxOFx1YWMwMCBcdWFjMTlcdWIyZTRcdWJhNzQgeVx1Yzc1OCBcdWNjMjhcdWMyMThcdWFjMDAgXHViMTkyXHVjNzQwIFx1YWM4M1x1YmQ4MFx1ZDEzMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkNTZkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2MCBcdWI1NTAgXHVjZDVjXHViMzAwXHVkNTVjIFx1Y2Q5NVx1YzU3ZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIHheMXleMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHViMzAwXHVjMmUwXHVjNWQwIHh5XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIHheMXleMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHViMzAwXHVjMmUwXHVjNWQwIHhcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YzY3OFx1Yzc1OCBcdWNkOWNcdWI4MjUgXHVkNjE1XHVjMmRkXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIwYjRcdWM2YTlcdWM3NDAgXHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWJjZjRcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMwYWNcdWM3NzRcdWM1ZDQgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUxNzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaW1lIExpbWl0IEV4Y2VlZGVkIiwiZGVzY3JpcHRpb24iOiI8cD4mbGRxdW87VGltZSBsaW1pdCBleGNlZWRlZCZyZHF1bzsgaXMgYW5vdGhlciBmYXZvcml0ZSBlcnJvciBtZXNzYWdlLiBNb3N0IGZyZXF1ZW50bHksIHRoZSBjYXVzZSBpcyBlaXRoZXIgYW4gaW5maW5pdGUgbG9vcCBzb21ld2hlcmUgaW4geW91ciBwcm9ncmFtLCBvciAmbWRhc2g7IG1vcmUgb2Z0ZW4gJm1kYXNoOyBhIHZlcnkgc2xvdyBicnV0ZS1mb3JjZSBzb2x1dGlvbiB0byBhIHByb2JsZW0gdGhhdCBzaG91bGQgYmUgc29sdmVkIG1vcmUgZWxlZ2FudGx5LiBUaGUgcHJvYmxlbSBpcyBub3QgdGhhdCB3ZSB0ZXJtaW5hdGUgdGhlIHByb2dyYW0gYWZ0ZXIgMSBtaW51dGU7IHlvdXIgc29sdXRpb25zIHdvdWxkIHByb2JhYmx5IHJ1biAxMDxzdXA+MTAwPFwvc3VwPiB5ZWFycyBpZiB0aGV5IHVzZSBicnV0ZS1mb3JjZSBmb3IgYSBwcm9ibGVtIHdoZXJlIHRoZXkgc2hvdWxkbiZyc3F1bzt0LjxcL3A+XHJcblxyXG48cD5UaGUgd2hvbGUgdGhpbmcgbWlnaHQgYmUgYSBsaXR0bGUgZWFzaWVyIGlmIHlvdSBoYWQgYSBsaXR0bGUgcHJvZ3JhbSB0byBmaWd1cmUgb3V0IHRoZSBydW50aW1lIGNvbXBsZXhpdHkgb2YgeW91ciBjb2RlLiBJbiBnZW5lcmFsLCB0aGlzIGlzIGFuIHVuZGVjaWRhYmxlIHByb2JsZW0gKGkuZS4sIHRoZXJlIGNhbm5vdCBiZSBhbnkgY29tcHV0ZXIgcHJvZ3JhbSBhbHdheXMgZ2V0dGluZyBpdCByaWdodCwgb25lIG9mIHRoZSBjb29sIHJlc3VsdHMgeW91IGxlYXJuIGluIENTQ0kgMzAzKS4gU28gaW5zdGVhZCwgd2Ugd2lsbCByZXN0cmljdCBvdXIgYXR0ZW50aW9uIHRvIGEgc2V2ZXJlbHkgcmVzdHJpY3RlZCAmbGRxdW87cHJvZ3JhbW1pbmcgbGFuZ3VhZ2UmcmRxdW87IGZvciB3aGljaCB0aGUgcHJvYmxlbSBjYW4gYmUgc29sdmVkIGFnYWluLiBQcm9ncmFtcyBvbmx5IGNvbnNpc3Qgb2YgZm91ciBraW5kcyBvZiBzdGF0ZW1lbnRzLCBuYW1lbHkgPGNvZGU+YmFzaWM8XC9jb2RlPiwgPGNvZGU+bG9vcDxcL2NvZGU+LCA8Y29kZT5lbmRsb29wPFwvY29kZT4gYW5kIDxjb2RlPmVuZHByb2dyYW08XC9jb2RlPi4gRWFjaCBzdGF0ZW1lbnQgaXMgb24gYSBsaW5lIGJ5IGl0c2VsZiwgdGhlcmUgYXJlIG5vIHNlbWljb2xvbnMgb3IgYW55IG90aGVyIHB1bmN0dWF0aW9uLCBhbmQgbG9vcCBpcyB0aGUgb25seSBjb21tYW5kIHdpdGggYSBwYXJhbWV0ZXIuIFRoYXQgcGFyYW1ldGVyIGlzIGVpdGhlciBhIHBvc2l0aXZlIGludGVnZXIgbnVtYmVyLCBvciBvbmUgb2YgdGhlIHR3byB2YXJpYWJsZXMgJmxzcXVvO3gmcnNxdW87IGFuZCAmbHNxdW87eSZyc3F1bzsgKG91ciBzaW1wbGlmaWVkIHByb2dyYW1taW5nIGxhbmd1YWdlIGhhcyBvbmx5IHR3byB2YXJpYWJsZXMpLCBkZW5vdGluZyB0aGF0IHRoZSBib2R5IGJldHdlZW4gdGhlIDxjb2RlPmxvb3A8XC9jb2RlPiBhbmQgdGhlIGNvcnJlc3BvbmRpbmcgZW5kbG9vcCBpcyBleGVjdXRlZCB0aGF0IG1hbnkgdGltZXMuPFwvcD5cclxuXHJcbjxwPjxjb2RlPmJhc2ljPFwvY29kZT4gZGVub3RlcyBhIGJhc2ljIHN0YXRlbWVudCAobGlrZSBhc3NpZ25tZW50LCBhZGRpdGlvbiwgb3Igc29tZSBvdGhlciBzdHVmZiB0aGF0IGRvZXMgbm90IG1hdHRlciBmb3IgY29tcGxleGl0eSBhbmFseXNpcyksIGFuZCA8Y29kZT5lbmRwcm9ncmFtPFwvY29kZT4gaXMgdGhlIGVuZCBvZiB0aGUgcHJvZ3JhbS4gTm90aWNlIHRoYXQgdGhlIG51bWJlciBvZiB0aW1lcyBhIGxvb3AgaXMgZXhlY3V0ZWQgaXMgYWx3YXlzIGEgY29uc3RhbnQgKGVpdGhlciB0aGUgdmFyaWFibGUgb3IgYSBudW1lcmljYWwgb25lKSwgc2luY2UgdmFyaWFibGVzIGNhbm5vdCBiZSBhc3NpZ25lZCB2YWx1ZXMuIEFsc28sIHdlIGFzc3VtZSB0aGF0IG91ciBjb21waWxlciBpcyBzbWFydCBlbm91Z2ggdG8gcHJ1bmUgYXdheSBsb29wcyB3aXRoIG5vIDxjb2RlPmJhc2ljPFwvY29kZT4gc3RhdGVtZW50IGFueXdoZXJlIGluIHRoZWlyIGJvZGllcy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byBkZXRlcm1pbmUsIGluIGJpZy1PaCAoTykgbm90YXRpb24sIHRoZSBjb21wbGV4aXR5IG9mIHRoZSBwcm9ncmFtLCBpLmUuIHRoZSB0b3RhbCBudW1iZXIgb2YgdGltZXMgdGhhdCBhbnkgYmFzaWMgc3RhdGVtZW50IGlzIGV4ZWN1dGVkLiBZb3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBhbiBhc3ltcHRvdGljYWxseSB0aWdodCBib3VuZCBvZiB0aGUgZm9ybSAmVGhldGE7KC4gLiAuKS48XC9wPlxyXG5cclxuPHA+V2Ugc2F5IHRoYXQgYSBmdW5jdGlvbiBmIGlzICZUaGV0YTsoZykgZm9yIGFub3RoZXIgZnVuY3Rpb24gZywgaWYgdGhlcmUgYXJlIHBvc2l0aXZlIGNvbnN0YW50cyBjIGFuZCBkIHdpdGggYyZtaWRkb3Q7Zyh4KSAmbGU7IGYoeCkgJmxlOyBkJm1pZGRvdDtnKHgpIGZvciBhbGwgeCAmZ2U7IDEuIEluIHByYWN0aWNlLCB0aGF0IG1lYW5zIHRoYXQgeW91IGNhbiBkcm9wIGFsbCBjb25zdGFudCBmYWN0b3JzIChlLmcuIDR4PHN1cD4zPFwvc3VwPiBpcyAmVGhldGE7KHg8c3VwPjM8XC9zdXA+KSksIGFuZCBhbGwgdGVybXMgdGhhdCBoYXZlIHNtYWxsZXIgZXhwb25lbnRzIGZvciBldmVyeSB2YXJpYWJsZSAoZS5nLiB4PHN1cD4zPFwvc3VwPiArIHg8c3VwPjI8XC9zdXA+IGlzICZUaGV0YTsoeDxzdXA+MzxcL3N1cD4pLCBiZWNhdXNlIHg8c3VwPjM8XC9zdXA+ICZsZTsgeDxzdXA+MzxcL3N1cD4gKyB4PHN1cD4yPFwvc3VwPiAmbGU7IDJ4PHN1cD4zPFwvc3VwPiBmb3IgYWxsIHggJmdlOyAxKS4gRm9yIHNvbWUgbW9yZSBleGFtcGxlcywgeDxzdXA+MjxcL3N1cD4gKyA3IGlzICZUaGV0YTsoeDxzdXA+MjxcL3N1cD4pLCBhbmQgeDxzdXA+MjxcL3N1cD55ICsgeTxzdXA+MjxcL3N1cD54ICsgeHkgKyB4PHN1cD4yPFwvc3VwPiBpcyAmVGhldGE7KHg8c3VwPjI8XC9zdXA+eSArIHk8c3VwPjI8XC9zdXA+eCkuPFwvcD5cclxuXHJcbjxwPkEgc2xpZ2h0bHkgbGVzcyBvYnZpb3VzIGNvbnNlcXVlbmNlIGlzIHRoYXQgY2VydGFpbiBtaXhlZCB0ZXJtcyBjYW4gYmUgb21pdHRlZCBhcyB3ZWxsLiBGb3IgaW5zdGFuY2UsIHg8c3VwPjI8XC9zdXA+ICsgMTd4eSArIHk8c3VwPjI8XC9zdXA+IGlzICZUaGV0YTsoeDxzdXA+MjxcL3N1cD4gKyB5PHN1cD4yPFwvc3VwPiksIGJlY2F1c2UgZWl0aGVyIHggJmxlOyB5LCB3aGljaCBpbXBsaWVzIHRoYXQgeDxzdXA+MjxcL3N1cD4gKyAxN3h5ICsgeTxzdXA+MjxcL3N1cD4gJmxlOyB5PHN1cD4yPFwvc3VwPiArIDE3eTxzdXA+MjxcL3N1cD4gKyB5PHN1cD4yPFwvc3VwPiAmbGU7IDE5KHg8c3VwPjI8XC9zdXA+ICsgeTxzdXA+MjxcL3N1cD4pLCBvciB4ICZnZTsgeSwgd2hpY2ggaW1wbGllcyB0aGF0IHg8c3VwPjI8XC9zdXA+ICsgMTd4eSArIHk8c3VwPjI8XC9zdXA+ICZsZTsgeDxzdXA+MjxcL3N1cD4gKyAxN3g8c3VwPjI8XC9zdXA+ICsgeTxzdXA+MjxcL3N1cD4gJmxlOyAxOSh4PHN1cD4yPFwvc3VwPiArIHk8c3VwPjI8XC9zdXA+KS4gSWYgeW91IGhhdmUgcXVlc3Rpb25zIGFib3V0IHRoZSBub3RhdGlvbiwgcGxlYXNlIGFzayBmb3IgYXNzaXN0YW5jZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGlzIHRoZSBudW1iZXIgSyBvZiBpbnB1dCBkYXRhIHNldHMsIGZvbGxvd2VkIGJ5IEsgZGF0YSBzZXRzLCBlYWNoIGJlaW5nIG9uZSBwcm9ncmFtIChhbmQgZWFjaCBmb2xsb3dlZCBieSBhbiBlbXB0eSBsaW5lKS48XC9wPlxyXG5cclxuPHA+QSBwcm9ncmFtIGNvbnNpc3RzIG9mIG9ubHkgdGhlIGZvdXIgY29tbWFuZHMgYWJvdmUsIGFuZCB3aWxsIGFsd2F5cyBiZSBzeW50YWN0aWNhbGx5IGNvcnJlY3QgKGUuZy4gdGhlIGxvb3AgYW5kIGVuZGxvb3AgY29tbWFuZHMgbWF0Y2gsIHRoZXJlIGlzIGV4YWN0bHkgb25lIDxjb2RlPmVuZHByb2dyYW08XC9jb2RlPiBvdXRzaWRlIHRoZSBvdXRlcm1vc3QgPGNvZGU+bG9vcDxcL2NvZGU+IGFuZCBzbyBmb3J0aCkuIEVhY2ggY29tbWFuZCB3aWxsIGJlIG9uIGEgbGluZSBieSBpdHNlbGYuIFRoZXJlIHdpbGwgYmUgZXhhY3RseSBvbmUgd2hpdGVzcGFjZSBiZXR3ZWVuIHRoZSBzdHJpbmcgPGNvZGU+bG9vcDxcL2NvZGU+IGFuZCBpdHMgcGFyYW1ldGVyLCBhbmQgbm8gdGFidWxhdG9yIG9yIHdoaXRlc3BhY2UgY2hhcmFjdGVycyBhbnl3aGVyZSBlbHNlIChiZXNpZGVzIHRoZSBsaW5lIGJyZWFrcykuIFRoZSBuZXN0aW5nIGRlcHRoIG9mIDxjb2RlPmxvb3A8XC9jb2RlPiBzdGF0ZW1lbnRzIHdpbGwgYmUgYXQgbW9zdCA1MCBpbiBhbGwgZXhhbXBsZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIG91dHB1dCAmbGRxdW87RGF0YSBTZXQgeDomcmRxdW87IG9uIGEgbGluZSBieSBpdHNlbGYsIHdoZXJlIHggaXMgaXRzIG51bWJlci4gT24gdGhlIG5leHQgbGluZSwgb3V0cHV0IHRoZSBhc3ltcHRvdGljIGNvbXBsZXhpdHkgb2YgdGhlIHByb2dyYW0uIFRoZSBvcmRlciBvZiB0aGUgdGVybXMgc2hvdWxkIGJlIGJ5IG5vbi1pbmNyZWFzaW5nIGV4cG9uZW50cyBvZiB4LCBicmVha2luZyB0aWVzIGJ5IG5vbi1pbmNyZWFzaW5nIGV4cG9uZW50cyBvZiB5LiBNYWtlIHlvdXIgb3V0cHV0IGxvb2sgJmxkcXVvO21hdGhlbWF0aWNhbGx5IG5lYXQmcmRxdW87LCBlLmcuIG91dHB1dCB4eSBpbnN0ZWFkIG9mIHheMXleMSBhbmQgeCBpbnN0ZWFkIG9mIHheMXleMC4gVGhlIG91dHB1dCBmb3IgZWFjaCBkYXRhIHNldCBzaG91bGQgYmUgZm9sbG93ZWQgYnkgYW4gZW1wdHkgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

University > The USC Programming Contest > Fall 2007 D번