Alternative moves
Practice
3.8 (9 votes)
Basics of greedy algorithms
Math
Greedy algorithms
Algorithms
Problem
15% Success 3251 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code
You are given three integers N, A, and B. You have another integer X = 0. You can apply the following move (1-indexed) any number of times:
- During the odd-numbered moves(1, 3, 5,....), you have to set X = X + A.
- During the even-numbered moves(2, 4, 6,....), you have to set X = X - B.
Find the minimum number of moves required so that the value of X becomes greater than or equal to N or print -1 if it is impossible to do so.
Input format
- The first line contains T denoting the number of test cases. The description of T test cases is as follows:
- Each test case consists of a single line containing three integers N, A, and B.
Output format
For each test case, print the minimum number of moves required so that the value of X becomes greater than or equal to N or print -1 otherwise.
Constraints
\(1 \leq T \leq 10^5\)
\(1 \leq N,A, B \leq 10^9\)
Explanation
The first test case
- During the first move you set X = 0 + 5 = 5 >= N = 5. Hence only one move is required.
The second test case
- It is impossible to make X >= N by applying the given move any number of times.
The third test case
- During the first move you set X = 0 + 4 = 4.
- During the second move you set X = 4 - 1 = 3.
- During the third move you set X = 3 + 4 = 7 >= N = 6. Hence minimum three moves are required.
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
12 votes
Tags:
ApprovedBasic ProgrammingBrute-force searchEasyGreedy AlgorithmsOpenSorting
Points:20
5 votes
Tags:
Greedy AlgorithmsAlgorithmsBasics of Greedy Algorithms
Points:20
74 votes
Tags:
AlgorithmsBasics of Greedy AlgorithmsGreedy Algorithms
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output