A. Potion of Immortality
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/gym/100187/problem/A
Description
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.
Sample Input
3 2
Sample Output
1
HINT
题意
有n瓶药，1瓶好的，其他都是毒药，一次性喝k瓶，问你在最坏情况下，最少死多少只兔子呢？
题解：
答案当然是n-1/k，很显然
讨论一下当n=k=1的情况就好了
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 200101 #define mod 10007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** ll n,k; int main() { n=read(),k=read(); if(n==1) puts("0"); else if(n==k) puts("-1"); else { ll ans1=(n-k); n--; if(n%k!=0) n+=k; printf("%lld ",min(n/k,ans1)); } }