CCF 201712-2 遊戲

問題描述 　　有 n個小朋友圍成一圈玩遊戲，小朋友從1至 n編号，2号小朋友坐在1号小朋友的順時針方向，3号小朋友坐在2号小朋友的順時針方向，……，1号小朋友坐在 n号小朋友的順時針方向。

　　遊戲開始，從1号小朋友開始順時針報數，接下來每個小朋友的報數是上一個小朋友報的數加1。若一個小朋友報的數為 k的倍數或其末位數（即數的個位）為 k，則該小朋友被淘汰出局，不再參加以後的報數。當遊戲中隻剩下一個小朋友時，該小朋友獲勝。

　　例如，當n=5, k=2時：

　　1号小朋友報數1；

　　2号小朋友報數2淘汰；

　　3号小朋友報數3；

　　4号小朋友報數4淘汰；

　　5号小朋友報數5；

　　1号小朋友報數6淘汰；

　　3号小朋友報數7；

　　5号小朋友報數8淘汰；

　　3号小朋友獲勝。

　　給定 n和 k，請問最後獲勝的小朋友編号為多少？ 輸入格式 　　輸入一行，包括兩個整數 n和 k，意義如題目所述。 輸出格式 　　輸出一行，包含一個整數，表示獲勝的小朋友編号。 樣例輸入 5 2 樣例輸出 3 樣例輸入 7 3 樣例輸出 4 資料規模和約定 　　對于所有評測用例，1 ≤  n ≤ 1000，1 ≤  k ≤ 9。

題解：

用單向循環連結清單來做。

#include<iostream>

#include<cstring> 

using namespace std;

struct node {

node *next;

int data;

};

int main(){

int n, k;

cin>>n>>k;

int count = n;

node *First = new node;

node *rear;

First->data = count;

First->next = NULL;

rear = First;

while(count--){

if (count == 0)

break;

node *p;

p = new node;

p -> data = count;

p -> next = First;

First = p;

}

rear -> next = First;

int numberOff = 0;

node *p = rear;

while (n!=1){

numberOff++;

if (numberOff%k==0 || numberOff%10==k){

node *t = p->next;

p -> next  = p -> next -> next;

delete(t);

t = NULL; 

n--;

}

else {

p = p -> next;

}

}

cout<<p->data;

return 0;

}