Chef and Water Car solution codechef

Chef and Water Car solution codechef

Chef is a great mechanic. As the cost of petrol is increasing day by day he decided to build a water car to take his girlfriend Natasha on a date. Water car has great build quality but is able to travel only 11 Km on every 11 liter of water. To show off his water car to Natasha he took her to the formula racing track which is an (N1N−1) km long road with checkpoints numbered 11 to NN from left to right. The distance between two adjacent checkpoints is 11 Km.

Chef and Water Car solution codechef

Initially, Chef is at checkpoint number 11 and the tank of the water car is empty. At every checkpoint, there is a water station, but the cost of filling 11 liter of water at a checkpoint is equal to the checkpoint number. Chef can not store more than VV liters of water in the tank of a car. Chef is interested in both minimum as well as the maximum cost of filling that can happen to reach the checkpoint number NN.

Input Format

Chef and Water Car solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers N,VN,V.

Output Format

For each test case, output two integers separated by space representing the maximum and minimum cost of filling respectively.

Constraints

Chef and Water Car solution codechef

  • 1T1031≤T≤103
  • 1N,V1091≤N,V≤109

Subtasks

Chef and Water Car solution codechef

Subtask 1 (20 points): V=1V=1

Subtask 2 (80 points): Original constraints

Sample Input 1

Chef and Water Car solution codechef

3
3 1
4 2
4 3

Sample Output 1 

3 3
6 4
6 3

Explanation

Chef and Water Car solution codechef

Test case 11: Given N=3N=3 and V=1V=1, Chef will start at checkpoint 11, fill 11 liter of water at a cost of 11 and move 11 Km right to reach checkpoint 22. At checkpoint 22, Chef will fill 11 liter of water again at a cost of 22 and move 11 Km right to reach the destination i.e checkpoint 33. Hence total cost incurred is 33. There is no other way to reach the destination with a different expense.

Leave a Comment