Cod sursa(job #595024)

Utilizator SpiderManSimoiu Robert SpiderMan Data 10 iunie 2011 20:01:11
Problema Expresii 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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 <string, ll> M[MAX];
ll solution, P, k;

inline int check (string S, int N, char ch) {
    return ((int) S.size () < N || ((int) S.size () == N && S[N - 1] == ch));
}

ll doit (int N, string S) {
    ll sol = 0;
    if (N == 1) return S.size () ? (S[0] >= 'A' && S[0] <= 'Z' ? 1 : 0) : K;
    if (M[N].find (S) != M[N].end ()) return M[N][S];
    if ((int) S.size () < N || ((int) S.size () == N && S[N - 1] == '!'))
        sol = doit (N - 1, S.substr  (0, N - 1));
    for (int i = 1, j = check (S, N, '+') + check (S, N, '*'); i < N - 1; ++i) {
        sol += j * doit (i, S.substr  (0, i)) * doit (N - i - 1, (int) S.size () < i ? "" : S.substr  (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) ;
}