기대 오류

면접 대비

시간 제한1초메모리 제한1024 MB

요약

비밀번호 길이 n, 오타 전 입력한 글자 수 k, 오타 확률 p%가 주어질 때 계속 입력, 백스페이스, 처음부터 다시 입력 중 기대 시간이 가장 짧은 방법을 고릅니다.

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

문제

sudo 비밀번호를 입력하는 도중 손가락이 잘못된 키를 눌렀다. 터미널은 입력한 문자를 가리기 때문에 여분의 문자가 들어갔는지 알 수 없다. 비밀번호를 끝까지 입력하는 방법은 다음 세 가지다.

계속 나머지 비밀번호를 입력한다.
백스페이스를 눌러 마지막 문자를 지우고, 나머지 비밀번호를 입력한다.
처음부터 다시 입력한다.

다음 입력 속도 가정을 사용해 가장 좋은 방법을 찾아라.

비밀번호의 문자 하나를 입력하는 데 $0.1$ 초가 걸린다.
백스페이스를 누르거나 비밀번호를 제출하는 데 $0.1$ 초가 걸린다.
다시 입력하려면 모든 문자를 지워야 하며, 이 작업에 $0.3$ 초가 걸린다.
잘못된 비밀번호를 제출하면, 실패를 알아차리고 빈 입력창에서 다시 시작하는 데 $0.3$ 초가 추가로 걸린다.

비밀번호의 길이 $n$ , 손가락이 미끄러지기 전까지 올바르게 입력한 문자 수 $k$ , 잘못된 키를 눌렀을 확률 $p\%$ 가 주어진다. 잘못된 키를 눌렀다면 입력창에는 $k+1$ 개의 문자가 남는다. 이후에 추가로 실수하지 않는다고 가정할 때, 비밀번호 입력을 끝내는 기대 시간이 가장 짧은 방법을 구하라.

입력

입력은 다음과 같이 주어진다.

세 정수 $n$ , $k$ , $p$ ( $1\leq n\leq1000$ , $1\leq k\leq n$ , $0\leq p\leq100$ )가 한 줄에 주어진다. 각각 비밀번호의 문자 수, 손가락이 미끄러지기 전까지 올바르게 입력한 문자 수, 잘못된 키를 눌렀을 확률(%)이다.

출력

가장 좋은 방법을 나타내는 문자열 continue, backspace, restart 중 하나를 출력하라. 최적 방법의 기대 시간은 다른 방법보다 적어도 1밀리초 짧다고 보장된다.

예제4

예제 1
입력
```
10 8 20
```
예상 출력
```
continue
```
예제 2
입력
```
10 8 80
```
예상 출력
```
backspace
```
예제 3
입력
```
10 2 50
```
예상 출력
```
restart
```
예제 4
입력
```
10 4 55
```
예상 출력
```
restart
```