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]
Rules:
• Please solve it on your own/submit your own solution. You may be asked to build an extension to this program or an advanced variant of this type of problem in person in the future.
• You may implement the program in either C/C++/C#/VB.Net/Java. If you choose to use C or C++ please mention the compiler version that you’re using in the email.
• Submit your source code as a single file as an email attachment (Do not compress it to zip/archive format). We would compile your program into an executable and run it (e.g. c:\>X.exe TestCases.txt)
• 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
