Opening The Ballot Box
All submissions for this problem are available.
Now that the votes have been casted, its time to count them. The ballot box has been locked with a secret code and has been handled to the Election Commission for
counting. The ballot box is very secure. It has 5 digits on its lock and only a particular combination of the digits can unlock it. The digits on the lock can be
changed only with the help of a laser machine.
The laser machine is very unique. It has K keys (with a number on each key) on it. In each step, it
multiplies the 5 digit number on the ballot box with any of its keys and then takes the remainder with 105 so as to make the number back to 5 digits. Note
that numbers are have leading 0's in case it is less than 5 digits. But using the laser machine is very expensive. Each step costs C Rupees. So the election
commission wants to know the minimum cost to unlock the ballot box.
Given the initial code, the final code (which unlocks the box), the K Keys and the cost per operation C, your job is to help find the minimum cost to
unlock the box, or report that the box cannot be opened.
The first line of the input consists of the number of cases (T). T test cases follows. Each test case begins with a line containing 4 numbers
K C I F,
where K is the number of Keys on the laser, C is the cost of using laser once, I is a 5 digit initial code and F is a 5 digit final code to unlock. Next line contains
K numbers, keys which are the keys on the laser machine.
For each test case, output a line with one number which is the minimum cost to open the box. If the box can never be opened output -1 instead.
T ≤ 50
1 ≤ K ≤ 10
1 ≤ C ≤ 107
I, F are 5 digit numbers and can have leading zero's. 0 ≤ Keys ≤ 105
2 2 10 00002 00016 2 4 2 10 00002 00001 2 4
- In the first case, you can use the key with number 2 to first reach to 4 and then use key 4 to reach 16. So laser was used two times.
- In the second case, whatever you multiply, you will never be able to reach an odd number.
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.