# UVa 11420

## Summary

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

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

• Use long long int

## C++ Implementation

```#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));
}
}
```

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

## Output

```16
9
6
1
0
64310620249541505
```