51nod 1246 항아리 와 동전

n 개의 항아리 가 있 고 k 개의 동전 이 있 으 며 항아리 마다 임의의 동전 을 수용 할 수 있다.항 아 리 는 투명 하지 않 으 니, 너 는 이 k 개의 동전 을 항아리 안에 임의로 분배 할 수 있다.그리고 항아리 가 순 서 를 어 지 럽 히 면 겉 으로 는 항 아 리 를 구별 할 수 없다.마지막 항 아 리 는 번호 1 - n 으로 묶 였 다.매번 어떤 항아리 에 동전 이 들 어 있 으 면 1 개 (하지만 이 항아리 에 동전 이 얼마나 있 는 지 는 모 르 지만) 를 얻 을 수 있다. 이 항아리 가 비어 있 으 면 어떤 동전 도 얻 지 못 하지만 물 어 볼 기 회 는 1 회 소모 된다.당신 은 최종 적 으로 적어도 c 개의 동전 (c < = k) 을 받 아야 합 니 다. 문 제 는 n, k, c 를 정 하 는 것 입 니 다. 당신 이 분배 방식 을 선택 하여 최 악의 상황 에서 질문 하 는 횟수 가 가장 적 고 이 최소 의 횟수 를 구 하 는 것 입 니 다.
예 를 들 어 항아리 3 개, 동전 10 개, 동전 7 개 를 받 아야 합 니 다. (n = 3, k = 10, c = 6)
동전 을 334 로 나 누 어 항아리 마다 2 번 물 어보 면 동전 6 개 를 얻 을 수 있 고 항아리 하나 에 물 어보 면 동전 7 개 를 얻 을 수 있다.
Input
  3  :n,k,c (1 <= n <= 10^9, 1 <= c <= k <= 10^9)。

Output

입력 예제
4 2 2

출력 예제
4
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
using namespace std;
#define esp  1e-8
const double PI = acos(-1.0);
const double e = 2.718281828459;
const int inf = 2147483647;
const long long mod = 1000000007;
//freopen("in.txt","r",stdin); //     ,      in.txt     
//freopen("out.txt","w",stdout); //     ,        out.txt   cin
int main()
{
	int n, k, c, i, j;
	while (~scanf("%d%d%d", &n, &k, &c))
	{
		int x = k / n;
		int y = n - k % n;
		if (x * n >= c || k % n == 0)
			printf("%d
", c); else { int z = k / (x + 1); z = n - z + c; //cout << z << endl; printf("%d
", min(z, c + y)); } } }

좋은 웹페이지 즐겨찾기