[UVA] 305 - Joseph

題目連結

題意:

給你一個K，表示有K個好人和K個壞人，
好人排在壞人前面，
例如k=3，
排成=>好好好壞壞壞
現在有一數字n，表示從第一個開始數第n個要被殺掉，
殺完繼續數，超過第2*k個就再重頭開始數。
如果n=4，
好好好壞壞壞(第四個被殺掉)
好好好壞壞壞
....過程中殺到好人了
但如果n=5，
好好好壞壞壞
好好好壞壞壞
好好好壞壞壞
把壞人都殺光了而且都沒殺到好人！


今天要求n最小為多少，可以將壞人殺光而不殺到好人。

我的作法:

直接模擬，
但是要先將k=1~13的答案先存起來，不然會TLE

--------------------------------------------------

/* 題目: UVa 305 - Joseph

 * Language: C++

 * Created on: 2015年11月28日

 *   Author: hanting

 */

#include <iostream>

#include <vector>

using namespace std;

vector<bool> arr;

bool test(int &n, int &k)

{

     int cur = (n - 1) % (k * 2);

     while (arr.size() > k)

     {

           if (cur < k)

                return false;

           arr.erase(arr.begin() + cur);

           cur += n - 1;

           cur %= arr.size();

     }

     return true;

}

int main()

{

     int k;

     int ans[14] = { };

     for (k = 1; k < 14; k++)

     {

           int testk;

           for (testk = k;; testk++)

           {

                arr.assign(k * 2, 0);

                if (test(testk, k))

                     break;

           }

           ans[k] = testk;

     }

     while (cin >> k and k)

           cout << ans[k] << endl;

     return 0;

}