11420 - Chest of Drawers

[f74956227]

Is this a DP problem? or a combination math problem.. i have tried a lot but still have no idea with this problem...can someone give me a little hints?

[sclo]

Could you include the name of the problem in the topic?
Yes, I believe this problem is DP.

[emotional blind]

Code: Select all

nway(n, s, pdl)  = nway(n-1, s, 0) + nway(n-1, s-1, 1)    if pdl=1
                        = nway(n-1, s, 0) + nway(n-1, s, 1) if pdl =0


here,
n = number of drawer
s = number of drawer to be secured
pdl = last drawer locked or not [1 means locked]

[Robert Gerbicz]

Don't forget that if s>n, then the answer is 0. (There are such tests in the input.)

[f74956227]

i finally got ac but i think the recursive function of the DP is

n(a,b,1)=n(a-1,b-1,1)+n(a-1,b-1,0)
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)

a is the number of drawer and b is the secured-num and the 0 or 1 means that the situation of the top drawer.

Finally thank all of you^^

[emotional blind]

:D
i finally got ac but i think the recursive function of the DP is

n(a,b,1)=n(a-1,b-1,1)+n(a-1,b-1,0)
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)

a is the number of drawer and b is the secured-num and the 0 or 1 means that the situation of the top drawer.

Finally thank all of you^^

n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)
how does this work? here u are increasing b..

[f74956227]

Just by initialize the array qq"

n[i][j][k]=0;
if(i<j)n[i][j][k]=0;
f((k==1 && i==j)||(k==1 && j==1))n[i][j][k]=1;
if(k==1 && j==0)n[i][j][k]=0;
if(k==0)
{
if(i-j<=1)n[i][j][k]=0;
else if(i-j==2)n[i][j][k]=1;
}
}

XDDD..

[shopnobaj_raju]

getting runtime error . please help

Code: Select all

#include<stdio.h>
#include<math.h>


unsigned long long int secureit(int n,int s);
unsigned long long int soln_lck_fst_it(int n,int s);
unsigned long long int secure[100][100];
unsigned long long int soln_lck_fst[100][100];


int main()
{
   int n,s;
   unsigned long long int ans;
   while(1)
   {
      int i,j;
      scanf("%d %d",&n,&s);
      if(n<0 && s<0) break;
      for(i=0;i<100;i++)
         for(j=0;j<100;j++) secure[i][j]=-1;
      for(i=0;i<100;i++)
         for(j=0;j<100;j++) soln_lck_fst[i][j]=-1;
        ans=secureit(n,s);
      printf("%llu\n",ans);
   }
   return 0;
}


unsigned long long int soln_lck_fst_it(int n,int s)
{
   if(s==n || s==n-1) return 1;
   if(n==2 && s==1) return 1;
   if(n==2 && (s==1 || s==2)) return 1;
   if(s>n) return 0;
   if(soln_lck_fst[n][s]!=-1) return soln_lck_fst[n][s];
   if(s==1)
   {
      soln_lck_fst[n][s]=(unsigned long long int) pow(2,n-2) - ((n-2)*(n-3))/2;
      return soln_lck_fst[n][s];
   }
   soln_lck_fst[n][s]=secureit(n-1,s-1);
   return soln_lck_fst[n][s];
}

unsigned long long int secureit(int n,int s)
{

    if(s==n || s==n-1) return 1;
   if(n==2 && s==1) return 1;
   if(n==2 && (s==1 || s==2)) return 1;
   if(s>n) return 0;
   if(secure[n][s]!=-1) return secure[n][s];
   secure[n][s]=soln_lck_fst_it(n,s)+secureit(n-1,s)-soln_lck_fst_it(n-1,s)+soln_lck_fst_it(n-1,s+1);
   return secure[n][s];


}


[brianfry713]

You are assigning -1 to unsigned variables.

[eric7237cire]

While probably obvious to most, just in case.

You need to use 64 bit integers (signed is ok)