시간 초과 판정

시간 제한2초메모리 제한256 MB

요약

복잡도 식으로 구한 f(N)에 테스트 케이스 수를 곱해 제한 시간 내 허용 연산량을 넘는지 판정합니다.

난이도: 쉬움10점 중 2점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

유빈이가 짠 프로그램이 채점에서 시간 초과를 받았다. 그래서 시간 복잡도를 직접 따져 보기로 했다.

채점 시스템은 1초에 $10^8$ 가지 동작을 처리한다. 제한 시간이 $L$ 초면 전부 합쳐 $10^8 \times L$ 가지 동작까지 허용한다.

프로그램의 시간 복잡도가 $f(N)$ 이고, 입력의 최대 범위가 $N$ , 테스트 케이스가 $T$ 개면 전체 동작 수는 $f(N) \times T$ 다. 이 값이 허용된 동작 수보다 크면 시간 초과가 나고, 크지 않으면 통과할 가능성이 있다.

각 상황마다 시간 초과가 나는지 판정하는 프로그램을 작성하라.

입력

첫째 줄에 상황의 수 $C$ 가 주어진다. ( $1 \le C \le 100$ )

다음 $C$ 개의 줄에는 시간 복잡도를 나타내는 문자열 $S$ , 입력의 최대 범위 $N$ , 테스트 케이스의 수 $T$ , 제한 시간 $L$ 이 공백으로 구분되어 주어진다. ( $1 \le N \le 10^6$ , $1 \le T \le 10$ , $1 \le L \le 10$ , $N$ , $T$ , $L$ 은 정수, $L$ 의 단위는 초)

$S$ 는 다음 다섯 가지 중 하나이며, 공백 없이 주어진다.

O(N): $f(N) = N$
O(N^2): $f(N) = N^2$
O(N^3): $f(N) = N^3$
O(2^N): $f(N) = 2^N$
O(N!): $f(N) = N!$

출력

각 상황마다 한 줄씩 판정 결과를 출력한다. 시간 초과가 나면 TLE!를, 나지 않으면 May Pass.를 출력한다.

예제4

예제 1

입력

5
O(N) 1000 10 10
O(2^N) 1000 10 10
O(N!) 2 10 10
O(N^3) 1000 1 10
O(N^3) 1001 1 10

예상 출력

May Pass.
TLE!
May Pass.
May Pass.
TLE!

예제 2

입력

5
O(N) 1 1 1
O(N^2) 1 1 1
O(N^3) 1 1 1
O(2^N) 1 1 1
O(N!) 1 1 1

예상 출력

May Pass.
May Pass.
May Pass.
May Pass.
May Pass.

예제 3

입력

4
O(N^2) 10000 1 1
O(N^2) 10001 1 1
O(N) 1000000 10 1
O(N^2) 1000000 10 10

예상 출력

May Pass.
TLE!
May Pass.
TLE!

예제 4

입력

4
O(N!) 12 1 10
O(N!) 13 1 10
O(2^N) 29 1 10
O(2^N) 30 1 10

예상 출력

May Pass.
TLE!
May Pass.
TLE!