K. Let the Flames Begin time limit per test 6 seconds memory limit per test 1024 megabytes input standard input output standard output
Tonight n
young men are going to participate in Peter’s campfire party. They decide to play an ancient counting-out game which was first described by Titus Flavius Josephus. Here is a brief introduction to the game.
Before starting the game, these young men will stand in a circle around the campfire and the first man to join the circle will start the game. Counting will begin at the first man and proceed around the circle in the counterclockwise direction repeatedly. That is, the first man will report one at the beginning, and the second one in the counterclockwise direction will report two, and so forth, until a poor man reports k
and consequently leaves the circle to become a bystander. The game will be repeated with the remaining men, restarting from the next man in the counterclockwise direction who will be the new first man, going in the same direction, until all the young men have left the circle.
Peter wanna be the m
-th one who left the circle since he strongly believes this number is lucky for him. As a sophisticated programmer, can you point out the right place he should stand at before the game start so that he can achieve his goal?
For the sake of clarity, we assume the index of the first man to join the circle is 1 , the index of the next man in his counterclockwise direction is 2, and so on. By the definition, the index of the last man in that direction should be n
, and your task is to determine the index of the place Peter wants. Input
The input contains several test cases, and the first line contains a positive integer T indicating the number of test cases which is up to 1000
.
For each test case, the only line contains three integers n,m and k where 1≤n,m,k≤1018 and n≥m
.
We guarantee that the sum of min{m,k} (i. e. the minimum of m and k) in all test cases is no larger than 2×106
. Output
For each test case, output a line containing “Case #x: y” (without quotes), where x is the test case number starting from 1
, and y is the index of the right place. Example Input Copy
20 10 1 2 10 2 2 10 3 2 10 4 2 10 5 2 10 6 2 10 7 2 10 8 2 10 9 2 10 10 2 10 1 3 10 2 3 10 3 3 10 4 3 10 5 3 10 6 3 10 7 3 10 8 3 10 9 3 10 10 3Output Copy
Case #1: 2 Case #2: 4 Case #3: 6 Case #4: 8 Case #5: 10 Case #6: 3 Case #7: 7 Case #8: 1 Case #9: 9 Case #10: 5 Case #11: 3 Case #12: 6 Case #13: 9 Case #14: 2 Case #15: 7 Case #16: 1 Case #17: 8 Case #18: 5 Case #19: 10 Case #20: 4Note
The sample cases indeed show the order of the young men to leave the circle when (n,k) is set to (10,2) and (10,3) respectively.
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll cir(ll n,ll m,ll k) { ll p=k%(n-m+1); if(p==0) p=n-m+1; for(ll i=2;i<=m;i++) { p=(p+k-1)%(n-m+i)+1; } return p; } int main() { int T,cas=0; cin>>T; while(T--) { ll n,m,k; scanf("%I64d%I64d%I64d",&n,&m,&k); ll ans; if(k==1) { ans=m; } else if(m<=k) { ans=cir(n,m,k); } else { ll p=k%(n-m+1); if(p==0) p=n-m+1; ll i=1; while(i<m) { ll d=(i+n-m-p)/(k+1); if(d==0) d++; if(i+d>=m) { d=m-i; } i+=d; p=(p+k*d%(n-m+i)-1+(n-m+i))%(n-m+i)+1; } ans=p; } printf("Case #%d: %I64d\n",++cas,ans); } return 0; }