[UVA][bitmask暴搜] 565 - Pizza Anyone?＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-03-29 20:01:50| 人751| 回0 | 上一篇 | 下一篇

[UVA][bitmask暴搜] 565 - Pizza Anyone?

推 0 收藏 0 0 站台

Pizza Anyone?

You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?

The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:

Input Code	Topping
A	Anchovies
B	Black Olives
C	Canadian Bacon
D	Diced Garlic
E	Extra Cheese
F	Fresh Broccoli
G	Green Peppers
H	Ham
I	Italian Sausage
J	Jalapeno Peppers
K	Kielbasa
L	Lean Ground Beef
M	Mushrooms
N	Nonfat Feta Cheese
O	Onions
P	Pepperoni

Your friends provide you with a line of text that describes their pizza preferences. For example, the line

+O-H+P;

reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line

-E-I-D+A+J;

indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.

Input

The input consists of a series of pizza constraints.

A pizza constraint is a list of 1 to 12 topping constraint lists each on a line by itself followed by a period on a line by itself.

A topping constraint list is a series of topping requests terminated by a single semicolon.

An topping request is a sign character (+/-) and then an uppercase letter from A to P.

Output

For each pizza constraint, provide a description of a pizza that satisfies it. A description is the string ``Toppings: " in columns 1 through 10 and then a series of letters, in alphabetical order, listing the toppings on the pizza. So, a pizza with onion, anchovies, fresh broccoli and Canadian bacon would be described by:

Toppings: ACFO

If no combination toppings can be found which satisfies at least one request of every person, your program should print the string

No pizza can satisfy these requests.

on a line by itself starting in column 1.

Sample Input

+A+B+C+D-E-F-G-H; -A-B+C+D-E-F+G+H; -A+B-C+D-E+F-G+H; . +A+B+C+D; +E+F+F+H; +A+B-G; +O+J-F; +H+I+C; +P; +O+M+L; +M-L+P; . +A+B+C+D; +E+F+F+H; +A+B-G; +P-O; +O+J-F; +H+I+C; +P; +O; +O+M+L; -O-P; +M-L+P; .

Sample Output

Toppings: Toppings: CELP No pizza can satisfy these requests.

Miguel A. Revilla
1998-03-10

所有可能。

一下目意思：每材料可放或不放，因此 2^16 ，只要符合任一人至少一的要求。

//0.464 s

#include <stdio.h>
int main() {
    char s[105];
    int i, j;
    while(1) {
        int person[105][2] = {}, n = 0;
        while(gets(s) && s[0] != '.') {
            for(i = 0; s[i] != ';'; i += 2) {
                if(s[i] == '+')
                    person[n][0] |= 1<<(s[i+1]-'A');
                else
                    person[n][1] |= 1<<(s[i+1]-'A');
            }
            n++;
        }
        if(n == 0) break;
        int m = 1<<16;
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++) {
                if(i&person[j][0]) continue;
                if((m-1-i)&person[j][1]) continue;
                break;
            }
            if(j == n) {
                printf("Toppings: ");
                for(j = 0; j < 16; j++)
                    if((i>>j)&1)
                        putchar(j+'A');
                puts("");
                break;
            }
        }
        if(i == m)
            puts("No pizza can satisfy these requests.");
    }
    return 0;
}