시간 초과

지금까지 문제를 풀면서 "시간 초과" 메시지를 본 적이 있을 것이다. 시간 초과는 여러 이유로 발생하지만, 대개 제출한 코드의 시간복잡도가 문제에서 허용하는 최대 시간복잡도를 넘어설 때 생긴다.

이번 문제에서는 시간복잡도에 대한 이해를 높여 시간 초과를 덜 겪도록 연습해 보자. 어떤 소스 코드가 주어지면, 그 코드의 시간복잡도를 계산하면 된다.

실제 코드를 그대로 분석하기는 어려우므로, 다음과 같이 단순화한 방식으로 계산한다. 프로그램은 오직 네 개의 명령어로만 이루어진다고 가정한다.

• basic : 사칙연산이나 값 할당 같은 기본 연산
• loop : 반복문의 시작
• endloop : 반복문의 끝
• endprogram : 프로그램의 종료

분석 규칙은 다음과 같다.

• 프로그램에는 위 네 명령어만 등장한다.
• loop는 항상 하나의 인자를 가지며, 자신 이후 처음 만나는 endloop와 짝을 이루어 하나의 반복문이 된다.
• loop의 인자는 x, y, 또는 양의 정수이다. x와 y는 상수이며 실행 도중 값이 바뀌지 않는다. 반복문은 이 인자만큼 반복한다.
• 어떤 loop 안에 basic이 하나도 없다면 의미 없는 반복문이므로, 인자 값과 관계없이 즉시 종료된다(실행 횟수에 기여하지 않는다).
• 어떤 loop 안에 basic이 여러 개 있더라도 하나만 있는 것으로 간주해도 된다.
• basic 한 번의 실행에는 상수 시간이 걸린다.

시간복잡도는 basic의 실행 횟수를 변수 x, y에 대한 함수로 나타낸 뒤 빅오 표기법으로 정리한 것이다.

빅오 표기법의 정의는 다음과 같다. 적절한 양의 상수 $c$와 $d$를 골라 $1$ 이상인 모든 입력에 대해 $c \cdot g \le f \le d \cdot g$가 성립하게 만들 수 있다면, $f$의 빅오 표기는 $O(g)$이다. 쉽게 말하면 상수 계수는 모두 떼어낼 수 있다는 뜻이다.

예를 들어 $4x^3$의 빅오 표기는 $x^3$이다. 또한 더 높은 차수의 항이 있으면 그보다 낮은 차수의 항은 통째로 없앨 수 있다. 예를 들어 $x^3 + x^2$은 $x^3$, $x^2 + 7$은 $x^2$이 된다.

단, 서로 다른 변수가 섞여 있어 다른 항보다 확실히 작다고 말할 수 없는 항은 모두 남겨 두어야 한다. 예를 들어 $x^2y + y^2x + xy + x^2$의 빅오 표기는 $x^2y + y^2x$이고, $x^2 + 17xy + y^2$의 빅오 표기는 $x^2 + y^2$이다.

첫 줄에 테스트 케이스의 수 $K$가 주어진다. 각 테스트 케이스(프로그램)는 빈 줄로 구분된다.

각 프로그램은 위에서 설명한 네 명령어로만 이루어지며, endprogram은 가장 바깥 반복문보다 아래에 정확히 하나 존재한다.

loop와 그 인자 사이에는 공백이 정확히 하나 있으며, 이 경우를 제외하면 프로그램 안에 불필요한 공백이나 다른 문자는 없다. 반복문의 최대 중첩 깊이는 $50$이다.

각 테스트 케이스마다 먼저 Data Set K:를 출력한 뒤($K$는 1부터 시작하는 테스트 케이스 번호), 그 프로그램의 시간복잡도를 출력한다.

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

각 항은 최대한 축약해서 출력한다. 예를 들어 x^1y^1은 xy로, x^1y^0은 x로 출력한다. 시간복잡도가 상수이면 1을, basic이 한 번도 실행되지 않으면 0을 출력한다. 여러 항은 +로 이어 붙인다.

테스트 케이스 사이에는 빈 줄을 하나 출력한다.