TMCTF Programming 500

400.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
using namespace std;

int size = 3;
string start, goal;

set<string> expand(const set<string> &ss)
{
    set<string> ret;

    for (auto cur: ss) {
        int pix = 0;
        for (int i = 0; i < cur.size(); i++) {
            if (cur[i] == goal[0]) {
                pix = i;
                break;
            }
        }

        int r1 = pix / size;
        int c1 = pix % size;

        int r2 = r1 ^ 1;
        for (int dc = -1; dc <= 1; dc++) {
            int c2 = c1 + dc;

            if (!(c2 >= 0 && c2 <size))
                continue;

            swap(cur[r1 * size + c1], cur[r2 * size + c2]);
            ret.insert(cur);
            swap(cur[r1 * size + c1], cur[r2 * size + c2]);
        }
    }

    return ret;
}

void init()
{
    for (int i = 0; i < size * 2; i++)
        start += (char)('A' + i);
    goal = start;
    swap(goal[0], goal[goal.size()-1]);

    cout << start << ", " << goal << endl;
}

bool has_common(const set<string> &a, const set<string> &b)
{
    auto p = a.begin();
    auto q = b.begin();

    while (p != a.end() && q != b.end()) {
        if (*p == *q) return true;
        if (*p < *q) p++;
        else q++;
    }
    return false;
}

int calc_dist(const string &s, const string &g)
{
    set<string> fron_a, fron_b;

    fron_a.insert(s);
    fron_b.insert(g);

    for (int i = 0; ; i++) {
        cout << "depth: " << i * 2 << "\r" << flush;

        if (has_common(fron_a, fron_b)) {
            cout << endl;
            return i * 2;
        }

        fron_a = expand(fron_a);

        cout << "depth: " << i * 2 + 1 << "\r" << flush;

        if (has_common(fron_a, fron_b)) {
            cout << endl;
            return i * 2 + 1;
        }

        fron_b = expand(fron_b);
    }

    abort();
}

int main(int argc, char *argv[])
{
    size = atoi(argv[1]);

    init();

    auto cur = start;
    string ans;

    for (;;) {
        cout << "*** " << cur << endl;

        int pix = 0;
        for (int i = 0; i < cur.size(); i++) {
            if (cur[i] == goal[0]) {
                pix = i;
                break;
            }
        }

        int best = 999;
        string best_n;
        int best_t = 0;

        int r1 = pix / size;
        int c1 = pix % size;

        int r2 = r1 ^ 1;
        for (int dc = -1; dc <= 1; dc++) {
            int c2 = c1 + dc;

            if (!(c2 >= 0 && c2 <size))
                continue;

            swap(cur[r1 * size + c1], cur[r2 * size + c2]);

            int dist = calc_dist(cur, goal);
            if (dist < best || (dist == best && r2 * size + c2 < best_t)) {
                best = dist;
                best_n = cur;
                best_t = r2 * size + c2;
            }

            swap(cur[r1 * size + c1], cur[r2 * size + c2]);
        }

        ans += (char)('A' + best_t);
        cur = best_n;

        if (best == 0)
            break;
    }

    cur = start;
    cout << cur << endl;
    for (auto &c: ans) {
        int pos1 = c - 'A';
        int pos2 = 0;
        for (int i = 0; i < cur.size(); i++) {
            if (cur[i] == goal[0]) {
                pos2 = i;
                break;
            }
        }

        swap(cur[pos1], cur[pos2]);
        cout << cur << endl;
    }

    cout << ans << endl;

    return 0;
}

bj.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
using namespace std;

inline int hand(int p, int s)
{
    if (p + s <= 21) return p + s;
    return p;
}

double calc(int p, int d, int s, int total, vector<int> &yama)
{
    if (d > 21) return 1;
    int ds = hand(d, s);

    if (ds >= 17) return ds < p ? 1 : 0;

    double ret = 0;

    for (int i = 1; i <= 13; i++) {
        if (yama[i-1] == 0) continue;

        int nd = d, ns = s;
        if (i == 1) {
            nd += 1;
            ns = 10;
        }
        else {
            nd += min(i, 10);
        }

        double prod = (double)yama[i-1] / total;
        yama[i-1]--;
        ret += prod * calc(p, nd, ns, total - 1, yama);
        yama[i-1]++;
    }

    return ret;
}

double solve(int p, int s, int total, vector<int> &yama)
{
    if (p > 21) return 0;

    double ret = calc(hand(p, s), 3, 0, total, yama);

    double hit = 0;

    for (int i = 1; i <= 13; i++) {
        if (yama[i-1] == 0) continue;

        int np = p, ns = s;
        if (i == 1) {
            np += 1;
            ns = 10;
        }
        else {
            np += min(i, 10);
        }

        double prod = (double)yama[i-1] / total;
        yama[i-1]--;
        hit += prod * solve(np, ns, total - 1, yama);
        yama[i-1]++;
    }

    return max(ret, hit);
}

int main(int argc, char *argv[])
{
    vector<int> yama(13, 8);
    yama[0]--;
    yama[1]--;
    yama[2]--;

    int total = 13 * 8 - 3;

    cout << fixed << setprecision(4);
    cout << "TMCTF{HIT:" << solve(3, 10, total, yama) << ":STAND:" << calc(13, 3, 0, total, yama) << "}" << endl;

    return 0;
}