Gym 100187A - Potion of Immortality

The world famous scientist Innokentiy has just synthesized the potion ofimmortality. Unfortunately, he put the flask with this potion on the shelfwhere most dangerous poisons of all time were kept. Now there are n flasks on this shelf, and the scientist has noidea which of them contains the potion of immortality.

Fortunately, Innokentiy has an infinite amount of rabbits. But thescientist doesn't know how exactly these potions affect rabbits. There is theonly thing he knows for sure. If rabbit tastes exactly k potions from the flasks on the shelf, it will survive if there was theimmortality potion among them and die otherwise. If rabbit tastes the number ofpotions different from k, the result will be absolutely unpredictable, so the scientist won'tmake such experiments no matter what.

The scientist intends to minimize the amount of lost rabbits whilesearching for the potion of immortality. You should determine how many rabbitshe has to sacrifice in the worst case.

Input

The only line contains two integers separated by space — n and k (1 ≤ n ≤ 2000, 1 ≤ k ≤ n) — the number of flasks on the Innokentiy's shelf andthe number of potions Innokentiy will give to a single rabbit to taste.

Output

If the scientist cannot determine which flusk contains the potion ofimmortality, output «-1». Otherwise, output a single integer — theminimal number of rabbits that Innokentiy will sacrifice in the worst casewhile searching for the potion of immortality.

Sample test(s)

input

3 2

output

1

input

4 2

output

2

 

思路：

n=1时不用牺牲任何兔子

n=k但不等于1时不能确定

剩下的情况最坏的情况就是每次都拿到k瓶毒药

代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF)
	{
		if (n == 1)
			printf("0\n");
		else
			if (n == k)
				printf("-1\n");
			else
			{
				int temp = n - 1;
				int mod = temp%k;
				if (mod == 0)
				{
					printf("%d\n", temp / k);
				}
				else
				{
					printf("%d\n", temp / k + 1);
				}
			}
	}

	return 0;
}