大学の課題として以下の問題が出ました。
ゲーム人数をNとし、それぞれに1からNまでの番号があるとする。K番から順にM番目の人はゲームから抜け、その度にその次の番号から数えてM番目の人が抜けるのを繰り返す。最後に残った人の番号を計算するプログラムを作れ。入力の一行目はNとゲーム回数、続けて各行に各ゲームのKとMを入力する。出力は最後に残った人の番号をそれぞれ一行ずつ出力すること。
このプログラムをvectorを使って作ってみましたが、入力する数字によっては「double free or corruption (out)」と表示されてしまいます。swapなどを使ってもエラーは直らず、どこが間違っているのかご指摘いただきたいです。
#include<iostream>
#include<vector>
using namespace std;
inline void Check(int kazu, int k, int m, vector<int> a){
int i;
for(int j = 1; j < kazu; j++){
i = k + m;//消す位置
if(i > a.size())i %= a.size();
a.erase(a.begin() + i - 1);
k = i;//次に始める場所
}
cout << a[0] << endl;
}
int main()
{
int kazu, n;// ゲーム人数, ゲーム回数
cin >> kazu >> n;
vector<vector<int>> lol(n, vector<int>(2));
for(int j = 0; j < n; j++){
cin >> lol[j][0] >> lol[j][1];// = k, m
lol[j][1] -= 1;} //mを間隔にする
vector<int> a;
for(int j = 1; j <= kazu; j++){
a.push_back(j);
}
int k, m;
for(int j = 0; j < n; j++){
k = lol[j][0], m = lol[j][1];
Check(kazu, k, m, a);
}
return 0;
}
上手くいく入力例
5 2
1 3
2 2
出力例
4
4
上手くいかない入力例
6 1
1 3
また、以下は助教からヒントとしてもらった解答例に少し変更を加えたものです。この中のvis[]
とwhile{}
の中で何故そのように書くのか、どういう仕組みなのかが理解できません。これも教えていただきたいです。よろしくお願いします。
解答例
#include<stdio.h>
int main(){
int kazu, n, k, m;
scanf("%d %d", &kazu, &n);
while(n != 0){
scanf("%d %d", &k, &m);
int vis[100] = { 0 };
int count = 0;
int rev = kazu;
while (rev != 1) {
count++;
if (count == m) {
vis[k] = 1;
rev--;
count = 0;
}
do {
k = k % kazu + 1;
} while (vis[k] == 1);
}
printf("%d\n", k);
n -= 1;
}
return 0;
}