All Tracks Problem

Final Destination
/

Algorithms, Breadth-first search, Easy-Medium

Problem
Editorial
Analytics

You’ve just come out of a theatre after watching X-Men, and you’re thinking of mutation. You cannot just move on. You’re stuck on mutation, and its issues. But unlike mutants in the movie, you’re just another Mathematician, with the four basic powers:

  1. Addition
  2. Subtraction
  3. Division
  4. Multiplication

And with every power there’s associated a number. And you are allowed to use only the number associated with a power, when using that power. After deciding all those rules, and powers, you feel better about yourself and decide to take on the task of converting one number to another, using your powers. But, here’s the tricky part -

NOTE:
All calculations done using your powers should be done in a way so that they never exceed 1000000 and should never go below 2 as well.

You’ve to output the minimum number of minimum number of steps to reach from a to b using powers.

input:
First line of input contains T, number of test cases . Each test case contains two lines , first line contains two integers a and b, second line contains four integer that Mul, Div, Add and Sub numbers associated with power of Multiplication, Division, Addition and Subtraction.

Output:
For each test case print the minimum number of steps to reach from a to b using powers, if not possible print -1 .

Constraints:
1<=T<=100
1<=a<=b<=10000
1<=Mul<=Div<=1000
0<=Add<=Sub<=1000

SAMPLE INPUT
3
2 4
2 1 1 1
2 4
1 2 3 4
2 5
1 2 3 4
SAMPLE OUTPUT
1
3
1
Explanation

Test Case#1:
Source= 2 and Destination=4
Value of Mul=2, Div=1, Add=1 and Sub=1
You can go from source to destination with one step that is 2*2=4.

Test Case#2:
Source=2 and Destination =4 Value of Mul=1, Div=2, Add=3 and Sub=4 Then the possible path will be:
Step1: 2+3 = 5
Step2: 5+3 = 8 Step3: 8/2= 4

Note: You can't use Div operation is first step because *All calculations done using your powers should be done in a way so that they never exceed 1000000 and should never go below 2 as well. *

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?