시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 3178 665 569 25.493%

문제

유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다.

채점 시스템은 1초에 100000000(108)가지 동작을 할 수 있다.

여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라.

입력

입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다.

그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의 수를 나타내는 T랑 제한시간(초 단위) 를 나타내는 L이 주어진다. (1 <= C <= 100, 1 <= N <= 1000000, 1 <= T, L <= 10, N, T, L은 정수)

시간 복잡도는 다음과 같은 5개 중 하나로 주어진다.

  • O (N)
  • O (N^2)
  • O (N^3)
  • O (2^N)
  • O (N!)

출력

각 테스트 케이스들에 대하여 시간 초과가 나면 "TLE!", 시간 초과가 나지 않으면 "May Pass." 를 출력한다.

예제 입력 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

예제 출력 1

May Pass.
TLE!
May Pass.
May Pass.
TLE!
W3sicHJvYmxlbV9pZCI6IjExMzMyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmRjXHVhYzA0XHVjZDA4XHVhY2ZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWJlNDhcdWM3NzRcdWIyOTQgXHVjZjU0XHViNTI5XHVjNzQ0IFx1ZDU1OFx1YjJlNFx1YWMwMCBcdWMyZGNcdWFjMDQgXHVjZDA4XHVhY2ZjXHVhYzAwIFx1YjBhY1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzJkY1x1YWMwNCBcdWJjZjVcdWM3YTFcdWIzYzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzQ0XHVjODEwIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0MCAxXHVjZDA4XHVjNWQwIDEwMDAwMDAwMCgxMDxzdXA+ODxcL3N1cD4pXHVhYzAwXHVjOWMwIFx1YjNkOVx1Yzc5MVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjXHViZDg0XHViNGU0XHVjNzQwIFx1YzcyMFx1YmU0OFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjMmRjXHVhYzA0XHVjZDA4XHVhY2ZjXHVhYzAwIFx1YjA5OFx1YjI5NFx1YzljMCBcdWQ2NTVcdWM3NzhcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViNGU0XHVjNzU4IFx1YzIxOCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBDXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWFjMDQgXHViY2Y1XHVjN2ExXHViM2M0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgUywgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNzg1XHViODI1XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWJjOTRcdWM3MDQgTiwgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFRcdWI3OTEgXHVjODFjXHVkNTVjXHVjMmRjXHVhYzA0KFx1Y2QwOCBcdWIyZThcdWM3MDQpIFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IEMgJmx0Oz0gMTAwLCAxICZsdDs9IE4gJmx0Oz0gMTAwMDAwMCwgMSAmbHQ7PSBULCBMICZsdDs9IDEwLCBOLCBULCBMXHVjNzQwIFx1YzgxNVx1YzIxOCk8XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhYzA0IFx1YmNmNVx1YzdhMVx1YjNjNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIDVcdWFjMWMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+TyAoTik8XC9saT5cclxuXHQ8bGk+TyAoTl4yKTxcL2xpPlxyXG5cdDxsaT5PIChOXjMpPFwvbGk+XHJcblx0PGxpPk8gKDJeTik8XC9saT5cclxuXHQ8bGk+TyAoTiEpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgXHVjMmRjXHVhYzA0IFx1Y2QwOFx1YWNmY1x1YWMwMCBcdWIwOThcdWJhNzQgJnF1b3Q7VExFISZxdW90OywgXHVjMmRjXHVhYzA0IFx1Y2QwOFx1YWNmY1x1YWMwMCBcdWIwOThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0ICZxdW90O01heSBQYXNzLiZxdW90OyBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMzMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGltZSBMaW1pdCBFeGNlZWRlZCIsImRlc2NyaXB0aW9uIjoiPHA+QXMgeW91IHNob3VsZCBiZSBhd2FyZSBieSBub3csIG9uZSBvZiB0aGUgdmVyZGljdHMgeW91IGNhbiBnZXQgd2hlbiBzdWJtaXR0aW5nIGEgc29sdXRpb24gdG8gYSBwcm9ibGVtIGlzIFRpbWUgTGltaXQgRXhjZWVkZWQgKFRMRSkuIFRoaXMgbWVhbnMgdGhhdCB0aGUgcnVubmluZyB0aW1lIG9mIHlvdXIgc29sdXRpb24gZXhjZWVkcyB0aGUgdGltZSBsaW1pdCBzZXQgYnkganVkZ2VzLjxcL3A+XHJcblxyXG48cD5MZXQgdXMgYXNzdW1lIHRoYXQgdGhlIGp1ZGdpbmcgc2VydmVyIGNhbiBtYWtlIDEwMCwwMDAsMDAwIG9wZXJhdGlvbnMgcGVyIHNlY29uZC4gR2l2ZW4gdGhlIHRpbWUgY29tcGxleGl0eSBvZiB5b3VyIHNvbHV0aW9uIGV4cHJlc3NlZCB1c2luZyBiaWctTyBub3RhdGlvbiwgbWF4aW11bSBzaXplIG9mIHRoZSBpbnB1dCBwZXIgdGVzdCBjYXNlIE4sIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGFuZCB0aGUgdGltZSBsaW1pdCBmb3IgYWxsIGNhc2VzIEwgY2FuIHlvdXIgc29sdXRpb24gcnVuIGluIHRpbWU/PFwvcD5cclxuXHJcbjxwPkFzc3VtZSB0aGF0IHlvdXIgc29sdXRpb24gdXNlcyBvbmx5IHNpbXBsZSBvcGVyYXRpb25zIGFuZCBkaXNyZWdhcmQgYW55IG90aGVyIG92ZXJoZWFkIChlLmcuIElcL08pLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBDICgxICZsdDs9IEMgJmx0Oz0gMTAwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBDIGxpbmVzIGZvbGxvdywgZWFjaCBvZiB0aGUgZm9ybWF0PFwvcD5cclxuXHJcbjxwcmU+XHJcbiZsdDt0aW1lX2NvbXBsZXhpdHkmZ3Q7IE4gVCBMPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgTiwgVCBhbmQgTCBhcmUgaW50ZWdlcnMgYXMgZGVzY3JpYmVkIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudCAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwLDAwMCwgMSAmbHQ7PSBULEwgJmx0Oz0gMTApLiBhbmQgJmx0O3RpbWVfY29tcGxleGl0eSZndDsgaXMgb25lIG9mIHRoZSBmb2xsb3dpbmc6PFwvcD5cclxuXHJcbjxwcmU+XHJcbk8oTiksIE8oTl4yKSwgTyhOXjMpLCBPKDJeTiksIE8oTiEpPFwvcHJlPlxyXG5cclxuPHA+Tm90ZTogV2UgdXNlIGEgdmVyeSBzaW1wbGlmaWVkIGNvbXBsZXhpdHkgbW9kZWwgaGVyZSBhbmQgZmFtaWxpYXJpdHkgd2l0aCBiaWctTyBub3RhdGlvbiBpcyBub3QgcmVxdWlyZWQgKG9yIG1heSBldmVuIGJlIGRldHJpbWVudGFsKS4gSnVzdCBhc3N1bWUgdGhhdCBhcHBseWluZyBOIHRvIHRoZSBmdW5jdGlvbiBpbiB0aGUgcGFyZW50aGVzaXMgaXMgd2hhdCBnaXZlcyB5b3UgdGhlIHRvdGFsIG51bWJlciBvZiBvcGVyYXRpb25zIHlvdXIgc29sdXRpb24gd2lsbCB1c2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IG9uIG9uZSBsaW5lIGVpdGhlciAmcXVvdDtUTEUhJnF1b3Q7IGlmIHRoZSBydW5uaW5nIHRpbWUgb2YgdGhlIHNvbHV0aW9uIGV4Y2VlZHMgdGhlIHRpbWUgbGltaXQgZm9yIHRoYXQgdGVzdCBjYXNlIG9yICZxdW90O01heSBQYXNzLiZxdW90OyBpZiBpdCBkb2VzIG5vdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Calgary Collegiate Programming Contest > CCPC 2013 A번