# uva 151 Power Crisis

此題其實就是Josephus Problem
唯一需要注意的就是它永遠都從1號電廠開始關電
所以輸入N個電廠其實只需要做N-1個電廠的Josephus Problem，並且將全部電廠的編號都減一，所以要找最後一個關的電廠是12號的那個
code如下，採用dp的作法，每給定一個N和m的時間複雜度都是$O(n)$

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

#define SIZE 101

int Joseph_Problem_DP(const int n,int& m){
    int Pos[n+1];
    Pos[1]=1;
    for(int i=2;i<=n;i++)
        Pos[i]=(Pos[i-1]+(m-1))%i + 1;

    return Pos[n];
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bool Turn_off[SIZE],Done;

    int N,m;
    bool find;
    while(cin>>N && N!=0){
        if(N==13)
            m=1;
        else{
            m=2;
            while(Joseph_Problem_DP(N-1,m)!=12)m++;
        }

        cout<<m<<endl;
    }
    return 0;
}