tc recursive dp 

Problem Statement for BearPlaysDiv2 Problem Statement      Limak is a little bear who loves to play. Today he is playing by moving some stones between three piles of stones. Initially, the piles contain A, B, and C stones, respectively. Limak's goal is to produce three equal piles. Limak will try reaching his goal by performing a sequence of zero or more operations. In each operation he will start by choosing two unequal piles. Let's label their sizes X and Y in such a way that X < Y. He will then double the size of the smaller chosen pile by moving some stones between the two chosen piles. Formally, the new sizes of the two chosen piles will be X+X and Y-X. You are given the ints A, B, and C. Return "possible" (quotes for clarity) if there is a sequence of operations that will make all three piles equal. Otherwise, return "impossible".   Definition      Class: BearPlaysDiv2 Method: equalPiles Parameters: int, int, int Returns: String Method signature: String equalPiles(int A, int B, int C) (be sure your method is public)        Constraints - A, B and C will be between 1 and 500, inclusive.   Examples 0)      10 15 35 Returns: "possible" One valid sequence of operations looks as follows: The initial pile sizes are 10, 15, and 35. For the first operation Limak will choose the piles with 15 and 35 stones. After doubling the size of the smaller pile the new sizes of these two piles will be 30 and 20. After the first operation the pile sizes are 10, 30, and 20. For the second operation Limak will choose the piles with 10 and 30 stones. After doubling the size of the smaller pile the new sizes of these two piles will be 20 and 20. After the second operation each pile has 20 stones, which means that Limak has reached his goal. 1)      1 1 2 Returns: "impossible" No matter what Limak does, there will always be two piles with a single stone each and one pile with 2 stones. 2)      4 6 8 Returns: "impossible" 3)      18 18 18 Returns: "possible" Sometimes Limak can reach his goal without making any operations. 4)      225 500 475 Returns: "possible" This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:         Single Round Match 664 Round 1 - Division II, Level Two

--------------------------------------------------editorial---------------------------------------------------------

in this peoblem dp state is 2 d not 3 d dp[a][b]  since for a given a and b c will always remain same ,

just  memorise whether  a,b,c state has come before or not...

-----------------------------------------------------------code---------------------------------------------

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int dp[5500][5500];

string f="impossible";

int nc=0;

class BearPlaysDiv2

{

int equal(int a,int b,int c)

 {

 

  if(a>=0 && b>=0 && c>=0)

  {

  nc++;

 

  if(dp[a][b]==0)

  {

  if(a==b && b==c) 

        {

     

           f="possible";

   

         }

   

   {

    dp[a][b]=1;

    dp[a][c]=1;

    dp[b][c]=1;

    dp[b][a]=1;

    dp[c][a]=1;

    dp[c][b]=1;

   

     equal(a+a,b-a,c);

   

        equal(a+a,c-a,b);

     equal(b+b,c-b,a);

     equal(b+b,a-b,c);

     equal(c+c,b-c,a);

     equal(c+c,a-c,b);

  }

 }

   

 }

 return 0;

 

 }

string equalPiles(int a, int b, int c) 

 {

 

   equal(a,b,c);

   return f;

 }

};