15136번 - Fygon 2.0 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 32 | 11 | 11 | 35.484% |
문제
The new version of beloved programming language Fygon has been released! The brand new Fygon 2.0 still has only two statements. The first statement is lag. It substitutes almost any other statement. Second statement is a for loop:
for <variable> in range (<from>, <to>): <body>
- The for
loopmakes<variable>iterate from<from>to<to>, both inclusive. - If
<from>is greater than<to>,<body>is not executed at all. <variable>is a lowercase letter fromatoz, except forn, which is a variable that is defined prior to the given code snippet.<from>and<to>can be equal to any variable defined in outer loop. In addition to that,<from>can be1and<to>can ben.- The
<body>of the loop is indented by four spaces and contains at least one statement.
If you are familiar with Fygon 1.0, you can notice that, in the spirit of the best programming practices, Fygon 2.0 is not backwards compatible, since the range function now requires two parameters.
The performance of the new version is significantly improved, so you can write more nested for loops. That is why we are no longer interested in the exact number of operations, but in the asymptotic complexity of the program instead. For simplicity, all for loops are nested in a single chain and there is exactly one lag statement that is inside all for loops. All loop variables are different and are not equal to n.
Let’s define f(n) as the number of lag operations exectuted by a given Fygon program as the function of n. For non-negative integer k and positive rational number C we say that C · nk is the asymptotic complexity of the program if
\[\lim_{n \to \infty}{\frac{f(n)}{C \cdot n^k}} = 1\]
Given a Fygon 2.0 program, find its asymptotic complexity.
입력
The first line of the input contains single integer m — the number of lines in Fygon 2.0 program. Next m lines contain the program itself. The program has at least 1 and at most 20 for statements. Each for statement contains either single nested for statement or lag statement.
출력
Output numbers k and C. C should be output in the form of irreducible fraction p/q, where p and q are coprime.
예제 입력 1
4
for i in range(1, n):
for j in range(1, i):
for k in range(j, n):
lag
예제 출력 1
3 1/3
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호