Algorithm


Problem link- https://www.spoj.com/problems/CHAIR/

CHAIR - Chairs

no tags 

 

N chairs are placed in a circle.

There will be K attendants to a very important meeting.

However, the attendants do not like each other, so they do not want to sit beside each other in the meeting.

As the host of this important meeting, you want to find out how many ways there are to choose K chairs such that none of them are adjacent to each other. 

Input

The first line of the input is an integer N (4<=N<=1000), which denotes the number of chairs.

The next line is an integer K (1<=K<=N), which denotes the number of attendants to the meeting.

Output

Output the total number of ways to choose K chairs from N chairs such that none of the chairs are adjacent.

Since the answer can get very large, output the answer modulo 1,000,000,003.

Example

Input:
4
2

Output:
2

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000003LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e5+5;

int N, K;

int dp[2][1001][501];

ll solve(int fi, int n, int k){
	if(k == K)	return 1;
	if(n > N)	return 0;
	if(n == N && fi)	return 0;
	if(dp[fi][n][k] != -1)	return dp[fi][n][k];
	ll res = 0;
	if(n == 1)	res += solve(1, n + 2, k + 1);
	else	res += solve(fi, n + 2, k + 1);
	res += solve(fi, n + 1, k);
	res %= MOD;
	return dp[fi][n][k] = res;
}

int main(){
	// io;
	// cin >> N >> K;
	memset(dp, -1, sizeof dp);
	scanf("%d %d", &N, &K);
	if(K > N/2){
		printf("0\n");
		// cout << 0 << endl;
	}
	else{
		int res = solve(0, 1, 0);
		// cout << res << endl;
		printf("%d\n", res);
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
4
2

Output

x
+
cmd
2
Advertisements

Demonstration


SPOJ Solution-Chairs-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python