2010年8月9日 星期一

440 - Eeny Meeny Moo

當太多人連上網際網路的時候會使網路變得非常、非常、非常慢,相信你一定有此經驗。

為了徹底解決這個問題,德國Ulm大學發展了一套稱為"隨機策略(contingency scheme)"的方法,當網路流量到達尖峰的時候,用一種有系統而又公平的方法切斷國內各大城市的連線。德國的各大城市隨機地由1到n來排列,Freiburg排在第一位,Ulm城排在第二位,Karlsruhe第三位,以此類推。

然後隨機選擇一數m,首先切斷其網路連線的是第一個城市(似乎是很公平的選擇),之後每隔m個城市切斷其網路連線,超過n則循環回到1繼續算下去,並忽略已經斷線的城市。例如,當n=17, m=5,各城市斷線的順序為:[1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7]。另外,我們希望Ulm是最後被斷網的城市(畢竟這是最多優秀程式設計師出生的地方),所以問題是給定n之後,如何選擇m的值才能使第二個城市最後被選到。

給定城市的總數為n,你的工作是要寫一個程式計算最小的m值,使Ulm在其他所有城市都斷線之前可以自在地瀏覽網路。

Input Specification

輸入會有許多列,每一列有一個整數n表示國內共有幾座城市, tex2html_wrap_inline43,,並以0表示資料結束。

Output Specification

如前面所言,對每一個n值找出滿足上述要求的最小m值。

Sample Input

3
4
5
6
7
8
9
10
11
12
0

Sample Output

2
5
2
4
3
11
2
3
8
16

原文出處

沒有留言:

張貼留言