CPE 一顆星
題目連結:https://zerojudge.tw/ShowProblem?problemid=c108
內容
一群人圍成一個圈圈(編號從1, 2, 3, …, n)，然後開始數，第 m 個人要被吃掉(第一次從編號1的人開始數)。
現在假設共有2k個人，其中排在編號 1 到 k 的是好人，排在編號 k+1 到 2k 的是壞人，你的任務就是要找出一個最小的 m，使得在所有 k 個壞人被吃掉之前，沒有一個好人會被吃掉。
每一列有一個整數 k (0 < k < 14)。
k = 0 結束。
範例輸入
3
4
0
範例輸出
5
30
想法
枚舉所有可能的 m 值，觀察後發現
m > k (否則第一輪就取到好人)。
(m-1) % 2*k >= k (一樣看第一輪)。
如果上述兩條件成立，就可以開始取人了，取到好人就直接跳掉，接著判斷下一個 m。
可在一開始使用一個陣列儲存所有 k 對應的 m ，詢問時就可直接印出。
參考資料:YUI HUANG 演算法學習筆記， inversion的小屋
程式碼
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
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
int m, kill, ans[14], total;
bool suc;
for(int i = 1; i < 14; ++i){
suc = false;
m = i;
total = i << 1;
while(!suc){
++m;
if(i == 1) suc = true;
if((m-1)%total >= i){
kill = (m-1) % total;
for(int c = 2; c <= i; ++c){
kill = (kill+m-1) % (total-c+1);
if(kill < i) break;
if(c == i) suc = true;
}
}
}
ans[i] = m;
}
int k;
while(cin >> k && k){
cout << ans[k] << "\n";
}
return 0;
}
|