snarknews [SNSS 2012, R3]. E. Fleet of Byteland

#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>

template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }

using namespace std;


map <char, string> m;

const int MAXN = 107;

unsigned long long f[MAXN];
unsigned long long k;
string s;

int main()
{
    freopen("fleet.in", "r", stdin);
    freopen("fleet.out", "w", stdout);
    m['A'] = ".-";
    m['E'] = ".";
    m['I'] = "..";
    m['M'] = "--";
    m['Q'] = "--.-";
    m['U'] = "..-";
    m['Y'] = "-.--";
    m['B'] = "-...";
    m['F'] = "..-.";
    m['J'] = ".---";
    m['N'] = "-.";
    m['R'] = ".-.";
    m['V'] = "...-";
    m['Z'] = "--..";
    m['C'] = "-.-.";
    m['G'] = "--.";
    m['K'] = "-.-";
    m['O'] = "---";
    m['S'] = "...";
    m['W'] = ".-- ";
    m['D'] = "-..";
    m['H'] = "....";
    m['L'] = ".-..";
    m['P'] = ".--.";
    m['T'] = "-";
    m['X'] = "-..-";
    cin >> s;
    cin >> k;
    int n = s.size();
    f[n] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        for (map <char, string> :: iterator iter = m.begin(); iter != m.end(); ++iter)
        {
            string p = iter->second;
            if (n - i >= (int)p.size() && p == s.substr(i, p.size()))
            {
                f[i] += f[i + p.size()];
                if (f[i] > k)
                    f[i] = k;
            }
        }
    }

    string ans = "";

    if (k > f[0])
    {
        cout << "0" << endl;
        return 0;
    }

    for (int i = 0; i < n; )
    {
        for (map <char, string> :: iterator iter = m.begin(); iter != m.end(); ++iter)
        {
            char c = iter->first;
            string p = iter->second;

            if (n - i >= (int)p.size() && p == s.substr(i, p.size()))
            {
                if (k <= f[i + p.size()])
                {
                    ans += c;
                    i += p.size();
                    break;
                }
                k -= f[i + p.size()];
            }
        }
    }
    cout << ans << endl;
    return 0;
}