CLSLDR - Class Leader
This is new year in Planet X and there is something special! A classroom in this planet is looking for a new class leader using an unique game!
These are the ways how the game is played.
- There are n students in the class. Each student is labeled from 1 (first student) to n (last student).
- A paper is given to m-th student.
- The next o-th student who gets the paper quits the game.
- The paper is passed until there is one last student who hasn't quitted the game.
- The student becomes the class leader.
Now, your task is to find the number of such student.
Input
The first line contains a number T (0 <= T <= 106).
Each of the next T lines contains 3 integers which are n (0 < n <= 103), m, o (0 < m, o <= n) and are separated by a single space.
Output
For each test cases, print the required answer.
Example
Input: 2 4 1 2 5 2 3 Output: 2 1
Explanation for Test Case 1
- 1 2 3 4 → The paper is being held by student 1. Pass the paper by 2 students. Now, the paper is being held by student 3.
- 1 2 4 → Student 3 quits. Pass the paper by 2 students. Now, the paper is being held by student 1.
- 2 4 → Student 1 quits. Pass the paper by 2 students. Now, the paper is being held by student 4.
- 2 → Student 4 quits. Student 2 becomes the class leader.
hide comments
farook_heroes:
2021-08-10 12:46:58
How the second test case in output is 1 pls say if anyone knows |
|
lighted:
2020-09-14 23:22:15
I like constraints for this problem! O(n) dp solution for each case gives TLE. Should do extra dp memoization or tabulation+precalculation. Since max value of n & k is 1000 we have O(1000*1000) dp solution in worst. No matter that value of T can be 10^6. Accepted in 0.32s with fast IO of cin/cout.
|
|
delta01:
2019-10-06 16:09:01
time limit exceeded problem .. dont know where to reduce complexity Last edit: 2019-10-06 18:25:02 |
|
amit013:
2019-02-26 23:09:38
Please remove this problem if you don't want us to be able to solve it. I have never seen so stupid time limit.
|
|
anonymous:
2017-02-22 09:45:36
It looks like the input test cases do not satisfy given constraints (probably last one):
|
|
vivek_singhvi:
2017-02-21 08:55:57
TLE with O(n) approach any suggestion
|
|
marcelljason06:
2017-02-16 15:11:54
are you sure with all of your testcases? please check again.
|
Added by: | Lucas |
Date: | 2017-02-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |