If using recursive algorithm increase recursion depth limit at least 4000. For my algo 2000 was not enough import sys sys.setrecursionlimit(4000) I checked them using my AC algorithm 6 100110 000111 -> Impossible 10 1001100110 0101010101 -> 11111111112222222222 10 1001110000 0011111010 -> 11111211221212122222 11 01011100000 01111011001 -> 1111121112121212222222 14 10011111100101 00000110101010 -> 1111121212121111112222222222 18 100111111001010010 000001101010100111 -> 111112121212111111222222222222121112 18 100111111001010011 000001101010100011 -> Impossible Edited by author 02.01.2018 07:25 I have solved it by reduction to a graph exploration task. Each vertex consists of three parameters (i, j, pr). Where i, j denote number of card at the top of each pile and pr denotes previous state. pr is also a "used" array. So, if pr[N] [N] =none, then impossible. Otherwise just recover answer using pr. You can also have in your state additional parameter diff denotes difference between red and black cards. I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively. There is an edge iff difference at the next step would be not greater than one (abs) , obviously. Can anyone give some test cases? #include<bits/stdc++.h> using namespace std; int i, j, k, l, x, y, z, m, n, ans; string first, second; int dp[1010][1010][3][4], dir[1010][1010]; int make_way(int first_pile, int second_pile, char c, int state) { //cout << first_pile << ' ' << second_pile << endl; if(first_pile == n && second_pile == n){ if(state > 1) return 0; else return 1; } if(state > 1) return 0; int p = 0, q = 0, r = 0; char d; if(c == '0') d = '1'; else d = '0'; if(first_pile < n){ if(first[first_pile] == c){ p = make_way(first_pile + 1, second_pile, c, state + 1); } else{ p = make_way(first_pile + 1, second_pile, d, 1); } } if(second_pile < n){ if(second[second_pile] == c){ q = make_way(first_pile , second_pile + 1, c, state + 1); } else{ q = make_way(first_pile , second_pile + 1, d, 1); } } if(p == 1){ dir[first_pile][second_pile] = 1; } else if(q == 1) dir[first_pile][second_pile] = 2; dp[first_pile][second_pile][c - '0'][state] = p | q; return dp[first_pile][second_pile][c - '0'][state]; } int main() { cin >> n >> first >> second; ans = make_way(0, 0, '0', 0); if(!ans){ cout << "Impossible" ; return 0; } for(i = 0, j = 0; i < n || j < n; ){ cout << dir[i][j]; if(dir[i][j] == 1) i++; else j++; } return 0; } I want to use bool dp[N][N][3] array, where dp[i][j][0] is true if it is possible to solve the problem for last 'i' characters of string1 and for last 'j' characters of string2 and in current state it is necessary to take 0 and place into the stack of '0's. dp[i][j][1] is true if it is possible to solve the problem for last 'i' characters of string1 and for last 'j' characters of string2 and in current state it is necessary to take 1 and place into the stack of '1's. dp[i][j][2] is true if it is possible to solve the problem for last 'i' characters of string1 and for last 'j' characters of string2 and in current state stacks of '0's and '1's have the same size. Obviously (dp[N][N][2] == true) means that it is possible to solve the problem. My problem is that I can't fill this 3D array. Please help. you just need dp[i][j] and store there form were you get the last piece, if it was from 1 you can rebuild the path looking dp[i-1][j], if it was from 2 you llok dp[i][j-1]. If dp[i][j] = 0 you can't solve the problem. Please help me!!! Well, try these: 11 01011100000 01111011001 10 1001110000 0011111010 10 1001111110 0000011010 They should n't be impossible. Edited by author 31.08.2007 16:17 Edited by author 15.10.2013 21:28 Edited by author 15.10.2013 21:28 I think both answer would do Edited by author 12.11.2006 01:35 BFS 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. It help you. I don't post all code =) int n; vector<int> poker_log, I, II; vector<vector<bool>> IsUs; void f( int posI, int posII, int kol0, int kol1 ){ if( abs(kol0-kol1)>1 ) return; if( !IsUs[posI][posII] ) IsUs[posI][posII] = true; else return; /* hush-hush secreted deleted code here*/ } Just recursive function and bool vector IsUs[0..n][0..n] which answer on quastion "Was we in this state? Y/N" I have been trying to solve this problem but I am getting WA 8 , please help me. Hello, I use DP and get WA9. Please give tests. pls give me solution. Edited by author 29.06.2011 15:01 #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; } But I think, it is difficult to understand it.) 4 1010 0110 22221111 Edited by author 29.06.2011 15:00 Search: TLE; Greed: WA; DP: AC. -_-!!! After I have tle many times, I found that in java declaring a 10^6 array would take 0.5 second. =========== Input ===================== Sample input #1 4 0011 0110 Sample input #2 4 1100 1100 Sample input #3 6 101010 101010 ============= Output ================= Sample output #1 22121112 Sample output #2 Impossible Sample output #3 111111222222 OK. I found that my program gave me the wrong answer when the input is as follow: 1 0 0 I fixed this, and I still got WA#1. I need some hints. there is my code: program z1501; Var s,s1,s2:string; i,l,n:longint; p:shortint; st:boolean; begin readln(n); readln(s); readln(s1); s:=s+' '; s1:=s1+' '; s2:=''; i:=1; l:=1; st:=false; while True do begin while ((i<=n)or(l<=n))and not st do begin if (p=-1)and(s[i]='1')and(s[i+1]='1')and(s[i+2]='0')then begin s2:=s2+'11'; inc(i,2); p:=1; break; end; if (p=-1)and(s1[l]='1')and(s1[l+1]='1')and(s1[l+2]='0')then begin s2:=s2+'22'; inc(l,2); p:=1; break; end; if (p=1)and(s[i]='0')and(s[i+1]='0')and(s[i+2]='1')then begin s2:=s2+'11'; inc(i,2); p:=-1; break; end; if (p=1)and(s1[l]='0')and(s1[l+1]='0')and(s1[l+2]='1')then begin s2:=s2+'22'; inc(l,2); p:=-1; break; end; if (p=-1)and(s[i]='1')and(s[i+1]='0')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=-1)and(s1[l]='1')and(s1[l+1]='0')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=1)and(s[i]='0')and(s[i+1]='1')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=1)and(s1[l]='0')and(s1[l+1]='1')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=0)and(s[i]='1')and(s[i+1]='0')then begin s2:=s2+'1'; inc(i); p:=1; break; end; if (p=0)and(s1[l]='1')and(s1[l+1]='0')then begin s2:=s2+'2'; inc(l); p:=1; break; end; if (p=0)and(s[i]='0')and(s[i+1]='1')then begin s2:=s2+'1'; inc(i); p:=-1; break; end; if (p=0)and(s1[l]='0')and(s1[l+1]='1')then begin s2:=s2+'2'; inc(l); p:=-1; break; end; if (p=-1)and(s[i]='1')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=-1)and(s1[l]='1')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=1)and(s[i]='0')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=1)and(s1[l]='0')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=0)and(s[i]='1')then begin s2:=s2+'1'; inc(i); p:=1; break; end; if (p=0)and(s1[l]='1')then begin s2:=s2+'2'; inc(l); p:=1; break; end; if (p=0)and(s[i]='0')then begin s2:=s2+'1'; inc(i); p:=-1; break; end; if (p=0)and(s1[l]='0')then begin s2:=s2+'2'; inc(l); p:=-1; break; end; st:=true; end; if (length(s2)=2*n)or st then break; end; if length(s2)=2*n then writeln(s2) else writeln('Impossible'); end. My program gives right answers for all your tests, but I got WA7. Please help. Try to take as described in answer and you give this order of the cards: for test 0011 0110 and answer 22121112 ----> 01010(11)0 (mistake!) True possible answer is 22121121. Am I right? I think you don't understand problem statement. Sample test is right. You don't need to make sequence like 01010101..... Read the task again. Edited by author 06.12.2006 18:24 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 <...> See table: zero's, one's, difference ---|-------- 0 | 1 0 1 1 | 1 1 0 0 | 2 1 1 1 | 2 2 0 0 | 3 2 1 1 | 3 3 0 1 | 3 4 1 0 | 4 4 0 I think all is right. Edited by author 08.12.2006 23:22 Yes :). I was very stupid.... Many sanks, now i will try to solve it. |
|