The Right Tip (UVa Live Archive Europe - Southwestern - 2006/2007 Lisbon (Portugal))
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3647
問題
1,2,5,10,20,50,100,200円玉がある。硬貨を全て使ってK人に同じ金額を分配できるか。
K<=5
硬貨の枚数<10000
解法
人数分以上の5,50円玉を10,100円玉に両替して、どの人に5,50円玉を何枚配るかで全探索する。5,50円玉以外はグリーディーに分配してよい。
If you have 5 and 50 cents coins more than K, exchange 5 and 50 cents coins for 10 and 100 cents coins. Divide 5 and 50 cents coins with brute force. Divide the other coins with greedy.
コード
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h> #include <assert.h> #include <vector> using namespace std; typedef long long ll; static const double EPS = 1e-9; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define DEC(i, s) for (int i = (s); i >= 0; i--) #define SIZE(v) (int)((v).size()) #define MEMSET(v, h) memset((v), h, sizeof(v)) #define FIND(m, w) ((m).find(w) != (m).end()) int n, m; int coin[10][8]; const int price[8] = { 1, 2, 5, 10, 20, 50, 100, 200 }; bool calc(int depth, int fifty, int five) { if (depth == n) { return true; } FOREQ(i, 0, five) { FOREQ(j, 0, fifty) { int ndepth = depth + 1; memcpy(coin[ndepth], coin[depth], sizeof(coin[depth])); int sum = 5 * i + j * 50; for (int index = 7; index >= 0; index--) { int give = min(coin[ndepth][index], (m - sum) / price[index]); sum += price[index] * give; coin[ndepth][index] -= give; } if (sum != m) { continue; } if (calc(depth + 1, fifty - j, five - i)) { return true; } } } return false; } // It is wrong. //bool calc(int depth, int fifty, int five, int pfifty, int pfive) { // if (depth == n) { return true; } // FOREQ(i, pfive, five) { // if (i * (n - depth) > five) { break; } // FOREQ(j, pfifty, fifty) { // if (j * (n - depth) > fifty) { break; } // int ndepth = depth + 1; // memcpy(coin[ndepth], coin[depth], sizeof(coin[depth])); // int sum = 5 * i + j * 50; // for (int index = 7; index >= 0; index--) { // int give = min(coin[ndepth][index], (m - sum) / price[index]); // sum += price[index] * give; // coin[ndepth][index] -= give; // } // if (sum != m) { continue; } // if (calc(depth + 1, fifty - j, five - i, j, i)) { return true; } // } // } // return false; //} int main() { while (scanf("%d", &n), n != -1) { m = 0; REP(i, 8) { scanf("%d", &coin[0][i]); m += coin[0][i] * price[i]; } if (m % n != 0) { puts("no"); continue; } m /= n; int give = max(0, coin[0][5] - n); if (give == coin[0][5] - n && give % 2 == 1) { give++; } coin[0][6] += give / 2; int fifty = coin[0][5] - give; give = max(0, coin[0][2] - n); if (give == coin[0][2] - n && give % 2 == 1) { give++; } coin[0][3] += give / 2; int five = coin[0][2] - give; coin[0][5] = 0; coin[0][2] = 0; if (calc(0, fifty, five)) { puts("yes"); } else { puts("no"); } } }