BIQ-005-Accelerator



You’ve been given an assorted set of gears. Each gear has a different number of teeth – the notches on a gear that interlock with notches on another gear to transmit speed. You have a couple of belts one coupled to an input and the other for the output. You are given the rpm of the input belt Si and a minimum value So (where So > Si) so that you can increase the speed via a system of gears as shown above
You need to figure out all the possible pairs of gears that can be used to achieve an output rpm >= So.
Input
The input is specified in a file containing test-cases.
• The first line contains the number of gears that are available to you, g.
• The next line contains g numbers indicating the number of teeth on each gear, separated by spaces.
• The next line contains the number of test cases – n
o This is followed by n test cases. Each test case is specified by 2 speed values on a single line. (So here the first test case specifies that you need to design a gear-system that increases Si = 50 rpm to a value above 200 rpm)
7
20 10 4 6 40 25 100
2
50 200
35 75

Output
9
15

E.g. for raising the speed from 50 to 200, any of the following 9 pairs can be used
[100, 6] [40, 6] [25, 6] [25, 4] [20, 4] [40, 4] [100, 4] [100, 20] [100, 10]
• You may implement the program in either C/C++/Java. If you choose to use C or C++ please mention the compiler version that you’re using in the email.
• Your program must accept a string as a command line argument. It should then proceed to open the file of that name in the same/current directory, which contains one or more test cases. Output should be printed to console via printf (or equivalent).
• The program will not expect any user input. Please test your program for compile / run time errors before submitting.
• You may submit multiple submissions – strive for solutions that are elegant, memory and time efficient.
• The time limit if specified is for all the test cases to be executed; the time limit is NOT per test case