Week7_1.cpp

/*
ผู้จัดเกมปริศนานามแฝงว่า "Skul1" ได้จับนักโทษมาเล่นเกมโดยบอกว่าผู้ชนะจะมีเพียงหนึ่งคน โดยผู้ชนะจะเป็นอิสระและได้รับเงินมหาศาล
โดยกฏของเกมมีอยู่ว่า จะให้จำนวนนักโทษนั้งเป็นวงกลม จำนวน N คน คนที่เริ่มตำแหน่งที่ 1 จะทำการสังหารคนถัดไปคือ ตำแหน่งคนที่ 2 
แล้วคนที่มีชีวิตรอดต่อจากคนถัดไป(ตำแหน่งคนที่ 3) สังหารคนถัดไป(ตำแหน่งคนที่ 4) วนไปเรื่อยๆจนเหลือคนสุดท้าย คนสุดท้ายที่รอดจะเป็นผู้ชนะของเกมนั้น
แต่ "Skul1" นึกแผนชั่วขึ้นมา โดยส่ง spy ไปนั้งตำแหน่งของผู้ชนะ เพื่อที่จะประหารนั้งโทษให้หมด เป็นกลอุบาย
"ฉันจะให้ล้านนึง เจ้าเขียนโปรแกรมหาตำแหน่งของผู้ชนะของเกมนี้ ในฐานะมือขวาของข้าขอให้เป็นความลับระหว่างพวกเรา" Skul1 กล่าวไว้
ข้อมูลเข้า
    N คือ จำนวนเก้าอี้ โดย 2<=N<=10000(ถ้าผู้ใช้พิมพ์ N > 10000 หรือ N < 2 ให้พิมพ์ว่า ERROR)
ข้อมูลออก
    x คือ ตำแหน่งที่เป็นผู้ชนะ
ยกตัวอย่าง
    N = 12
    โดยลำดับของตำแหน่งที่ถูกสังการคือ
    1->2 3->4 5->6 7->8 9->10 11->12
    1->3 5->7 9->11
    1->5 9->1
    9 เป็นจำแหน่งสุดท้ายที่อยู่รอดเลยเป็นผู้ชนะ
*/
//Recursive O(n)
#include<iostream>
#include<vector>
using namespace std;
void findSafeSpot(vector<int> person,int index)
{
    if(person.size() == 1)
    {
        cout << person[0] << endl;
        return;
    }
    index = ((index+1) % person.size());
    person.erase(person.begin()+index);
    findSafeSpot(person,index);
}
main()
{
    int seat;
    cin >> seat;
    if(seat < 2 || seat > 10000)
    {
        cout << "ERROR" << endl;
    }
    else
    {
        int index = 0;

        vector<int> person;
        for (int i = 1; i <= seat; i++) 
        {
            person.push_back(i);
        }

        findSafeSpot(person,index);
    }
}