[UVA] 1163 - The Right Tip＠Morris' Blog｜PChome Online 個人新聞台

2013-10-08 10:06:01| 人氣1,169| 回應0 | 上一篇 | 下一篇

[UVA] 1163 - The Right Tip

推薦 0 收藏 0 轉貼0 訂閱站台

The Right Tip

During the recent Football Worldcup, a group of friends worked at a courtyard café to pay for their holidays. Everyday they would collect all the tips given by the customers on a jar, and at the end of the day they wanted to split the tips equally between them. After a few days, they reached the conclusion that (given the various face values of euro coins) sometimes it was not possible to equally split the collect of the day between them.

Write a program to help the friends determine if it is possible (or not) to equally split the collect of the day between them.

Input

The input will consist of a sequence of pairs of lines, each pair represents a coin division problem to be solved. For each such pair the first line contains the number of friends (a positive integer not greater than 5). The second line contains eight space separated non-negative integers n₁, n₂,..., n₈, where n_i is the number of coins of value i (0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1.00 and 2.00 euros respectively, e.g., the number of 5 cents coins will be denoted by n₃). The maximum number of coins is 10000. Input is terminated by a single line with the number -1.

Output

For each coin division problem print either "yes" or "no", depending on whether it is possible or not to divide equally the tips by the friends.

Sample Input

1 1 1 1 1 1 1 1

2 1 2 1 5 2 2 1

3423 234 324 972 740 12 234 901

147 5502 3486 434 76 66 267 20

3015 3590 1559 1219 78 507 23 8

-1

Sample Output

yes

題目描述：

將有限個數幣值為 1,2,5,10,20,50,100,200 均分給 n < 6 個人。
硬幣總個數不超過 10000 個。

題目解法：

首先，簡易 Greedy 過不了，DP 狀態來說也要 []^5，至於 [] 想必也是太大無法運行。
即使將無用狀態篩掉 ... 還是甭想這個了。
再者思考一個問題，假如幣值相鄰恰好是一個倍數的話，即 coin[i] = coin[i-1]*k。
可以使用 greedy 依序對每個人挑出來吧？這很難證明，只能靠日常生活的經驗猜測。
相信國幣 1,5,10,50,100,500,1000,2000 可以對每個人都均分！
在這麼猜測下，發現題目去除掉 5 和 50 這兩種之後便符合剛剛的要求了。
因此打算將 5 兌換成 10，50 兌換成 100，非偶數怎麼辦？
沒錯，窮舉看看每一個人是否要拿 1 枚，因此要窮舉 (2^n)*(2^n)。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int coins[8] = {1,2,5,10,20,50,100,200};
int check(int pay[], int n, int items[]) {
    if(items[2]%2 || items[5]%2)
        return 0;
    items[3] += items[2]/2, items[2] = 0;
    items[6] += items[5]/2, items[5] = 0;
    int i, j, k;
    for(i = 0; i < n; i++) {
        for(j = 7; j >= 0; j--) {
            k = min(items[j], pay[i]/coins[j]);
            items[j] -= k;
            pay[i] -= k*coins[j];
        }
        if(pay[i])    return 0;
    }
    return 1;
}
int main() {
    int i, j, k;
    int n, items[8];
    while(scanf("%d", &n) == 1 && n > 0) {
        int sum = 0;
        for(i = 0; i < 8; i++) {
            scanf("%d", &items[i]);
            sum += items[i]*coins[i];
        }
        if(sum%n) {
            puts("no");
            continue;
        }
        sum /= n;
        int ret = 0;
        for(i = (1<<n)-1; i >= 0; i--) {
            for(j = (1<<n)-1; j >= 0; j--) {
                int t[8], pay[8];
                memcpy(t, items, sizeof(items));
                for(k = 0; k < n; k++)
                    pay[k] = sum;
                for(k = 0; k < n; k++) {
                    if((i>>k)&1) {
                        if(t[2] && pay[k]-coins[2] >= 0) {
                            pay[k] -= coins[2];
                            t[2]--;
                        }
                    }
                    if((j>>k)&1) {
                        if(t[5] && pay[k]-coins[5] >= 0) {
                            pay[k] -= coins[5];
                            t[5]--;
                        }
                    }
                }
                ret |= check(pay, n, t);
                if(ret)    i = j = -1;
            }
        }
        puts(ret ? "yes" : "no");
    }
    return 0;
}

我要檢舉

#1163#The Right Tip

台長： Morris

您可能對以下文章有興趣

[UVA] 234 - Switching Channels

[UVA] 394 - Mapmaker

[UVA][Greedy] 12405 - Scarecrow

[UVA] 1189 - Find The Multiple

人氣(1,169) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][dfs] 845 - Gas Station Numbers
此分類上一篇:[UVA] 12586 - Overlapping Characters

回應(0)