[UVA] 402 - M*A*S*H

/* 題目: UVa 402 - M*A*S*H

 * Language: C++

 * Created on: 2015年12月1日

 *   Author: hanting

 */

#include <iostream>

#include <vector>

using namespace std;

void killSomeone(vector<int> &vec, int &n, int &num)

{

     int t = n - 1;

     while (vec.size() > num and t < vec.size())

     {

           vec.erase(vec.begin() + t);

           t += n - 1;

     }

}

int main()

{

     int N; // N people

     int testCase = 1;

     while (cin >> N)

     {

           int luckyMan = 0;

           cin >> luckyMan;

           vector<int> point(20);

           vector<int> man(N);

           for (int i = 0; i < N; i++)

                man[i] = i + 1;

           for (int i = 0; i < 20; i++)

           {

                cin >> point[i];

           }

           for (int i = 0; i < 20 and man.size() > luckyMan; i++)

           {

                killSomeone(man, point[i], luckyMan);

           }

           cout << "Selection #" << testCase++ << endl;

           for (int i = 0; i < man.size(); i++)

           {

                cout << man[i];

                if (i == man.size() - 1)

                     cout << endl;

                else

                     cout << " ";

           }

           cout << endl;

     }

     return 0;

}

[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;

}