1182 - SCU-B
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 98
Solved: 32
- Description
- You wish to enter a whole number onto your simple four-function calculator.
Unfortunately for you, some of the keys are broken.
Nonetheless, rather than buy a new calculator, you enjoy the challenge presented before you.
Your calculator is a very primitive one, and can only display positive numbers with up to three digits.
Initially, your display does not show anything, until you press a number key.
Any time an operation exceeds the number 999, it causes an error, and you cannot continue.
You are given which numeric keys are still functional, and which of the four operators are available to you.
Assume that the equals key is always available.
Finally, you are given the number you wish to display.
When you perform a division, your calculator performs an integer division, dropping any remainder.
Thus, pressing "23/7=" yields 3, and "3/8" yields 0.
Pressing the equals key completes any calculation,
and any subsequent key presses after pressing equals discards the current display,
and starts a new calculation.
Like most simple four function calculators,
pressing any operator has the effect of performing an "equals" on anything entered so far,
and operations are performed in exactly the order entered.
Thus, 2 + 2 * 3 = evaluates to 12 (instead of 8, as with typical order of operations).
You are to answer the minimum number of key presses necessary to display the target number.
If it is not possible to ever get your display to show the target number, output -1.
- Input
- The first line of the input data will be a integer n ( 1 <= n <= 100 ) to represent the number of test cases.
For each case there is three lines each contains a string.
The first non-empty line is the numeric keys are still functional.
The second non-empty line is the operators are available.
The third line is the target number ( 1 <= target <= 999 ).
There is a blank line before each test case. - Output
- For each test case output the answer on a single line.
The minimum number of key presses necessary to display the target number.
If it is not possible to ever get your display to show the target number, output -1. - sample input
-
2 1248 +-*/ 875 0 +*/ 5
- sample output
-
8 -1
- hint
- source
- SCUPC