問題 1352: P1085

題目描述

Matrix67發現身高接近的人似乎更合得來。Matrix67舉辦的派對共有N(1< =N< =10)個人參加，Matrix67需要把他們安排在圓桌上。Matrix67的安排原則是，圓桌上任意兩個相鄰人的身高之差不能超過K。請告訴Matrix67他共有多少種安排方法。

輸入

第一行輸入兩個用空格隔開的數N和K，其中1< =N< =10，1< =K< =1 000 000。 第二行到第N+1行每行輸入一個人的身高值。所有人的身高都是不超過1 000 000的正整數

輸出

輸出符合要求的安排總數

樣例輸入

4 10

2

16

6

10

樣例輸出

2

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

int f(int a[], int index, int n, int k)
{
	int i = 0, t = 0, sum = 0;
	if (n == index) {
		for (i = 0; i < n-1; ++i) {
			if (abs(a[i]-a[i+1])>k) return 0;
		}
		if (abs(a[n-1]-a[0])>k) return 0;
		return 1;
	}
	for (i = index; i < n; ++i) {
		t = a[index], a[index]= a[i], a[i] = t;
		sum += f(a, index+1, n, k);
		t = a[index], a[index]= a[i], a[i] = t;
	}
	return sum;
}
int main(void)
{
	int i = 0, n = 0, k = 0;
	scanf("%d %d", &n, &k);
	int a[n];
	for (i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	printf("%d", f(a, 0, n, k)/n);
	return 0;
}