Google Code Jam 2016

R1B-a.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <algorithm>

using namespace std;

typedef long long i64;

#define edge(i, u) for (int i = head[u]; i != -1; i = graph[i].next)
#define range(i, a, b, step) for (int i = ((int) (a)); i != ((int) (b)) && ((i - ((int) (b))) ^ ((int) (step))) < 0 ; i += ((int) (step)))

string a;
int tcase, cnt[26], num[10];

int get(char chr) {
    return cnt[chr - 'A'];
}

int main(int argc, char const *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("A-large-practice.in", "r", stdin);
    freopen("A-large-practice.out", "w", stdout);
#endif
    cin >> tcase; range(times, 1, tcase + 1, 1) {
        memset(cnt, 0, sizeof cnt);

        cin >> a;
        range(i, 0, a.length(), 1) cnt[a[i] - 'A']++;

        num[0] = get('Z');
        num[2] = get('W');
        num[4] = get('U');
        num[6] = get('X');
        num[8] = get('G');
        num[7] = get('S') - num[6];
        num[5] = get('F') - num[4];
        num[3] = get('H') - num[8];
        num[9] = get('I') - num[5] - num[6] - num[8];
        num[1] = get('N') - num[7] - num[9] - num[9];

        cout << "Case #" << times << ": ";
        range(i, 0, 10, 1) range(_, 0, num[i], 1) {
            cout << i;
        }
        cout << endl;
    }

    return 0;
}

R1B-b.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <deque>

using namespace std;

typedef long long ll;

const ll inf = 0x7fffffffffffffffl;

#define edge(i, u) for (ll i = head[u]; i != -1; i = graph[i].next)
#define range(i, a, b, step) for (ll i = ((ll) (a)); i != ((ll) (b)) && ((i - ((ll) (b))) ^ ((ll) (step))) < 0 ; i += ((ll) (step)))

string a, b;
int tcase, len;

tuple<ll, ll, ll> dfs(int now, ll x, ll y) {
    if (now >= len)  return make_tuple(abs(x - y), x, y);
    else {
        auto offsets = deque<tuple<int, int>> () ;
        if (x > y) {
            ll xx = a[now] == '?' ? 0 : a[now] - '0';
            ll yy = b[now] == '?' ? 9 : b[now] - '0';
            offsets.push_back(make_tuple(xx, yy));
        } else if (x < y) {
            ll xx = a[now] == '?' ? 9 : a[now] - '0';
            ll yy = b[now] == '?' ? 0 : b[now] - '0';
            offsets.push_back(make_tuple(xx, yy));
        } else {
            if (a[now] == '?' && b[now] == '?') {
                offsets.push_back(make_tuple(0, 0));
                offsets.push_back(make_tuple(0, 1));
                offsets.push_back(make_tuple(1, 0));
            } else if (a[now] == '?') {
                ll yy = b[now] - '0';
                offsets.push_back(make_tuple(yy - 1, yy));
                offsets.push_back(make_tuple(yy + 0, yy));
                offsets.push_back(make_tuple(yy + 1, yy));
            } else if (b[now] == '?') {
                ll xx = a[now] - '0';
                offsets.push_back(make_tuple(xx, xx - 1));
                offsets.push_back(make_tuple(xx, xx + 0));
                offsets.push_back(make_tuple(xx, xx + 1));
            } else {
                offsets.push_back(make_tuple(a[now] - '0', b[now] - '0'));
            }
        }

        auto ans = make_tuple(inf, inf, inf);
        for (auto item : offsets) {
            ll xx, yy;
            tie(xx, yy) = item;
            if (0 <= xx && xx < 10 && 0 <= yy && yy < 10) {
                ans = min(ans, dfs(now + 1, x * 10 + xx, y * 10 + yy));
            }
        }

        return ans;
    }
}

int length(ll val) {
    if (val) return length(val / 10) + 1;
    else return 0;
}

int main(int argc, char const *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("B-small-practice (1).in", "r", stdin);
    freopen("B-small-practice (1).out", "w", stdout);
#endif

    cin >> tcase; range(times, 1, tcase + 1, 1) {
        cin >> a >> b;
        len = a.length();
        ll ab, xx, yy;
        tie(ab, xx, yy) = dfs(0, 0, 0);
        cout << "Case #" << times << ": ";
        range(i, 0, len - max(1, length(xx)), 1) cout << 0; cout << xx; cout << " ";
        range(i, 0, len - max(1, length(yy)), 1) cout << 0; cout << yy; cout << "\n";
    }

    return 0;
}