11420 - Chest of Drawers

Moderator: Board moderators

11420 - Chest of Drawers

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?

f74956227
New poster

Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan

Could you include the name of the problem in the topic?
Yes, I believe this problem is DP.
Last edited by sclo on Wed Mar 19, 2008 11:56 am, edited 1 time in total.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

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]
Last edited by emotional blind on Wed Mar 19, 2008 2:20 pm, edited 1 time in total.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

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

Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek

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^^
f74956227
New poster

Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan

f74956227 wrote::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..

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

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..
f74956227
New poster

Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan

Re: 11420 - Chest of Drawers

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];}`
shopnobaj_raju
New poster

Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

Re: 11420 - Chest of Drawers

You are assigning -1 to unsigned variables.
brianfry713
Guru

Posts: 1861
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11420 - Chest of Drawers

While probably obvious to most, just in case.

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

Posts: 4
Joined: Sat Mar 30, 2013 4:06 pm