約瑟先生在傍晚時刻總是東奔西跑地,邀請親朋好友到家裡共進晚餐。 約瑟先生住的是豪宅,每到了晚餐時刻,豪宅內總是人山人海。 剛回到家的約瑟先生,急切的想要尋找他的太太,傭人也幫忙尋找,於是他們在庭院和人群中不斷的喊著: 「約瑟夫人咧?」
好啦,我承認上面的冷笑話不好笑= =。(逃~)
我們現在關心的是晚餐。噢,不是的,我們關心的是約瑟夫問題。
約瑟先生和他的親朋好友在大樹底下圍成一圈,並且從某一位親友開始,順時針報數(從1號開始報),每數k個人,那位親友就必須退場,排到一旁,而順位的下一個人,就從1號開始報數,繼續循環,直到剩下M個人為止。
最後剩下的那M個人可以先開動,大家要在旁邊「看」到他們吃飽…
由於親友們實在是太多了,每次剩下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 |