WHY????

Edited by author 15.10.2013 21:28

Edited by author 15.10.2013 21:28

You can read the input into the status table which has a number 'x' inside the cell "[i][j]" if the difference in height between two piles (red and black) after you remove 'i' cards from the first pile and 'j' from the second one is 'x'.
For the first statement example, the table is: {{0,-1,0,1,0},{-1,-2,-1,0,-1},{-2,-3,-2,-1,-2},{-1,-2,-1,0,-1},{0,-1,0,1,0}} (you can view it using "Wolfram|Alpha" service).

Thus, you are to "move" over the table cells from the top left-hand one to the bottom right-hand one, but you can't visit cells with the values different from -1,0,1. Use DP with the diagonal process to draw the right way.

#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::cin;
using std::cout;
using std::string;
using std::pair;


int main()
{
    int count;
    string first_pile, second_pile;

    cin >> count;
    cin >> first_pile >> second_pile;

    vector<vector<pair<int, int> > > possibility(count + 1);
    for (int i = 0; i <= count; ++i) {
        possibility[i].resize(count + 1);
    }
    possibility[0][0].first = 1;
    possibility[0][0].second = 0;
    for (int i = 1; i <= count; ++i) {
        if (possibility[i - 1][0].first == 0) {
            possibility[i][0].first = 0;
        } else {
            if (first_pile[i - 1] == '0') {
                if (possibility[i - 1][0].second <= 0) {
                    possibility[i][0].first = 1;
                    possibility[i][0].second = possibility[i - 1][0].second + 1;
                } else {
                    possibility[i][0].first = 0;
                }
            } else {
                if (possibility[i - 1][0].second >= 0) {
                    possibility[i][0].first = 1;
                    possibility[i][0].second = possibility[i - 1][0].second - 1;
                } else {
                    possibility[i][0].first = 0;
                }

            }
        }
        if (possibility[0][i - 1].first == 0) {
            possibility[0][i].first = 0;
        } else {
            if (second_pile[i - 1] == '0') {
                if (possibility[0][i - 1].second <= 0) {
                    possibility[0][i].first = 2;
                    possibility[0][i].second = possibility[0][i - 1].second + 1;
                } else {
                    possibility[0][i].first = 0;
                }
            } else {
                if (possibility[0][i - 1].second >= 0) {
                    possibility[0][i].first = 2;
                    possibility[0][i].second = possibility[i - 1][0].second - 1;
                } else {
                    possibility[i][0].first = 0;
                }

            }
        }
    }
    for (int i = 1; i <= count; ++i) {
        for (int j = 1; j <= count; ++j) {
            possibility[i][j].first = 0;
            if (possibility[i - 1][j].first != 0) {
                if (first_pile[i - 1] == '0') {
                    if (possibility[i - 1][j].second <= 0) {
                        possibility[i][j].first = 1;
                        possibility[i][j].second = possibility[i - 1][j].second + 1;
                        continue;
                    }
                } else {
                    if (possibility[i - 1][j].second >= 0) {
                        possibility[i][j].first = 1;
                        possibility[i][j].second = possibility[i - 1][j].second - 1;
                        continue;
                    }
                }
            }
            if (possibility[i][j - 1].first != 0) {
                if (second_pile[j - 1] == '0') {
                    if (possibility[i][j - 1].second <= 0) {
                        possibility[i][j].first = 2;
                        possibility[i][j].second = possibility[i][j - 1].second + 1;
                        continue;
                    }
                } else {
                    if (possibility[i][j - 1].second >= 0) {
                        possibility[i][j].first = 2;
                        possibility[i][j].second = possibility[i - 1][j].second - 1;
                        continue;
                    }
                }
            }
        }
    }
    if (possibility[count][count].first == 0) {
        cout << "Impossible\n";
//        cin >> count;
        return 0;
    }
    vector<int> answer(0);
    int i = count, j = count;
    while ((i != 0) || (j != 0)) {
        answer.push_back(possibility[i][j].first);
        if (possibility[i][j].first == 1) {
            --i;
        } else {
            --j;
        }
    }
    for (int k = answer.size() - 1; k >= 0; --k) {
        cout << answer[k];
    }
//    cin >> count;
    return 0;
}

 n>=4 !

But it's just hard to understand for me...
Why example is true?  If we take card 1 than card 1 than pile with ones is lager than pile with zeros. And lager by 2 cards, not by 1! See problem - <...> At each moment the resulting piles must not differ in size by more than one card <...>