RomanRouletteRoman Roulette

time limit:   1000ms      

memory limit:   65535kb

submissions:   36      

accepted:   19

description西元67年，在羅馬和猶太人的衝突中，史學家

josephus 和其他40個人被關在一個洞穴中。羅馬人知道 josephus

的下落後希望他能投效羅馬帝國。但是他的同伴們卻不允許他投降。是以josephus

建議他們彼此殺害，一個接一個，被殺的順序就由命運決定。傳統上他們決定命運的方式為：大家圍成一個圓圈，從某個人開始算起，每算到 3

個人那個人就被殺掉，如此不斷下去，直到隻剩一個人。後來 josephus 成為唯一的存活者並投降羅馬。我們有興趣的是：josephus

如何剛好是那個存活者？真的是運氣好，還是他事先在暗地裡用 41 顆石頭練習過，或者他有一個數學的方法可以知道要站在哪一個位置才能成為最後的存活者？

聽過這個故事後，你相當的憂心要是將來某一天你也面臨同樣的情況要怎麼辦。是以你決定用你的手上型電腦寫一個程式算出應該從那個人開始算起，你才可以成為那個最後唯一存活的人。

在這個問題中，你的程式必須能解決 josephus 描述的另一種變形。有 n 個人排成一個圓圈，面向內，依順時鐘方向編號從 1 到 n。你的位置在

1 。殺人程式由編號 i 的人開始算起（順時鐘方向），直到算到第 k 個人，那個人立刻被殺掉。然後從這個被殺的人左邊的那個人再順時鐘方向算 k

個人，那個人必須負責埋葬剛才被殺的那個人，然後回去站在剛才被殺的那個人的位置。接下來從這個人的左邊那個人算起，第 k

個人又被殺掉，如此一直下去直到隻剩下一個人為止。 例如：當 n=5, k=2, i=1, 那麼被殺的順序為 2, 5, 3,

1，存活者為4。

input輸入含有多組測試資料。

每組測試資料有2個整數 n, k 。你可以假設最多隻有 100 個人。 若 n = k = 0 時代表輸入結束。請參考sample

input。

output對每組測試資料輸出一開始時應該從哪一個人算起（也就是

i），才能確保你是最後唯一的存活者。請記住：你的位置在 1。以上述的例子來看，必須由第 3 個人算起，最後存活的人才能是 1

。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

<code>/*</code>

<code> </code><code>* uva_130_1.cpp</code>

<code> </code><code>*</code>

<code> </code><code>*  created on: 2013年10月31日</code>

<code> </code><code>*      author: administrator</code>

<code> </code><code>*/</code>

<code>   </code> 

<code>#include &lt;iostream&gt;</code>

<code>#include &lt;cstdio&gt;</code>

<code>#include &lt;vector&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>/**</code>

<code> </code><code>* 模拟的實作使用動态數組是非常友善的，過程也很簡單。數組初始存儲每一個人的編号，</code>

<code> </code><code>* 從第0個元素（1号）開始計數，每次殺死一個人前先不要将這個人的編号删除，而是先找出要來埋他的人，</code>

<code> </code><code>* 将他們的編号互換，然後将埋他的人原來所在的位置删掉即可。最後計算出的是從1号開始計數，最後能幸存的人編号p，</code>

<code> </code><code>* 那麼從你前面第p個人開始你就是安全的（你站在第1位），即n - p。這個換算的原理是顯而易見的。</code>

<code>int</code>

<code>main(){</code>

<code>    </code><code>int</code>

<code>n,k;</code>

<code>    </code><code>while</code><code>(</code><code>scanf</code><code>(</code><code>"%d%d"</code><code>,&amp;n,&amp;k)!=eof,n||k){</code>

<code>        </code><code>int</code>

<code>i;</code>

<code>        </code><code>vector&lt;</code><code>int</code><code>&gt; circle;</code>

<code>        </code><code>for</code><code>(i = 1 ; i &lt;= n ; ++i){</code>

<code>            </code><code>circle.push_back(i);</code>

<code>        </code><code>}</code>

<code>t;</code>

<code>m = (k - 1)%circle.size();</code><code>//計算第一個被殺死的人的位置</code>

<code>        </code><code>while</code><code>(circle.size() != 1){</code>

<code>            </code><code>t = (m - 1 + k)%(circle.size() - 1);</code><code>//計算替換者的位置</code>

<code>            </code><code>t = (t + (t &gt;= m))%circle.size();</code><code>//判斷替換着的位置與被殺者位置之間的關系,若被殺者的位置在替換着的前面,則需要+1</code>

<code>            </code><code>circle[m] = circle[t];</code><code>//将替換者一道被殺者的位置上</code>

<code>            </code><code>circle.erase(circle.begin() + t);</code><code>//删除替換者原來的位置</code>

<code>            </code><code>m = (m  - ( t &lt; m ) + k)%circle.size();</code><code>//計算下一個被殺者的位置,因為最後删掉的其實還是替換者的位置,是以如果替換者的位置在額被殺者的前面的話,那麼就要-1</code>

<code>        </code><code>printf</code><code>(</code><code>"%d\n"</code><code>,(n - circle.front() + 1)%n + 1 );</code>

<code>    </code><code>}</code>

<code>    </code><code>return</code>

<code>0;</code>

<code>}</code>