Cod sursa(job #595042)

Utilizator SpiderManSimoiu Robert SpiderMan Data 10 iunie 2011 22:32:35
Problema Expresii 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
# include <cstdio>
# include <cstring>
# include <map>
# include <string>
using namespace std ;

typedef long long ll;
const char *FIN = "expresii2.in", *FOU = "expresii2.out" ;
const int MAX = 31;

int N, K;
char A[MAX], B[MAX] ;
map <const char*, ll> M[MAX];
ll solution, P, k;

inline int check (const char *S, int N, char ch) {
    return (strlen (S) < N || (strlen (S) == N && S[N - 1] == ch));
}

inline char* sub (const char *S, int st, int size) {
    char *X = new char [MAX] ;
    strncpy (X, S + st, size);
    X[size] = '\0' ;
    return X;
    delete X ;
}

ll doit (int N, const char *S) {
    ll sol = 0;
    if (N == 1) return strlen (S) ? (S[0] >= 'A' && S[0] <= 'Z' ? 1 : 0) : K;
    if (M[N].count (S) > 0) return M[N][S];
    if (strlen (S) < N || (strlen (S) == N && S[N - 1] == '!'))
        sol = doit (N - 1, sub (S, 0, N - 1));
    for (int i = 1, j = check (S, N, '+') + check (S, N, '*'); i < N - 1; ++i) {
        sol += j * doit (i, sub (S, 0, i)) * doit (N - i - 1, strlen (S) < i ? "" : sub (S, i, N - i - 1));
    }
    M[N][S] = sol;
    return sol;
}

int main (void) {
    fscanf (fopen (FIN, "r"), "%d %d %lld", &N, &K, &P) ;
    freopen (FOU, "w", stdout) ;
    printf ("%lld\n", doit (N, ""));
    for (int i = 0; i < K; ++i)
        A[i] = 'A' + i;
    A[K] = '+', A[K + 1] = '*', A[K + 2] = '!';
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < K + 3; ++j) {
            B[i] = A[j], k = doit (N, B) ;
            if (P <= (solution += k)) {
                solution -= k;
                break ;
            }
        }
    }
    printf ("%s", B) ;
}