ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1501. Sense of Beauty

WA9, give tests please!
Posted by Vasily Slesarev 25 May 2011 23:16
Hello, I use DP and get WA9.
Please give tests.
Re: WA9, give tests please!
Posted by trn 20 Jun 2011 13:20
pls give me solution.

Edited by author 29.06.2011 15:01
Re: WA9, give tests please!
Posted by Vasily Slesarev 24 Jun 2011 23:23
#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;
}
Re: WA9, give tests please!
Posted by Vasily Slesarev 24 Jun 2011 23:24
But I think, it is difficult to understand it.)
Re: WA9, give tests please!
Posted by trn 28 Jun 2011 13:27
4
1010
0110


22221111

Edited by author 29.06.2011 15:00