Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2010-01-30

TeXLeX

| 22:45

問題文, SRM 178

'^' のみが特別な入力である入力文字列のASCII値を返せ、という問題。この '^' をどのように処理するかが問題の肝。

この問題を解くには適宜文字列を変換ルールにしたがって1文字目から変換していく必要がある。基本的には変換ルールのとおりに機能を実装すればいい。注意する点としてはルール1を適用すると、値がchar型ではオーバーフローする場合があるので、それ対応する必要がある(僕は気づけなかったために、システムテストで落とされた。

238.78/600 (1 failed)

class TeXLeX {
public:
    vector <int> getTokens(string input) {
        vector <int> result;
        const int len = input.length();
        for (int i = 0; i < len; i++) {
            if (input[i] == '^') {
                if (i >= len-2) {
                    result.push_back('^');
                } else if (input[i+1] != '^') {
                    result.push_back('^');
                } else if (i < len-3 && isHex(input[i+2]) && isHex(input[i+3])) {
                    unsigned int c;
                    sscanf(input.substr(i+2,2).c_str(), "%x", &c);
                    if (c >= 128) {
                        result.push_back(c);
                        i += 3;
                    } else {
                        input[i+3] = (char) c;
                        i += 2;
                    }
                } else if (input[i+2] > 63) {
                    input[i+2] -= 64;
                    i += 1;
                } else {
                    input[i+2] += 64;
                    i += 1;
                }
            } else {
                result.push_back(input[i]);
            }
        }
        return result;
    }
private:
    bool isHex(const char c) {
        return ('0'<=c && c<='9') || ('a'<=c && c<='f');
    }
};

CamiCami2011/08/31 01:54Hey hey hey, take a gaednr at what' you've done

ifhwgxmyifhwgxmy2011/09/01 01:26IyxF2c <a href="http://zzvvdkadzyzw.com/">zzvvdkadzyzw</a>

vsyaesivsyaesi2011/09/03 20:20bbeGDx <a href="http://xqcimzgfyxjv.com/">xqcimzgfyxjv</a>

2009-10-23

PizzaDelivery

| 07:29

問題文, SRM 451

2人の配達人を使って、ピザを配達し終えるのにかかる最短時間を求める。

解くのに2時間強かかった。しょうもないバグにより3回、時間制限により1回、システムテストで落とされた。解法はBFS+Brute Forceなので割と単純だが、異常に調子が良い時でないと本番の時間内にバグなしで解ける気がしない。

300.00/1000 (4-failed)

const static int INFTY = INT_MAX/2;

class PizzaDelivery {
    public:
        int deliverAll(vector <string> terrain) {
            const int H = terrain.size();
            const int W = terrain[0].size();
            vector<pair<int,int> > piza;
            pair<int,int> r;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (terrain[y][x] == 'X') {
                        r = make_pair(y, x);
                    } else if (terrain[y][x] == '$') {
                        piza.push_back(make_pair(y,x));
                    }
                }

            int D[100];
            int T[100][100];
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                    T[y][x] = INFTY;
            T[r.first][r.second] = 0;
            queue<pair<int,int> > Q;
            Q.push(r);
            while (!Q.empty()) {
                pair<int,int> a = Q.front(); Q.pop();
                const int y = a.first, x = a.second;
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                for (int i = 0; i < 4; i++) {
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                        if (!isdigit(terrain[ny][nx]) || !isdigit(terrain[y][x])) {
                            if (T[y][x]+2 < T[ny][nx]) {
                                T[ny][nx] = T[y][x] + 2;
                                Q.push(make_pair(ny, nx));
                            }
                            continue;
                        }
                        if (abs(terrain[ny][nx]-terrain[y][x]) == 0 && 
                                T[y][x]+1 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 1;
                            Q.push(make_pair(ny, nx));
                        } else if (abs(terrain[ny][nx]-terrain[y][x]) == 1 && 
                                T[y][x]+3 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 3;
                            Q.push(make_pair(ny, nx));
                        }
                    }
                }
            }
            for (int i = 0; i < piza.size(); i++) {
                D[i] = T[piza[i].first][piza[i].second];
                if (D[i] == INFTY) return -1;
            }

            int minTime = INFTY;
            for (int i = 0; i < 1<<(piza.size()-1); i++) {
                bitset<20> pat(i);
                vector<int> vboy1, vboy2;
                for (int j = 0; j < piza.size(); j++) {
                    if (pat[j]) vboy1.push_back(D[j]);
                    else        vboy2.push_back(D[j]);
                }
                int boy1=0, boy2=0;
                if (vboy1.size() > 0)
                    boy1 = 2*accumulate(vboy1.begin(), vboy1.end(), 0) 
                        - *max_element(vboy1.begin(), vboy1.end());
                if (vboy2.size() > 0)
                    boy2 = 2*accumulate(vboy2.begin(), vboy2.end(), 0) 
                        - *max_element(vboy2.begin(), vboy2.end());
                //cout << pat << " " << boy1 << " " << boy2 << endl;
                minTime = min(minTime, max(boy1, boy2));
            }
            return minTime;
        }
};

nphuuejznphuuejz2011/02/28 17:01PX5gMr <a href="http://thxvtmuhvzkh.com/">thxvtmuhvzkh</a>, [url=http://aegsueyzfdwj.com/]aegsueyzfdwj[/url], [link=http://juwwqktqnkxe.com/]juwwqktqnkxe[/link], http://fuvdtrdrrxop.com/

2009-09-20

MatArith

| 21:03

問題文, TCI '02 Round 2

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 1から。

行列同士の足し算と掛け算。

169.75/500 (1 failed)

typedef long long int64;

class MatArith {
public:
    vector <string> calculate(vector <string> A, vector <string> B, vector <string> C, string equation) {
        return print(calc(parse(A),parse(B),parse(C),equation));
    }
private:
    vector<string> print(vector<vector<int64> > M) {
        const int R = M.size();
        if (R == 0) return vector<string>();
        const int C = M[0].size();
        vector<string> ret(R);
        for (int r = 0; r < R; r++) {
            ostringstream oss;
            for (int c = 0; c < C; c++) {
                if (c >= 1) oss << " ";
                oss << M[r][c];
            }
            ret[r] = oss.str();
        }
        return ret;
    }
    vector<vector<int64> > parse(vector<string>& M) {
        const int R = M.size();
        vector<vector<int64> > ret(R);
        for (int r = 0; r < R; r++) {
            istringstream iss(M[r]);
            int t;
            while (iss >> t) ret[r].push_back(t);
        }
        return ret;
    }
    vector<vector<int64> > calc(const vector<vector<int64> > A,
            const vector<vector<int64> > B, const vector<vector<int64> > C,
            const string& equation) {
        stack<vector<vector<int64> > > matStack;
        int opStack = 0;
        for (int i = 0; i < equation.size(); i++) {
            if (equation[i] == '+') {
                opStack++;
            } else if (equation[i] == '*') {
                vector<vector<int64> > T1 = matStack.top(); matStack.pop();
                i++;
                vector<vector<int64> > T2;
                if (equation[i] == 'A') T2 = A;
                else if (equation[i] == 'B') T2 = B;
                else  T2 = C;
                vector<vector<int64> > M = matmul(T1, T2);
                if (M.size() == 0) return M;
                matStack.push(M);
            } else if (equation[i] == 'A') {
                matStack.push(A);
            } else if (equation[i] == 'B') {
                matStack.push(B);
            } else {
                matStack.push(C);
            }
        }
        while (opStack-- > 0) {
            vector<vector<int64> > T1 = matStack.top(); matStack.pop();
            vector<vector<int64> > T2 = matStack.top(); matStack.pop();
            vector<vector<int64> > M = matadd(T1, T2);
            if (M.size() == 0) return M;
            matStack.push(M);
        }
        return matStack.top();
    }
    vector<vector<int64> > matmul(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (CA != RB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CB,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CB; j++) {
                for (int k = 0; k < CA; k++) {
                    M[i][j] += A[i][k] * B[k][j];
                }
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
    vector<vector<int64> > matadd(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (RA != RB || CA != CB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CA,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CA; j++) {
                M[i][j] += A[i][j] + B[i][j];
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
};

2009-09-10

WalkingHome

| 16:29

問題文, SRM 222

Algorithm Tutorials -- How to Find a Solutionから。

学校から家に帰るまでに、最低何回道路を横断すればよいのか。道路は2つまでしか横断できないと勘違いしたために、1回落ちた。

150.00/500 (1 failed)

struct Johnny {
    int y, x, times;
    Johnny() { Johnny(0,0,0); }
    Johnny(const int y, const int x, const int times) :
        y(y), x(x), times(times) {}
};

class WalkingHome {
public:
    int fewestCrossings (vector <string> map) {
        const int H = map.size();
        const int W = map[0].size();
        Q = queue<Johnny>();
        visited = vector<vector<int> >(H, vector<int>(W, INT_MAX));
        int homeY=0, homeX=0;
        for (int y = 0; y < H; y++) {
            // cout << map[y]<< endl;
            for (int x = 0; x < W; x++) {
                if (map[y][x] == 'S') {
                    checkAndPush(Johnny(y,x,0));
                } else if (map[y][x] == 'H') {
                    homeY = y;
                    homeX = x;
                    map[y][x] = '.';
                }
            }
        }

        int result = INT_MAX;
        while (!Q.empty()) {
            Johnny j(Q.front());  Q.pop();
            if (j.y == homeY && j.x == homeX)
                result = min(result, j.times);
            const static int d[4][2] = {
                {1,0}, {-1,0}, {0,1}, {0,-1} };
            for (int i = 0; i < 4; i++) {
                const int ny = j.y + d[i][0];
                const int nx = j.x + d[i][1];
                int nnx, nny;
                if (!(0<=ny&&ny<H && 0<=nx&&nx<W)) continue;
                switch (map[ny][nx]) {
                    case '.':
                        checkAndPush(Johnny(ny,nx,j.times));
                        break;
                    case '|':
                        if (d[i][1] == 0) break;
                        nnx = nx + d[i][1];
                        while (0<=nnx&&nnx<W && map[ny][nnx] == '|')
                            nnx += d[i][1];
                        if (0<=nnx&&nnx<W && map[ny][nnx] == '.')
                            checkAndPush(Johnny(ny,nnx,j.times+1));
                        break;
                    case '-':
                        if (d[i][0] == 0) break;
                        nny = ny + d[i][0];
                        while (0<=nny&&nny<H && map[nny][nx] == '-')
                            nny += d[i][0];
                        if (0<=nny&&nny<H && map[nny][nx] == '.')
                            checkAndPush(Johnny(nny,nx,j.times+1));
                        break;
                }

            }
        }
        if (result == INT_MAX) return -1;
        else return result;
    }
private:
    queue<Johnny> Q;
    vector<vector<int> > visited;
    void checkAndPush(const Johnny& j) {
        if (j.times < visited[j.y][j.x]) {
            Q.push(j);
            visited[j.y][j.x] = j.times;
        }
    }
};

2009-09-07

GardenHose

| 12:51

問題文, SRM 197

庭の外側からホースを使って水を撒くとき、撒けないプラントは何個か。1回落とされたのは、ホースの長さが庭の長さより長い場合の処理を実装するのを忘れたため。解いた後にEditorialを見たら、撒けた場合にはcontinueし、ループの最後までいってしまったらカウンタを増やすというやり方が紹介されていた。その方法の方がバグを作りにくいな。

173.11/250 (1 failed)

class GardenHose {
public:
    int countDead(int n, int rowDist, int colDist, int hoseDist) {
        if (rowDist*n <= hoseDist || colDist*n <= hoseDist)
            return 0;
        vector<vector<int> > garden(n, vector<int>(n, 'x'));
        for (int i = 0; i < n; i++) {
            for (int j = 0; (j+1)*rowDist <= hoseDist; j++)
                garden[j][i] = garden[n-j-1][i] = 'o';
            for (int j = 0; (j+1)*colDist <= hoseDist; j++)
                garden[i][j] = garden[i][n-j-1] = 'o';
        }
        int result = 0;
        for (int i = 0; i < n; i++)
            result += count(garden[i].begin(), garden[i].end(), 'x');
        return result;
    }
};

2009-09-06

CaptureThemAll

| 19:09

問題文, SRM 207

Algorithm Tutorials -- How to Find a Solutionから。

Knightだけで、RookとQueenをとるのに最低何ステップかかるか。BFSで解ける。どのように実装すればよいのかで迷った。1回目と2回目に出したときは、setを使って同じ条件の時にはもう調べないようにしなかったために、queueの許容量を超えてしまい、例外が発生して落ちた(例外が発生しなくても時間制限に引っかかったと思うが)。

300.00/1000 (2 failed)

struct State {
    const static int ROOK_VAL = 1;
    const static int QUEEN_VAL = 10;
    const static int BOTH_VAL = ROOK_VAL+QUEEN_VAL;
    pair<int,int> p;
    int step, val;
    State() {}
    State(const pair<int,int> p) : p(p) {
        step = 0;
        val = 0;
    }
    State(const pair<int,int> p, const int step) : p(p), step(step) {
        val = 0;
    }
};
bool operator< (const State& a, const State& b) {
    if (a.step < b.step) {
        return true;
    } else if (a.step > b.step) {
        return false;
    } else {
        if (a.val > b.val) {
            return true;
        } else if (a.val < b.val) {
            return false;
        } else {
            return a.p < b.p;
        }
    }
}

class CaptureThemAll {
public:
    int fastKnight(string knight, string rook, string queen) {
        const pair<int,int> rPos = getPos(rook);
        const pair<int,int> qPos = getPos(queen);
        queue<State> Q;
        Q.push(State(getPos(knight)));
        set<State> checked;
        checked.insert(Q.front());
        while (!Q.empty()) {
            State k = Q.front(); Q.pop();
            if (k.val == State::BOTH_VAL) return k.step;
            for (int dy = -2; dy <= 2; dy++) {
                for (int dx = -2; dx <= 2; dx++) {
                    if (dy*dy+dx*dx != 5) continue;
                    const int ny = k.p.first + dy;
                    const int nx = k.p.second + dx;
                    if (0<=ny&&ny<BOARD_SZ && 0<=nx&&nx<BOARD_SZ) {
                        State next(make_pair(ny,nx), k.step+1);
                        if (k.val%10 == 1 || next.p == rPos) 
                            next.val += State::ROOK_VAL;
                        if (k.val/10 == 1 || next.p == qPos)
                            next.val += State::QUEEN_VAL;
                        if (checked.find(next) == checked.end()) {
                            Q.push(next);
                            checked.insert(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
private:
    const static int BOARD_SZ = 8;
    pair<int,int> getPos(const string& s) {
        return make_pair(s[1]-'1', s[0]-'a');
    }
};

SmartWordToy

| 16:33

問題文, SRM 233

Algorithm Tutorials -- How to Find a Solutionから。

startからfinishに禁止された文字列を経由するためにかかる変換回数。BFSで解ける。時間制限がきつかった。

157.45/500 (1 failed)

class SmartWordToy {
public:
    int minPresses(string start, string finish, vector <string> forbid) {
        forbids.clear();
        for (int i = 0; i < forbid.size(); i++) {
            istringstream iss(forbid[i]);
            vector<string> token(WORD_LEN);
            for (int j = 0; j < WORD_LEN; j++)
                iss >> token[j];
            generateForbids(0, 0, token);
        }

        queue<pair<int,int> > Q;
        const int startCode = encode(start);
        const int finishCode = encode(finish);
        Q.push(make_pair(startCode, 0));
        set<int> checked;
        checked.insert(startCode);
        while (!Q.empty()) {
            pair<int,int> p = Q.front(); Q.pop();
            if (p.first == finishCode) return p.second;
            for (int i = 0; i < 4; i++) {
                for (int pad = -1; pad <= 1; pad += 2) {
                    int nextCode(next(p.first, pad, i));
                    if (checked.find(nextCode) == checked.end() && 
                            forbids.find(nextCode) == forbids.end()) {
                        checked.insert(nextCode);
                        Q.push(make_pair(nextCode, p.second+1));
                    }
                }
            }
        }
        return -1;
    }
private:
    set<int> forbids;
    const static int WORD_LEN = 4;
    void generateForbids(const int code, const int idx, const vector<string>& token) {
        if (idx == WORD_LEN) {
            forbids.insert(code);
            return;
        }
        for (int i = 0; i < token[idx].size(); i++)
            generateForbids(code*100+token[idx][i]-'a', idx+1, token);
    }
    int encode(const string& s) {
        int code = 0;
        for (int i = 0; i < WORD_LEN; i++)
            code = 100*code + s[i]-'a';
        return code;
    }
    int next(int code, const int pad, const int i) {
        const static int table[5] = {100*100*100*100,100*100*100,100*100,100,1};
        int v = code % table[i] / table[i+1];
        code -= v * table[i+1];
        v = (v+pad+26) % 26;
        code += v * table[i+1];
        return code;
    }
};

2009-09-04

PassingGrade

| 17:21

メイン(?)ブログの方にGoogle Code Jam 2009 - Qualification Roundの参戦記録は書いた。結果は約1時間半で全問解けて、65位。

問題文, SRM 185

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

期末テストで単位を得るためにとらなければならない最低点数を求める。単精度では精度が足りないらしく、落とされた。

204.22/250 (1 failed)

class PassingGrade {
public:
    int pointsNeeded(vector <int> pointsEarned, vector <int> pointsPossible, int finalExam) {
        int totalEarned = accumulate(pointsEarned.begin(), pointsEarned.end(), 0);
        int totalPossible = accumulate(pointsPossible.begin(), pointsPossible.end(), 0) 
            + finalExam;
        int minimum = (int) ceil(0.65l*totalPossible - totalEarned);
        if (minimum > finalExam) return -1;
        else if (minimum < 0) return 0;
        else return minimum;
    }
};

2009-08-31

StampPads

| 13:51

問題文, SRM 158

欲しい色を全部そろえるには、何種類のスタンプパッドを買えば良いのか。Brute forceで解ける問題だったが、DPで解こうとした。2回タイムアウトで落とされたが、始めにmaskを作る方法に変えたら通った。

150.00/500 (2 failed)

class StampPads {
public:
    int bestCombo(vector <string> pads, vector <string> wishlist) {
        numPads = pads.size();
        pds = vector<vector<string> >(numPads, vector<string>(5));
        for (int i = 0; i < numPads; i++) {
            istringstream iss(pads[i]);
            for (int j = 0; iss >> pds[i][j]; j++) ;
        }
        bitset<32> got;
        numWishes = wishlist.size();
        wishL = wishlist;
        mask = vector<bitset<32> >(numPads);
        for (int i = 0; i < numPads; i++)
            for (int j = 0; j < numWishes; j++)
                mask[i][j] = find(pds[i].begin(),pds[i].end(),wishL[j]) != pds[i].end();
        return go(0, 0, got);
    }
    int numPads;
    vector<vector<string> > pds;
    vector<string> wishL;
    vector<bitset<32> > mask;
    int numWishes;
    int go(const int bought, const int idx, const bitset<32>& got) {
        if (got.count() >= numWishes) return bought;
        if (idx >= numPads) return -1;
        bitset<32> next(got | mask[idx]);
        if (next != got) {
            int retBuy = go(bought+1, idx+1, next);
            int retNot = go(bought, idx+1, got);
            if (retBuy == -1 && retNot == -1) return -1;
            else if (retBuy == -1) return retNot;
            else if (retNot == -1) return retBuy;
            else return min(retBuy, retNot);
        } else {
            return go(bought, idx+1, got);
        }
    }
};

2009-08-30

InstantRunoff

| 17:56

問題文, SRM 175

選挙で、誰が過半数の票を獲得するか。

166.88/550 (1 failed)

class InstantRunoff {
public:
    string outcome(string candidates, vector <string> ballots) {
        const int numCandidates = candidates.size();
        const int numVoters = ballots.size();
        vector<int> idx(numVoters, 0);
        vector<char> failed;
        for (int i = 0; i < numCandidates; ) {
            map<char,int> votes;
            for (int k = 0; k < numCandidates; k++) 
                if (find(failed.begin(),failed.end(),candidates[k]) == failed.end())
                    votes[candidates[k]] = 0;
            for (int j = 0; j < numVoters; j++) {
                while (votes.find(ballots[j][idx[j]]) == votes.end()) idx[j]++;
                votes[ballots[j][idx[j]]]++;
            }
            int minimum = INT_MAX;
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second > numVoters/2)
                    return string(1,v->first);
                if (v->second < minimum)
                    minimum = v->second;
            }
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second == minimum) {
                    failed.push_back(v->first);
                    i++;
                    for (int j = 0; j < numVoters; j++) {
                        if (v->first == ballots[j][idx[j]])
                            idx[j]++;
                    }
                }
            }
        }
        return "";
    }
};

2009-08-25

QuiningTopCoder

| 14:09

問題文, SRM 152

自分自身のソースを出力するプログラムかどうかを確認。

150.0/500 (1 failed)

class QuiningTopCoder {
public:
    string testCode(string source) {
        string output;
        const static int TIME_LIMIT = 80000;
        stack<int> stk;
        for (int i = 0; i < TIME_LIMIT; i++) stk.push(0);
        int IP=0, D=1, N=source.size();
        int cycle = 0;
        while (source[IP] != '@' && cycle < TIME_LIMIT) {
            const char c = source[IP];
            int DD = D;
            if (isdigit(c)) {
                stk.push(c-'0');
            } else if (c == '$') {
                stk.pop();
            } else if (c == ':') {
                int X = stk.top(); stk.pop();
                stk.push(X); stk.push(X);
            } else if (c == 'W') {
                int A = stk.top(); stk.pop();
                int B = stk.top(); stk.pop();
                stk.push(A); stk.push(B);
            } else if (c == ',') {
                int X = stk.top(); stk.pop();
                output += source[abs(X)%N];
                if (output == source ||
                        output != source.substr(0,output.length())) 
                    break;
            } else if (c == '+') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A+B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '-') {
                int A = stk.top(); stk.pop(); 
                int B = stk.top(); stk.pop();
                stk.push(A-B);
                if (abs(stk.top()) > 1000000000) break;
            } else if (c == '#') {
                DD *= 2;
            } else if (c == 'R') {
                DD *= -1; D *= -1;
            } else if (c == 'S') {
                int X = stk.top(); stk.pop();
                if (X > 0) stk.push(1);
                else stk.push(-1);
            } else if (c == '_') {
                int X = stk.top(); stk.pop();
                D = DD = X % N;
            } else if (c == 'J') {
                int X = stk.top(); stk.pop();
                IP = abs(X) % N;
            } 
            if (c != 'J')
                IP = (3*N+IP+DD) % N;
            cycle++;
        }
      
        ostringstream res;
        if (source[IP] == '@') {
            res << "BADEND " << cycle;
        } else if (cycle == TIME_LIMIT) {
            res << "TIMEOUT";
        } else if (abs(stk.top()) > 1e+9) {
            res << "OVERFLOW " << cycle;
        } else if (source != output) {
            res << "MISMATCH " << cycle;
        } else {
            res << "QUINES " << cycle;
        }
        return res.str();
    }
};