|
|
back to boardWA9, give tests please! 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! #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! 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 |
|
|