시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 2 2 40.000%

문제

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

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

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

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

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

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

  • 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+bG9vcFx1YmIzOFx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODA0XHViMmVjXHVjNzc4XHVjNzkwXHViOTdjIFx1YWMxNlx1YjI5NFx1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCBcdWQ1NmRcdWMwYzEgeCBcdWI2MTBcdWIyOTQgeVx1Yzc3NFx1YmE3MCwgeCx5XHViMjk0IFx1YzBjMVx1YzIxOFx1Yzc3NFx1YWNlMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjMmU0XHVkNTg5IFx1YjNjNFx1YzkxMSBcdWM3YWNcdWQ1NjBcdWIyZjlcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM3NzQgXHVjODA0XHViMmVjXHVjNzc4XHVjNzkwXHViOWNjXHVkMDdjIFx1YjhlOFx1ZDUwNFx1Yjk3YyBcdWJjMThcdWJjZjVcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM3N2MgXHVjNWI0XHViNWE0IGxvb3BcdWJiMzggXHViMGI0XHVjNWQwIGJhc2ljIFx1Y2Y1NFx1YjRkY1x1YWMwMCBcdWQ1NThcdWIwOThcdWIzYzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCBcdWM3NThcdWJiZjhcdWM1YzZcdWIyOTQgXHViOGU4XHVkNTA0XHVjNzc0XHViYmMwXHViODVjIFx1YzgwNFx1YjJlY1x1Yzc3OFx1Yzc5MFx1Yzc1OCBcdWFjMTJcdWM1ZDAgXHVhZDAwXHVhY2M0XHVjNWM2XHVjNzc0IFx1YWRmOCBsb29wXHViOTdjIFx1Yzk4OVx1YzJkYyBcdWM4ODVcdWI4Y2NcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM3N2MgXHVjNWI0XHViNWE0IGxvb3BcdWJiMzggXHViMGI0XHVjNWQwIGJhc2ljIFx1Y2Y1NFx1YjRkY1x1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWQ1NWMgXHVhYzFjXHVjNzU4IGJhc2ljIFx1Y2Y1NFx1YjRkY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWIzYzQgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5iYXNpYyBcdWNmNTRcdWI0ZGNcdWIyOTQgXHVjMmU0XHVkNTg5XHVjNWQwIFx1YzBjMVx1YzIxOCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzJkY1x1YWMwNFx1YmNmNVx1YzdhMVx1YjNjNFx1YjI5NCBiYXNpYyBcdWFkNmNcdWJiMzhcdWM3NTggXHVjMmU0XHVkNTg5IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWQ1NjhcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YjRhNCBcdWJlNDVcdWM2MjQgXHVkNDVjXHVhZTMwXHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzVlYyBcdWJkODRcdWMxMWRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmU0NVx1YzYyNCBcdWQ0NWNcdWFlMzBcdWJjOTVcdWM3NTggXHVjODE1XHVjNzU4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWM3ODRcdWM3NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzBjMVx1YzIxOCBjXHVjNjQwIGRcdWI5N2MgXHVjNzk4IFx1YWNlOFx1Yjc3YywgMSBcdWM3NzRcdWMwYzFcdWM3NzggXHViYWE4XHViNGUwIHhcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIGMqZyh4KSAmbGU7IGYoeCkgJmxlOyBkKmcoeClcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHVhYzhjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IGYoeClcdWM3NTggXHViZTQ1XHVjNjI0IFx1ZDQ1Y1x1YWUzMFx1YjI5NCBPKGcpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ODAgXHViMzU0IFx1YzI3ZFx1YWM4YyBcdWMxMjRcdWJhODVcdWQ1NThcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWMwYzFcdWMyMThcdWJkODBcdWIyOTQgXHViNWJjXHVjNWI0XHViMGI0XHViYzg0XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IDR4IDxzdXA+MzxcL3N1cD5cdWM3NTggXHViZTQ1XHVjNjI0IFx1ZDQ1Y1x1YWUzMFx1YjI5NCB4PHN1cD4zPFwvc3VwPlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHVjNWI0XHViNWE0IFx1ZDU2ZFx1YmNmNFx1YjJlNCBcdWIwYWVcdWM3NDAgXHVjYzI4XHVjMjE4XHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWQ1NmRcdWI0ZTRcdWM3NDAgXHVkMWI1XHVjOWY4XHViODVjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCB4IDxzdXA+MzxcL3N1cD4gKyB4PHN1cD4yPFwvc3VwPlx1Yzc1OCBcdWJlNDVcdWM2MjQgXHVkNDVjXHVhZTMwXHViMjk0IHg8c3VwPjM8XC9zdXA+XHVjNzc0IFx1YjQxOFx1YmE3MCwgeDxzdXA+MjxcL3N1cD4gKyA3XHVjNzU4IFx1YmU0NVx1YzYyNCBcdWQ0NWNcdWFlMzBcdWIyOTQgeDxzdXA+MjxcL3N1cD5cdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNWVjXHViN2VjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViY2MwXHVjMjE4XHVhYzAwIFx1YzExZVx1YzVlY1x1Yzc4OFx1YjJlNFx1YmE3NCBcdWIyZTRcdWI5NzggXHVkNTZkXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNFx1YWNlMCBcdWQ2NTVcdWMyZTBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWQ1NmRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1ZDQ1Y1x1YWUzMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIHggPHN1cD4yPFwvc3VwPnkgKyB5PHN1cD4yPFwvc3VwPnggKyB4eSArIHg8c3VwPjI8XC9zdXA+IFx1Yzc1OCBcdWJlNDVcdWM2MjQgXHVkNDVjXHVhZTMwXHViMjk0IHg8c3VwPjI8XC9zdXA+eSArIHk8c3VwPjI8XC9zdXA+eFx1YWMwMCBcdWI0MThcdWJhNzAsIHg8c3VwPjI8XC9zdXA+ICsgMTd4eSArIHk8c3VwPjI8XC9zdXA+IFx1Yzc1OCBcdWJlNDVcdWM2MjQgXHVkNDVjXHVhZTMwXHViMjk0IHg8c3VwPjI8XC9zdXA+ICsgeTxzdXA+MjxcL3N1cD5cdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YjEyNCBcdWFjMDBcdWM5YzBcdWM3NTggXHViYTg1XHViODM5XHVjNWI0XHViODVjXHViOWNjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIGVuZHByb2dyYW1cdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWMwMFx1YzdhNSBcdWJjMTRcdWFlNjVcdWM3NTggbG9vcFx1YmIzOFx1YmNmNFx1YjJlNCBcdWIzNTQgXHVjNTQ0XHViNzk4XHVjNWQwIFx1YjJlOCBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5sb29wXHVjNjQwIFx1YzgwNFx1YjJlY1x1Yzc3OFx1Yzc5MCB4IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWIyZTggXHVkNTVjXHVhYzFjXHVjNzU4IFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWIwYjRcdWM1ZDAgXHVjNWI0XHViNWE0IFx1YWNmNVx1YmMzMVx1Yzc3NFx1YjA5OCBcdWM3NzRcdWMwYzFcdWQ1NWMgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5sb29wXHViYjM4XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWM5MTFcdWNjYTkgXHVkNjlmXHVjMjE4XHViMjk0IDUwXHVkNjhjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IERhdGEgU2V0IEs6IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0LCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWJjZjVcdWM3YTFcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkNTZkXHVjNzQwIHhcdWM3NTggXHVjYzI4XHVjMjE4XHVhYzAwIFx1YjE5Mlx1Yzc0MCBcdWFjODNcdWJkODBcdWQxMzAsIHhcdWM3NTggXHVjYzI4XHVjMjE4XHVhYzAwIFx1YWMxOVx1YjJlNFx1YmE3NCB5XHVjNzU4IFx1Y2MyOFx1YzIxOFx1YWMwMCBcdWIxOTJcdWM3NDAgXHVhYzgzXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQ1NmRcdWM3NDQgXHVjZDljXHViODI1XHVkNTYwIFx1YjU1MCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjZDk1XHVjNTdkXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgeF4xeV4xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWIzMDBcdWMyZTBcdWM1ZDAgeHlcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgeF4xeV4wXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWIzMDBcdWMyZTBcdWM1ZDAgeFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNjc4XHVjNzU4IFx1Y2Q5Y1x1YjgyNSBcdWQ2MTVcdWMyZGRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjBiNFx1YzZhOVx1Yzc0MCBcdWM2MDhcdWM4MWMgXHVjZDljXHViODI1XHVjNzQ0IFx1YmNmNFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkNCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTE3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRpbWUgTGltaXQgRXhjZWVkZWQiLCJkZXNjcmlwdGlvbiI6IjxwPiZsZHF1bztUaW1lIGxpbWl0IGV4Y2VlZGVkJnJkcXVvOyBpcyBhbm90aGVyIGZhdm9yaXRlIGVycm9yIG1lc3NhZ2UuIE1vc3QgZnJlcXVlbnRseSwgdGhlIGNhdXNlIGlzIGVpdGhlciBhbiBpbmZpbml0ZSBsb29wIHNvbWV3aGVyZSBpbiB5b3VyIHByb2dyYW0sIG9yICZtZGFzaDsgbW9yZSBvZnRlbiAmbWRhc2g7IGEgdmVyeSBzbG93IGJydXRlLWZvcmNlIHNvbHV0aW9uIHRvIGEgcHJvYmxlbSB0aGF0IHNob3VsZCBiZSBzb2x2ZWQgbW9yZSBlbGVnYW50bHkuIFRoZSBwcm9ibGVtIGlzIG5vdCB0aGF0IHdlIHRlcm1pbmF0ZSB0aGUgcHJvZ3JhbSBhZnRlciAxIG1pbnV0ZTsgeW91ciBzb2x1dGlvbnMgd291bGQgcHJvYmFibHkgcnVuIDEwPHN1cD4xMDA8XC9zdXA+IHllYXJzIGlmIHRoZXkgdXNlIGJydXRlLWZvcmNlIGZvciBhIHByb2JsZW0gd2hlcmUgdGhleSBzaG91bGRuJnJzcXVvO3QuPFwvcD5cclxuXHJcbjxwPlRoZSB3aG9sZSB0aGluZyBtaWdodCBiZSBhIGxpdHRsZSBlYXNpZXIgaWYgeW91IGhhZCBhIGxpdHRsZSBwcm9ncmFtIHRvIGZpZ3VyZSBvdXQgdGhlIHJ1bnRpbWUgY29tcGxleGl0eSBvZiB5b3VyIGNvZGUuIEluIGdlbmVyYWwsIHRoaXMgaXMgYW4gdW5kZWNpZGFibGUgcHJvYmxlbSAoaS5lLiwgdGhlcmUgY2Fubm90IGJlIGFueSBjb21wdXRlciBwcm9ncmFtIGFsd2F5cyBnZXR0aW5nIGl0IHJpZ2h0LCBvbmUgb2YgdGhlIGNvb2wgcmVzdWx0cyB5b3UgbGVhcm4gaW4gQ1NDSSAzMDMpLiBTbyBpbnN0ZWFkLCB3ZSB3aWxsIHJlc3RyaWN0IG91ciBhdHRlbnRpb24gdG8gYSBzZXZlcmVseSByZXN0cmljdGVkICZsZHF1bztwcm9ncmFtbWluZyBsYW5ndWFnZSZyZHF1bzsgZm9yIHdoaWNoIHRoZSBwcm9ibGVtIGNhbiBiZSBzb2x2ZWQgYWdhaW4uIFByb2dyYW1zIG9ubHkgY29uc2lzdCBvZiBmb3VyIGtpbmRzIG9mIHN0YXRlbWVudHMsIG5hbWVseSA8Y29kZT5iYXNpYzxcL2NvZGU+LCA8Y29kZT5sb29wPFwvY29kZT4sIDxjb2RlPmVuZGxvb3A8XC9jb2RlPiBhbmQgPGNvZGU+ZW5kcHJvZ3JhbTxcL2NvZGU+LiBFYWNoIHN0YXRlbWVudCBpcyBvbiBhIGxpbmUgYnkgaXRzZWxmLCB0aGVyZSBhcmUgbm8gc2VtaWNvbG9ucyBvciBhbnkgb3RoZXIgcHVuY3R1YXRpb24sIGFuZCBsb29wIGlzIHRoZSBvbmx5IGNvbW1hbmQgd2l0aCBhIHBhcmFtZXRlci4gVGhhdCBwYXJhbWV0ZXIgaXMgZWl0aGVyIGEgcG9zaXRpdmUgaW50ZWdlciBudW1iZXIsIG9yIG9uZSBvZiB0aGUgdHdvIHZhcmlhYmxlcyAmbHNxdW87eCZyc3F1bzsgYW5kICZsc3F1bzt5JnJzcXVvOyAob3VyIHNpbXBsaWZpZWQgcHJvZ3JhbW1pbmcgbGFuZ3VhZ2UgaGFzIG9ubHkgdHdvIHZhcmlhYmxlcyksIGRlbm90aW5nIHRoYXQgdGhlIGJvZHkgYmV0d2VlbiB0aGUgPGNvZGU+bG9vcDxcL2NvZGU+IGFuZCB0aGUgY29ycmVzcG9uZGluZyBlbmRsb29wIGlzIGV4ZWN1dGVkIHRoYXQgbWFueSB0aW1lcy48XC9wPlxyXG5cclxuPHA+PGNvZGU+YmFzaWM8XC9jb2RlPiBkZW5vdGVzIGEgYmFzaWMgc3RhdGVtZW50IChsaWtlIGFzc2lnbm1lbnQsIGFkZGl0aW9uLCBvciBzb21lIG90aGVyIHN0dWZmIHRoYXQgZG9lcyBub3QgbWF0dGVyIGZvciBjb21wbGV4aXR5IGFuYWx5c2lzKSwgYW5kIDxjb2RlPmVuZHByb2dyYW08XC9jb2RlPiBpcyB0aGUgZW5kIG9mIHRoZSBwcm9ncmFtLiBOb3RpY2UgdGhhdCB0aGUgbnVtYmVyIG9mIHRpbWVzIGEgbG9vcCBpcyBleGVjdXRlZCBpcyBhbHdheXMgYSBjb25zdGFudCAoZWl0aGVyIHRoZSB2YXJpYWJsZSBvciBhIG51bWVyaWNhbCBvbmUpLCBzaW5jZSB2YXJpYWJsZXMgY2Fubm90IGJlIGFzc2lnbmVkIHZhbHVlcy4gQWxzbywgd2UgYXNzdW1lIHRoYXQgb3VyIGNvbXBpbGVyIGlzIHNtYXJ0IGVub3VnaCB0byBwcnVuZSBhd2F5IGxvb3BzIHdpdGggbm8gPGNvZGU+YmFzaWM8XC9jb2RlPiBzdGF0ZW1lbnQgYW55d2hlcmUgaW4gdGhlaXIgYm9kaWVzLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIGRldGVybWluZSwgaW4gYmlnLU9oIChPKSBub3RhdGlvbiwgdGhlIGNvbXBsZXhpdHkgb2YgdGhlIHByb2dyYW0sIGkuZS4gdGhlIHRvdGFsIG51bWJlciBvZiB0aW1lcyB0aGF0IGFueSBiYXNpYyBzdGF0ZW1lbnQgaXMgZXhlY3V0ZWQuIFlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IGFuIGFzeW1wdG90aWNhbGx5IHRpZ2h0IGJvdW5kIG9mIHRoZSBmb3JtICZUaGV0YTsoLiAuIC4pLjxcL3A+XHJcblxyXG48cD5XZSBzYXkgdGhhdCBhIGZ1bmN0aW9uIGYgaXMgJlRoZXRhOyhnKSBmb3IgYW5vdGhlciBmdW5jdGlvbiBnLCBpZiB0aGVyZSBhcmUgcG9zaXRpdmUgY29uc3RhbnRzIGMgYW5kIGQgd2l0aCBjJm1pZGRvdDtnKHgpICZsZTsgZih4KSAmbGU7IGQmbWlkZG90O2coeCkgZm9yIGFsbCB4ICZnZTsgMS4gSW4gcHJhY3RpY2UsIHRoYXQgbWVhbnMgdGhhdCB5b3UgY2FuIGRyb3AgYWxsIGNvbnN0YW50IGZhY3RvcnMgKGUuZy4gNHg8c3VwPjM8XC9zdXA+IGlzICZUaGV0YTsoeDxzdXA+MzxcL3N1cD4pKSwgYW5kIGFsbCB0ZXJtcyB0aGF0IGhhdmUgc21hbGxlciBleHBvbmVudHMgZm9yIGV2ZXJ5IHZhcmlhYmxlIChlLmcuIHg8c3VwPjM8XC9zdXA+ICsgeDxzdXA+MjxcL3N1cD4gaXMgJlRoZXRhOyh4PHN1cD4zPFwvc3VwPiksIGJlY2F1c2UgeDxzdXA+MzxcL3N1cD4gJmxlOyB4PHN1cD4zPFwvc3VwPiArIHg8c3VwPjI8XC9zdXA+ICZsZTsgMng8c3VwPjM8XC9zdXA+IGZvciBhbGwgeCAmZ2U7IDEpLiBGb3Igc29tZSBtb3JlIGV4YW1wbGVzLCB4PHN1cD4yPFwvc3VwPiArIDcgaXMgJlRoZXRhOyh4PHN1cD4yPFwvc3VwPiksIGFuZCB4PHN1cD4yPFwvc3VwPnkgKyB5PHN1cD4yPFwvc3VwPnggKyB4eSArIHg8c3VwPjI8XC9zdXA+IGlzICZUaGV0YTsoeDxzdXA+MjxcL3N1cD55ICsgeTxzdXA+MjxcL3N1cD54KS48XC9wPlxyXG5cclxuPHA+QSBzbGlnaHRseSBsZXNzIG9idmlvdXMgY29uc2VxdWVuY2UgaXMgdGhhdCBjZXJ0YWluIG1peGVkIHRlcm1zIGNhbiBiZSBvbWl0dGVkIGFzIHdlbGwuIEZvciBpbnN0YW5jZSwgeDxzdXA+MjxcL3N1cD4gKyAxN3h5ICsgeTxzdXA+MjxcL3N1cD4gaXMgJlRoZXRhOyh4PHN1cD4yPFwvc3VwPiArIHk8c3VwPjI8XC9zdXA+KSwgYmVjYXVzZSBlaXRoZXIgeCAmbGU7IHksIHdoaWNoIGltcGxpZXMgdGhhdCB4PHN1cD4yPFwvc3VwPiArIDE3eHkgKyB5PHN1cD4yPFwvc3VwPiAmbGU7IHk8c3VwPjI8XC9zdXA+ICsgMTd5PHN1cD4yPFwvc3VwPiArIHk8c3VwPjI8XC9zdXA+ICZsZTsgMTkoeDxzdXA+MjxcL3N1cD4gKyB5PHN1cD4yPFwvc3VwPiksIG9yIHggJmdlOyB5LCB3aGljaCBpbXBsaWVzIHRoYXQgeDxzdXA+MjxcL3N1cD4gKyAxN3h5ICsgeTxzdXA+MjxcL3N1cD4gJmxlOyB4PHN1cD4yPFwvc3VwPiArIDE3eDxzdXA+MjxcL3N1cD4gKyB5PHN1cD4yPFwvc3VwPiAmbGU7IDE5KHg8c3VwPjI8XC9zdXA+ICsgeTxzdXA+MjxcL3N1cD4pLiBJZiB5b3UgaGF2ZSBxdWVzdGlvbnMgYWJvdXQgdGhlIG5vdGF0aW9uLCBwbGVhc2UgYXNrIGZvciBhc3Npc3RhbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgaXMgdGhlIG51bWJlciBLIG9mIGlucHV0IGRhdGEgc2V0cywgZm9sbG93ZWQgYnkgSyBkYXRhIHNldHMsIGVhY2ggYmVpbmcgb25lIHByb2dyYW0gKGFuZCBlYWNoIGZvbGxvd2VkIGJ5IGFuIGVtcHR5IGxpbmUpLjxcL3A+XHJcblxyXG48cD5BIHByb2dyYW0gY29uc2lzdHMgb2Ygb25seSB0aGUgZm91ciBjb21tYW5kcyBhYm92ZSwgYW5kIHdpbGwgYWx3YXlzIGJlIHN5bnRhY3RpY2FsbHkgY29ycmVjdCAoZS5nLiB0aGUgbG9vcCBhbmQgZW5kbG9vcCBjb21tYW5kcyBtYXRjaCwgdGhlcmUgaXMgZXhhY3RseSBvbmUgPGNvZGU+ZW5kcHJvZ3JhbTxcL2NvZGU+IG91dHNpZGUgdGhlIG91dGVybW9zdCA8Y29kZT5sb29wPFwvY29kZT4gYW5kIHNvIGZvcnRoKS4gRWFjaCBjb21tYW5kIHdpbGwgYmUgb24gYSBsaW5lIGJ5IGl0c2VsZi4gVGhlcmUgd2lsbCBiZSBleGFjdGx5IG9uZSB3aGl0ZXNwYWNlIGJldHdlZW4gdGhlIHN0cmluZyA8Y29kZT5sb29wPFwvY29kZT4gYW5kIGl0cyBwYXJhbWV0ZXIsIGFuZCBubyB0YWJ1bGF0b3Igb3Igd2hpdGVzcGFjZSBjaGFyYWN0ZXJzIGFueXdoZXJlIGVsc2UgKGJlc2lkZXMgdGhlIGxpbmUgYnJlYWtzKS4gVGhlIG5lc3RpbmcgZGVwdGggb2YgPGNvZGU+bG9vcDxcL2NvZGU+IHN0YXRlbWVudHMgd2lsbCBiZSBhdCBtb3N0IDUwIGluIGFsbCBleGFtcGxlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgb3V0cHV0ICZsZHF1bztEYXRhIFNldCB4OiZyZHF1bzsgb24gYSBsaW5lIGJ5IGl0c2VsZiwgd2hlcmUgeCBpcyBpdHMgbnVtYmVyLiBPbiB0aGUgbmV4dCBsaW5lLCBvdXRwdXQgdGhlIGFzeW1wdG90aWMgY29tcGxleGl0eSBvZiB0aGUgcHJvZ3JhbS4gVGhlIG9yZGVyIG9mIHRoZSB0ZXJtcyBzaG91bGQgYmUgYnkgbm9uLWluY3JlYXNpbmcgZXhwb25lbnRzIG9mIHgsIGJyZWFraW5nIHRpZXMgYnkgbm9uLWluY3JlYXNpbmcgZXhwb25lbnRzIG9mIHkuIE1ha2UgeW91ciBvdXRwdXQgbG9vayAmbGRxdW87bWF0aGVtYXRpY2FsbHkgbmVhdCZyZHF1bzssIGUuZy4gb3V0cHV0IHh5IGluc3RlYWQgb2YgeF4xeV4xIGFuZCB4IGluc3RlYWQgb2YgeF4xeV4wLiBUaGUgb3V0cHV0IGZvciBlYWNoIGRhdGEgc2V0IHNob3VsZCBiZSBmb2xsb3dlZCBieSBhbiBlbXB0eSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

University > The USC Programming Contest > Fall 2007 D번