CodeForces Gym 100187 A Potion of Immortality

http://codeforces.com/gym/100187/problem/A

A. Potion of Immortality

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

The scientist intends to minimize the amount of lost rabbits while searching for the potion of immortality. You should determine how many rabbits he 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 and the number of potions Innokentiy will give to a single rabbit to taste.

Output

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

Examples

input

3 2

output

1

input

4 2

output

2

题意理解错了。。。以为只有一种毒药。

有n种药，只有一瓶不是毒药，一只兔子每次和k种，问最坏的情况下最少毒死几只兔子。。。

思路：注意n=0,n=k,k=1的情况。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
   int i,j,k,n;
   while(scanf("%d%d",&n,&k)!=EOF)
   {
       if(n==1)
       {
           printf("0\n");
           continue;
       }
       if(n==k)
       {
           printf("-1\n");
           continue;
       }
       if(k==1)
       {
           printf("%d\n",n-1);
           continue;
       }
       if(n%k==0||n%k==1)
       {
           printf("%d\n",n/k);
       }
       else printf("%d\n",n/k+1);
   }
   return 0;
}