PKU 1012

Joseph
とりあえず書いてみたプログラムだとTLEになるけどkの幅が小さいので、↓のプログラムで全ての場合を計算し、

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    for ( int k=1; k<14; k++ )
    //int k;
    //while ( cin >> k  &&  k > 0 )
    {
        int m;
        for ( m=1; ; m++ )
        {
            vector<bool> guy( 2*k );
            int p = -1;

            int i;
            for ( i=0; i<k; i++ )
            {
                int t = (m-1) % (2*k-i) + 1;
                for ( int j=0; j<t; j++ )
                {
                    do
                        p = ( p + 1 ) % (2*k);
                    while ( guy[p] );
                }

                guy[p] = true;

                if ( p < k )
                    break;
            }

            if ( i >= k )
                break;
        }

        cout << m << endl;
    }

    return 0;
}

↓のプログラムでOK。

#include <iostream>

using namespace std;

int main()
{
    int ans[] = { 0, 2, 7, 5, 30, 169, 441, 1872, 7632,
                  1740, 93313, 459901, 1358657, 2504881 };
    int k;
    
    while ( cin >> k  &&  k > 0 )
        cout << ans[k] << endl;

    return 0;
}

真っ当な解法はどんなのだろうか。

• 実は真面目にシミュレートする必要がない
• k-1人目を殺したあとk人目に移るときを考えると　m = 0 or 1 (mod k+1)

で高速化できたがまだ間に合わない。
答えをキャッシュしておくのが想定解法なのだろうか？

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

bool check( int m, int k );

int main()
{
    int ans[14] = { 0 };

    int k;
    while ( cin >> k  &&  k > 0 )
    {
        for ( int m=0; ans[k]==0; m+=k+1 )
        {
            if ( check( m, k ) )
                ans[k] = m;
            if ( check( m+1, k ) )
                ans[k] = m + 1;
        }

        cout << ans[k] << endl;
    }

    return 0;
}

bool check( int m, int k )
{
    int p = 0;

    for ( int i=0; i<k; i++ )
    {
        p += m - 1;
        p %= 2 * k - i;

        if ( p < k )
            return false;
    }

    return true;
}