SRM464 Div1 Easy(250), Div2 Medium(500) ColorfulStrings

ColorfulStrings

全探索。n≦50とあるが各桁の数字は全て異なるのでcolorfulな文字列の個数はそれほど多くない。

#include <string>
#include <set>

using namespace std;

class ColorfulStrings
{
    string BT( int n, int k, string s, int *c );
    bool check( string s );

public:
    string getKth( int n, int k );
};

string ColorfulStrings::getKth( int n, int k )
{
    int c = 0;
    return BT( n, k, "", &c );
}

string ColorfulStrings::BT( int n, int k, string s, int *c )
{
    if ( ! check(s) )
        return "";

    if ( (int)s.length() == n )
        return ++*c==k ? s : "";

    string r;

    for ( char i='0'; i<='9'; i++ )
        r = max( r, BT(n,k,s+i,c) );

    return r;
}

bool ColorfulStrings::check( string s )
{
    int l = (int)s.length();

    set<int> p;

    for ( int i=1; i<=l; i++ )
    for ( int j=0; j+i<=l; j++ )
    {
        int t = 1;
        for ( int k=j; k<j+i; k++ )
            t *= s[k] - '0';

        if ( p.count( t ) > 0 )
            return false;
        p.insert( t );
    }

    return true;
}