# UVa 11420

## Contents

## 11420 - Chest of Drawers[edit]

## Summary[edit]

A chest of drawers means a wardrobe which has many drawers aligned vertically. A drawer is secure only if it is locked and either it is the topmost drawer of the chest or the drawer just above it is also locked. There are **n** drawers and exactly **s** drawers are secure. How many such arrangements of drawers is possible?

## Explanation[edit]

This is a Dynamic Programming Problem.
Let **dp(n,s,x)** be the number of ways s drawers can me made secure out of the n drawers where the drawer just above these n drawers is locked if x = 1 and unlocked if x = 0. We consider our two options for the current topmost drawer (lock it or unlock it) and reduce this n sized problem to n-1 sized problem.

**General Cases**:
If the drawer just above these n drawers is unlocked (x = 0), the current topmost drawer cannot be made secure whether we lock it or not. If we lock it dp(n,s,0) reduces to dp(n-1,s,1). If we keep it unlocked dp(n,s,0) reduces to dp(n-1,s,0).
If the drawer is the topmost drawer or the drawer just above these n drawers is locked (x = 1), the current topmost drawer can be made secure only if it is locked. If we lock it, the current topmost drawer is secured and dp(n,s,0) reduces to dp(n-1,s-1,1). If we keep it unlocked dp(n,s,0) reduces to dp(n-1,s,0).

dp(n,s,0) = dp(n-1, s, 1) + dp(n-1,s,0) dp(n,s,1) = dp(n-1,s-1,1) + dp(n-1,s,0)

**Base Cases**:
When n = 1 (only one drawer),

- s = 1 and x = 0 ---- 1 of 1 drawer needs to be secured and the drawer above it is unlocked, so no possible way to secure the drawer (return 0)
- s = 1 and x = 1 ---- 1 of 1 drawer needs to be secured and the drawer above it is locked, only possible way to secure the drawer is to lock it (return 1)
- s = 0 and x = 1 ---- 0 of 1 drawer needs to be secured and the drawer above it is locked, only possible way to make the drawer insecure is to keep the drawer unlocked (return 1)
- s = 0 and x = 0 ---- 0 of 1 drawer needs to be secured and the drawer above it is unlocked, we can either lock the drawer or keep it unlocked, the drawer will not be secured (return 2)
- Any time s > n, that is, number of drawer that needs to be secured exceeds the number of drawers, there is no possible way (return 0)
- Any time s = n and x = 0, that is, number of drawer that needs to be secured equals the number of drawers and the drawer above these n drawer is unlocked, there is no possible way (return 0)

## Gotchas[edit]

- Use long long int

## C++ Implementation[edit]

```
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int L;
L arr[66][66][2];
L dp(int n, int s, int x)
{
if(n == 1)
{
if(s == 0 && x == 1)
return 1;
if(s == 0 && x == 0)
return 2;
if(s == 1 && x == 1)
return 1;
return 0;
}
if(n < s)
return 0;
if(n == s && x == 0)
return 0;
if(arr[n][s][x] != -1)
return arr[n][s][x];
if(x)
arr[n][s][x] = dp(n-1,s-1,1) + dp(n-1,s,0);
else
arr[n][s][x] = dp(n-1,s,1) + dp(n-1,s,0);
return arr[n][s][x];
}
main()
{
memset(arr, -1, sizeof(arr));
int n,s;
while(1)
{
scanf("%d %d", &n, &s);
if(n<0 && s<0)
break;
printf("%lld\n", dp(n,s, 1));
}
}
```

## Input[edit]

6 2 6 3 6 4 65 65 5 6 65 30 -1 -1

## Output[edit]

16 9 6 1 0 64310620249541505