約瑟先生在傍晚時刻總是東奔西跑地,邀請親朋好友到家裡共進晚餐。 約瑟先生住的是豪宅,每到了晚餐時刻,豪宅內總是人山人海。 剛回到家的約瑟先生,急切的想要尋找他的太太,傭人也幫忙尋找,於是他們在庭院和人群中不斷的喊著: 「約瑟夫人咧?」
好啦,我承認上面的冷笑話不好笑= =。(逃~)
我們現在關心的是晚餐。噢,不是的,我們關心的是約瑟夫問題。
最後剩下的那M個人可以先開動,大家要在旁邊「看」到他們吃飽…
你的工作,就是幫約瑟先生計算出:N個人,每K個一數的時候,站在第一個報數的人順時針方向上的哪個位置,才可以先開動?
當然,由於你也在約瑟先生的邀請之列,你偶爾想要耍一下約瑟先生。
你修改了一下你的程式,使得幫約瑟先生算出的位置,剛好在晚餐前最後一輪被刷掉(嘿嘿,夠心機吧!)
例如上面的兩張圖,N=7,K=3,M=3,那麼被刷掉的人的位置依序是3,6,2,7,讓約瑟先生排在位置7讓他出糗吧。
事後只要跟他說:啊,程式算錯了~就好了!放心,約瑟夫人很好的。
由於太心機了,約瑟先生決定不再請你幫忙寫程式。(當然,你還是有晚餐吃XD)
不過約瑟夫人倒是對這個很有興趣,於是跟你伸程式碼。
請你幫約瑟夫人寫一個程式吧XD
輸入可能包含多筆測試資料。每一筆測試資料代表某個晚上的晚餐情形,佔一列,包含三個正整數N,K,M。
(1<=M<N<=1,000,000,000;1<=K<=10,000)
當N=K=M=0的時候代表輸入結束。
對於每筆測試資料,請輸出使約瑟先生當天晚上會餓肚子並且出糗的絕佳位置。
第一筆測試資料中,退場者依序為位置3,1,5。於是位置5成了絕佳位置。
原TIOJ1203 / TIOJ 2008例行賽02 (prob E)。Problem Setter:Tmt。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 50 |
2 | 1 | 50 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 3000 | 65536 | 262144 | |
1 | 3000 | 65536 | 262144 |