p273.ans1
======================
br

=================
p273.ans2
======================
Nobody

=================
p273.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int rule_mask[4][4];
string row;

int color_id(char c) { return c == 'b' ? 0 : c == 'r' ? 1 : c == 'y' ? 2 : 3; }

void read() {
    int cnt[4];
    for(int c = 0; c < 4; c++) {
        cin >> cnt[c];
    }

    for(int c = 0; c < 4; c++) {
        for(int i = 0; i < cnt[c]; i++) {
            string rule;
            cin >> rule;
            rule_mask[color_id(rule[0])][color_id(rule[1])] |= 1 << c;
        }
    }

    cin >> row;
}

void solve() {
    // dp[l][r] is a 4-bit mask whose set bits are the colors that the segment
    // row[l..r] can be collapsed into as a single stone. Any collapse of a
    // segment ends with one final merge of two adjacent stones, and those two
    // stones are the independent collapses of a prefix row[l..mid] into some
    // color a and a suffix row[mid+1..r] into some color b. So for every split
    // point mid and every reachable pair (a, b) we add all colors that the
    // replacement rules allow (a, b) to turn into. rule_mask[a][b] already
    // holds that set as a mask, including the case where one ordered pair is
    // listed under several target colors.
    //
    // The base case is a single stone, which can only stay its own color. The
    // colors Sasha can win with are exactly the bits of dp[0][n-1], since
    // winning means reducing the whole row to one stone of his color.

    int n = (int)row.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++) {
        dp[i][i] = 1 << color_id(row[i]);
    }

    for(int len = 2; len <= n; len++) {
        for(int l = 0, r = len - 1; r < n; l++, r++) {
            int mask = 0;
            for(int mid = l; mid < r; mid++) {
                int left = dp[l][mid], right = dp[mid + 1][r];
                for(int a = 0; a < 4; a++) {
                    for(int b = 0; b < 4; b++) {
                        if((left >> a & 1) && (right >> b & 1)) {
                            mask |= rule_mask[a][b];
                        }
                    }
                }
            }

            dp[l][r] = mask;
        }
    }

    string colors = "bryw", ans;
    for(int c = 0; c < 4; c++) {
        if(dp[0][n - 1] >> c & 1) {
            ans += colors[c];
        }
    }

    cout << (ans.empty() ? "Nobody" : ans) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p273.in1
======================
2 1 1 1
br
bw
bw
wb
wy
brwy

=================
p273.in2
======================
1 1 1 1
br
bw
yr
by
bbbbbbbbbbb

=================
statement.txt
======================
273. Game Po
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



In the eastern country Pon-pong there is a very popular game Po. Po is the game with stones of four different colors: blue, red, yellow and white. The game is played by four participants. Before the beginning all stones are randomly placed in a row in front of the participants, each player chooses one of the stone colors (all players should have different colors). After that the game process begins. Each of the players in a turn chooses two nearby stones and replaces them by the third one, but only if this change is permitted by the "List of Po Replacements". Replacement is possible if the stones in the row and in the "List of Po Replacements" are in the same order. The game is considered to be finished if it is impossible to perform any change on the stones row. If after the end of the game only one stone remains, the player who chose the color of the stone left is a winner. If there are multiple stones, then the game result is draw. The boy Sasha liked very much the game Po during his visit to Pon-pong. He noticed, that in some games the players with some color are doomed to loose before the beginning of the game (after the distribution of the colors between players, but before the first move). Sasha decided to choose only such color, that he will have some chance to win the game, i.e. there is some sequence of players' moves, that leads to Sasha's victory.

Input
Each stone color is defined by one symbol: "b" -- blue, "r" -- red, "y" -- yellow and "w" -- white. The first line of the input file contains integer numbers B, R, Y and W (1 <= B,R,Y,W <= 16). The following B lines contain the rules of replacement of stones to the blue stone (one rule per line). Each rule is a pair of symbols without spaces, denoting the two stones which can be replaced by the blue one. The following R lines describe the rules of replacement to the red stone, Y lines --- to the yellow stone and W lines -- to the white stone. The last line contains from 1 to 200 symbols denoting stone colors -- the row of the stones before the beginning of the game.

Output
Output the single line without spaces containing the list of colors, for which there is a chance to win the game (in any order). If it is impossible to win the game with any color, output "Nobody".

Sample test(s)

Input
Test #1
2 1 1 1
br
bw
bw
wb
wy
brwy

Test #2
1 1 1 1
br
bw
yr
by
bbbbbbbbbbb

Output
Test #1
br

Test #2
Nobody
Author:	Sergey V. Mironov, Alexander S. Ivanov
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

=================
