| 
 | 
вернуться в форумWA9, give tests please! Hello, I use DP and get WA9. Please give tests. Re: WA9, give tests please! Послано  trn 20 июн 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! Послано  trn 28 июн 2011 13:27 4 1010 0110     22221111   Edited by author 29.06.2011 15:00  |  
  | 
|