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

Any idea?
Posted by Olympic Bear 12 Nov 2006 01:33


Edited by author 12.11.2006 01:35
Re: Any idea?
Posted by Piratek-(akaDK) 12 Sep 2008 21:40
BFS
Re: Any idea?
Posted by S.77 15 Aug 2011 22:53
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.
Re: Any idea?
Posted by IgorKoval(from Pskov) 10 Feb 2012 04:47
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"