SRM487 Div1 Medium(550) BunnyExam

BunnyExam

-1となるのは、k=1で長さが2以上の場合、k=2でリンクの両端の偶奇が異なる場合、リンクの両端が接している場合。あとは接している答えが異なるようなリンクの割り当てが出来ない場合。ただしリンクの両眼が接しているリンクの端は高々４つなので、k≧5ではこのようなことは起こらない。

条件を満たす答えの列が存在するならば、各答えについて正解する確率は1/k。

#include <vector>

using namespace std;

class BunnyExam{public:
double getExpected( int m, int k, vector <int> linkage )
{
    int N = (int)linkage.size() / 2;

    if ( k == 1  &&  m >= 2 )
        return -1;

    for ( int i=0; i<N; i++ )
        if ( k == 2  &&  linkage[i*2]%2 != linkage[i*2+1]%2  ||
             abs(linkage[i*2]-linkage[i*2+1]) == 1 )
            return -1;
    
    if ( k <= 4 )
    {
        bool ok = false;

        int lim = 1;
        for ( int i=0; i<N-1; i++ )
            lim *= k;
        for ( int c=0; c<lim; c++ )
        {
            vector<int> ans(N);
            int t = c;
            for ( int i=0; i<N; t/=k, i++ )
                ans[i] = t%k;

            bool f = true;
            for ( int i=0; i<2*N; i++ )
            for ( int j=i+1; j<2*N; j++ )
                if ( abs(linkage[i]-linkage[j]) == 1  &&
                     ans[i/2] == ans[j/2] )
                        f = false;
            if ( f )
                ok = true;
        }

        if ( ! ok )
            return -1;
    }

    return 1.0 / k * m;
}};