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");
    }
  }
}