SRM493 Div1 Easy(300), Div2 Medium(600) StonesGame

TopCoder

StonesGame

普通のニムと違って１手前の状態に戻すことが可能なので、双方が最善を尽くして３手目以降に決着が付くことはない。

#include <string>
using namespace std;

bool check( int N, int M, int K, int L )
{
    return abs(L-M)%2 != K%2  &&
           2*max(M-K+1,1)+K-M-1 <= L &&  L <= 2*min(M,N-K+1)+K-M-1;
}

class StonesGame{public:
string winner( int N, int M, int K, int L )
{
    if ( check(N,M,K,L) )
        return "Romeo";

    for ( int i=max(M-K+1,1); i<=min(M,N-K+1); i++ )
        if ( ! check(N,2*i+K-M-1,K,L) )
            return "Draw";

    return "Strangelet";
}};