Little Tim is now a graduate,and is thinking about higher studies. However, he first needs to appear in anexam whose preparation alone includes memorizing the meanings of over 3500words!

After going through the list afew times, however, he sees trouble – he can remember all the word-meanings aslong as they keep coming in the same order. When quizzed in random order,however, he is at a complete loss. So, as any decent programmer would, hewrites a random shuffler to help him quiz himself.

To his dismay, however, hefinds that words that were near each other in the original list quite often endup being close together in the shuffled list as well. He does not like this atall, and suspects that his random shuffler may have some kind of a bug. Butbefore he recodes his shuffler he wants your help to make sure that theshuffler is indeed faulty.

So he is asking for your helpin determining how likely such events are even if the list is indeed gettingcompletely randomly shuffled, and even if his program is working perfectly.

Given the size of the list N,and a proximity factor K, you are to determine the expected number ofwastedwords in a shuffled list assuming that all possible shufflings are equallylikely. Informally, two words are consideredwasted if they appear at adistance less than or equal to K in both the lists. Assume that theoriginal list iscyclical and shuffled list is linear (non-cyclical).

Formally, let us suppose thattwo words A and B have indices o_a ando_b inthe original list and indices s_a ands_b inthe shuffled list, respectively (all indices are 0-based). Then both the wordsare consideredwasted if:

and

Input

The input consists of a seriesof cases. Each case consists of two integers N and K on a singleline. You may assume that 1≤K≤N≤100000.Input is terminated by a line containing two 0s, and has at most 125 lines ofinput.

Output

Output oneline for each test case except the last one. Each line of output should be ofthe form “Case X: Y”, where X is the serial number of output and Y is  the expected number of wasted words in theshuffled list, printed with exactly four digits after the decimal point, withrounding if necessary.

SampleInput                             Outputfor Sample Input

题意：输入n和k，你的任务是计算平均情况下，无效单词的个数，计算方法是：两个单词在重新排列后的位置不超过k

思路：我们先计算有效的位置，枚举后，从剩下的选出2*k来计算，用log来计算

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 100005;

int n, k;
long double f[maxn];

void solve() {
	if (n == 1) {
		printf("0.0000\n");
		return;
	}
	if (n <= 2 * k + 1) {
		printf("%d.0000\n", n);
		return;
	}

	int N = k << 1, p;
	long double sum = 0;
	for (int i = 1; i <= n; i++) {
		p = max(i-1-k, 0) + max(n-k-i, 0);
		if (p < N)
			continue;
		sum += exp(f[p] + f[n - N - 1] - f[n - 1] - f[p - N]);
	}
	printf("%.4lf\n", (double)(n - sum));
}

int main() {
	f[0] = f[1] = 0;
	for (int i = 2; i <= maxn; i++)
		f[i] = f[i-1] + log((long double) i); 

	int cas = 1;
	while (scanf("%d%d", &n, &k) != EOF && n) {
		printf("Case %d: ", cas++);
		solve();
	}
	return 0;
}

UVA - 11637 Garbage Remembering Exam （组合+概率）