DBAL - Jon and Cow
Farmer Jon has two cows. He loves his cows very much. One cow gives exactly A liters milk in a day. Other cow gives exactly B liters milk in a day. But Farmer Jon is a very busy person. He can collect one cow’s milk in a day.
Nowadays farmer Jon need a little bit more money to create a nice house for his cows. So he wants to sale exactly N liters milk to the buyer.
Now Farmer Jon asked to you to calculate what is the minimum days needed to make exactly N liters of milk.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains three integers A, B (1 ≤ A,B ≤= 15) and N (1 ≤ N ≤ 105).
Output
For each case, print the case number and the minimum number of days needed to make exactly N liters of milk. If it is not possible to make exactly N liters of milk print “Not Possible” (without quotes)
Sample Input |
Output for Sample Input |
3 2 3 7 2 3 12 2 2 11 |
Case 1: 3 Case 2: 4 Case 3: Not Possible |
Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology
hide comments
nadstratosfer:
2018-08-10 22:15:52
BFS works but O(max(A, B)) is way faster. Anyone found O(1)? Nice tutorial problem. |
Added by: | Alim |
Date: | 2014-05-12 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |