랜덤 워크

랜덤 알고리즘은 오늘날 널리 쓰인다. 예를 들어 암호학(소수 판정 등)에서 흔히 사용된다. 일반적인 결정론적 알고리즘과 달리, 랜덤 알고리즘은 실행 경로가 고정되어 있지 않을 수 있다. 특정 지점에서 "동전을 던져" 그 결과에 따라 어디로 갈지 정하기 때문이다.

예를 들어 다음과 같은 지점을 생각해 보자.

x = random(1);   // random(1)은 [0, 1)에서 균등하게 뽑은 실수를 반환한다
IF x > 0.3 GOTO ...

프로그램이 이 지점에 도달하면 난수 $x$를 하나 뽑는다. $x > 0.3$이면 다른 곳으로 점프하고, 그렇지 않으면 그대로 다음 줄로 진행한다. 프로그램은 거리를 걷는 술 취한 사람처럼 헤매므로, 그 경로를 미리 예측할 수 없다.

이 문제에서 여러분이 할 일은 선택한 프로시저의 기대 실행 시간을 계산하는 간단한 랜덤 프로그램 평가기를 만드는 것이다.

간단한 랜덤 프로그램은 다음과 같이 정의된다.

1. 예약어(대소문자 구분): NOP, IF, GOTO, END, PROC, PROG_START, PROG_END.
2. 프로그램은 PROG_START로 시작하여 PROG_END로 끝난다.
3. 프로그램에는 하나 이상의 프로시저가 있다.
4. 각 프로시저는 PROC [이름]으로 시작한다. [이름]은 문자와 숫자로만 이루어지며 예약어가 될 수 없다.
5. 프로시저는 END;로 끝난다.
6. 프로시저에는 하나 이상의 명령이 있다(END;는 명령이 아니다). 명령 하나를 실행하는 데 정확히 한 시간 단위가 걸린다.
7. 명령은 다음 형식 중 하나이다.
   • NOP; — 다음 시간 단위에 다음 줄로 진행한다.
   • IF x>[임계값] GOTO [줄 번호]; — $[0, 1)$에서 균등하게 $x$를 뽑아, $x >$ 임계값이면 다음에 [줄 번호]를 실행하고, 아니면 다음 줄을 실행한다.
   • IF x<[임계값] GOTO [줄 번호]; — $x$를 뽑아, $x <$ 임계값이면 다음에 [줄 번호]를 실행하고, 아니면 다음 줄을 실행한다.
   • IF x>[임계값] PROC [이름]; — $x$를 뽑아, $x >$ 임계값이면 프로시저 [이름]을 끝까지 실행한 뒤 이 명령의 다음 줄로 돌아온다. 아니면 다음 줄로 진행한다.
   • IF x<[임계값] PROC [이름]; — $x$를 뽑아, $x <$ 임계값이면 프로시저 [이름]을 끝까지 실행한 뒤 다음 줄로 돌아온다. 아니면 다음 줄로 진행한다.
8. 프로시저는 END;에 도달하는 즉시 끝난다.
9. 각 프로시저에서 줄 번호는 1부터 시작한다. 첫 번째 명령이 1번 줄, 두 번째가 2번 줄이며, END;가 마지막 줄이다.

편의를 위해 다음을 가정한다.

1. 모든 IF 조건은 난수와 상수 임계값의 비교이다.
2. 서로 다른 IF 문의 난수들은 독립이다. 같은 IF x>0.5 명령이 두 개 있더라도 각각의 $x$는 독립적으로 뽑힌다.
3. 프로시저 사이에는 (직접이든 간접이든) 상호 재귀 참조가 없다.
4. 모든 명령에서, 결국 그 프로시저의 끝에 도달할 확률이 양수이다. 따라서 끝에 항상 도달할 수 있고, 모든 기대 시간은 유한하다.
5. 프로그램의 프로시저 개수는 1보다 크고 100보다 작다.
6. 이 문제의 모든 문자열 길이는 100자 이하이다.

각 기대 실행 시간을 소수점 아래 정확히 3자리로 반올림하여 보고하라.

입력은 위에서 설명한 하나의 랜덤 프로그램(프로시저 하나 이상)과 그 뒤를 잇는 요청 목록으로 이루어진다. 각 요청은 기대 실행 시간을 보고해야 할 프로시저의 이름 하나가 적힌 줄이다. 요청 목록은 REQUEST_END가 적힌 줄로 끝난다(REQUEST_END라는 이름의 프로시저는 없다).

각 요청에 대해, 요청한 프로시저의 기대 실행 시간을 소수점 아래 3자리로 반올림하여 한 줄에 출력한다.