Algorithm/DS Problem#4:Minimum time needed to make copies
This morning the jury decided to add one more , very easy problem to the problem set of the Olympiad. The executive secretary of the organizing committee has printed its statement in one copy and now they need to make n more copied before the start of the Olympiad. They have two copiers at his disposal, one of which copies a sheet in x seconds and other in y seconds.(It is allowed to use one copier or both at the same time. You can copy not only from the original , but also from the copy.) Help them find out what is the minimum time they need to make n copies of the statement.
Input:
The program receives 3 integers n, x, y (1 <= n <= 2.10⁸, 1 <=x,y <= 10)
Output:
Print one integer, the minimum time in seconds required to get n copies.
Examples:
input : 4 1 1
output: 3
input: 5 1 2
output : 4
Clarification
You start with “ONE” copy (that’s the original correct) and 2 copiers. Now you can feed that to one copier only as first and once you get the FIRST EVER copy, you have now 2 copies which you can feed to both copiers and get the rest of the copies needed.
Minimum time it can take to achieve the entire task : 0
Maximum time it can take to achieve the entire task: max(x,y) * n
So the answer will be between above two both ranges and they are in sorted order.. which hints us to use Binary Search.
Idea
While doing binary search, if mid is good enough time to make n copies, go towards to LEFT and see whether we can minimize the time even further.
if mid not enough to make the copies, go RIGHT .
Complexity: T: O(logN) S: O(1)
