Expected Error

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sudo password of length n, a slip after k correct characters with probability p%, pick the strategy (continue, backspace, or restart) with the lowest expected typing time.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

You are typing your password at a sudo prompt when one of your fingers slips onto a wrong key. The terminal hides the characters you type, so you cannot tell whether an extra character got in. You can finish typing the password with one of three strategies.

Continue to type the rest of your password.
Press backspace to delete the last character, then type the rest of your password.
Restart typing your password from scratch.

Use these typing speed assumptions to find the best strategy.

Typing any character of your password takes $0.1$ seconds.
Pressing backspace or submitting your password takes $0.1$ seconds.
Restarting requires deleting all characters, which takes $0.3$ seconds.
If you submit a wrong password, it takes an additional $0.3$ seconds to notice the mistake and start typing at a new, empty prompt.

You are given the password length $n$ , the number of characters $k$ you typed correctly before your finger slipped, and the probability $p\%$ that you pressed a wrong key, which leaves you with $k+1$ characters. Assuming you make no further errors, determine which strategy has the lowest expected time to finish typing your password.

Input

The input consists of:

One line with three integers $n$ , $k$ , and $p$ ( $1\leq n\leq1000$ , $1\leq k\leq n$ , $0\leq p\leq100$ ): the number of characters in your password, the number of characters you typed correctly before your finger slipped, and the probability percentage that you pressed a wrong key.

Output

Output one of the strings continue, backspace, or restart for the optimal strategy. It is guaranteed that the optimal strategy's expected time is at least one millisecond shorter than that of the other strategies.

Examples4

Example 1
Input
```
10 8 20
```
Expected output
```
continue
```
Example 2
Input
```
10 8 80
```
Expected output
```
backspace
```
Example 3
Input
```
10 2 50
```
Expected output
```
restart
```
Example 4
Input
```
10 4 55
```
Expected output
```
restart
```