Codeforces Round #518 (Div. 2) A. Birthday 思维

92 阅读 0 评论 61 点赞

我是靠谱客的博主还单身巨人，最近开发中收集的这篇文章主要介绍Codeforces Round #518 (Div. 2) A. Birthday 思维，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A. Birthday

Ivan is collecting coins. There are only N different collectible coins, Ivan has K of them. He will be celebrating his birthday soon, so all his M freinds decided to gift him coins. They all agreed to three terms:

Everyone must gift as many coins as others.
All coins given to Ivan must be different.
Not less than L coins from gifts altogether, must be new in Ivan’s collection.
But his friends don’t know which coins have Ivan already got in his collection. They don’t want to spend money so they want to buy minimum quantity of coins, that satisfy all terms, irrespective of the Ivan’s collection. Help them to find this minimum number of coins or define it’s not possible to meet all the terms.

Input
The only line of input contains 4 integers N, M, K, L (1≤K≤N≤1018; 1≤M,L≤1018) — quantity of different coins, number of Ivan’s friends, size of Ivan’s collection and quantity of coins, that must be new in Ivan’s collection.

Output
Print one number — minimal number of coins one friend can gift to satisfy all the conditions. If it is impossible to satisfy all three conditions print “-1” (without quotes).

Examples
inputCopy
20 15 2 3
outputCopy
1
inputCopy
10 11 2 4
outputCopy
-1
Note
In the first test, one coin from each friend is enough, as he will be presented with 15 different coins and 13 of them will definitely be new.

In the second test, Ivan has 11 friends, but there are only 10 different coins. So all friends can’t present him different coins.

这题的意思是有n个人来为你庆祝生日，他们给你纪念币为礼物，其中，纪念币总共有m种，而你已经有了k种，要求是朋友们送给你的纪念币至少有l种是你没有的。另外，每个朋友给的硬币都是不一样的，但是个数是一样的，求每个朋友送的最少个数。一开始我的思路是枚举每个朋友的送的个数，看是否满足n*ans-l>k，但是在codeforces里做题，枚举这种做法一向是比较愚蠢的(我就很愚蠢)。所以，我们知道，需要的硬币数仅仅是至少k+L种，所以若(k+L) %m==0 ，则只需要(k+l)/m枚，若不为零，则再加一枚，若需要的已经大于所有n种，自然无法再分配

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{

	unsigned long long n,m,k,l,ans=0;
	cin>>n>>m>>k>>l;
	int flag=1;
	if(k+l>n||n<m)
		flag=1;
	else
		{	
			
			ans=(l+k)/m;
			flag=0;
	
			if((l+k)%m==0)
				ans=(l+k)/m;
			else
				ans++;
			if(ans*m>n)
				flag=1;			
		
		}
	if(flag)
		printf("-1n");
	else
		cout<<ans<<endl;
	return 0;
}