2102: [Usaco2010 Dec]The Trough Game
2102: [Usaco2010 Dec]The Trough Game
2102: [Usaco2010 Dec]The Trough Game
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 117 Solved: 84
Description
Farmer John and Bessie are playing games again. This one has to do with troughs of water. Farmer John has hidden N (1 <= N <= 20) troughs behind the barn, and has filled some of them with food. Bessie has asked M (1 <= M <= 100) questions of the form, "How many troughs from this list (which she recites) are filled?". Bessie needs your help to deduce which troughs are actually filled. Consider an example with four troughs where Bessie has asked these questions (and received the indicated answers): 1) "How many of these troughs are filled: trough 1" --> 1 trough is filled 2) "How many of these troughs are filled: troughs 2 and 3" --> 1 trough is filled 3) "How many of these troughs are filled: troughs 1 and 4" --> 1 trough is filled 4) "How many of these troughs are filled: troughs 3 and 4" --> 1 trough is filled From question 1, we know trough 1 is filled. From question 3, we then know trough 4 is empty. From question 4, we then know that trough 3 is filled. From question 2, we then know that trough 2 is empty. 求N位二进制数X，使得给定的M个数，满足X and Bi=Ci ,Bi ci分别是读入的两个数
Input
* Line 1: Two space-separated integers: N and M * Lines 2..M+1: A subset of troughs, specified as a sequence of contiguous N 0's and 1's, followed by a single integer that is the number of troughs in the specified subset that are filled.
Output
* Line 1: A single line with: * The string "IMPOSSIBLE" if there is no possible set of filled troughs compatible with Farmer John's answers. * The string "NOT UNIQUE" if Bessie cannot determine from the given data exactly what troughs are filled. * Otherwise, a sequence of contiguous N 0's and 1's specifying which troughs are filled.
Sample Input
4 4 1000 1 0110 1 1001 1 0011 1
Sample Output
1010
HINT
Source
题解：一上来居然没有别的想法——只有暴力。。。然后写了个纯粹的二进制穷举，然后，然后，然后，居然AC了？！？！44ms也是醉大了= =
1 type
2 point=^node;
3 node=record
4 g:longint;
5 next:point;
6 end;
7 var
8 i,j,k,l,m,n,t:longint;
9 a:array[0..10000] of point;
10 b,c,d:array[0..10000] of longint;
11 c1,c2:char;
12 procedure add(x,y:longint);inline;
13 var p:point;
14 begin
15 new(p);p^.g:=y;
16 p^.next:=a[x];a[x]:=p;
17 end;
18 procedure dfs(x:longint);inline;
19 var i,j,k,l:longint;p:point;
20 begin
21 if x>n then
22 begin
23 for i:=1 to m do if b[i]>0 then exit;
24 if t=0 then
25 begin
26 for i:=1 to n do d[i]:=c[i];
27 t:=1;
28 end
29 else
30 begin
31 writeln('NOT UNIQUE');
32 halt;
33 end;
34 end
35 else
36 begin
37 p:=a[x];l:=0;
38 while p<>nil do
39 begin
40 if b[p^.g]=0 then
41 begin
42 l:=1;
43 break;
44 end;
45 p:=p^.next;
46 end;
47 if l=0 then
48 begin
49 p:=a[x];
50 while p<>nil do
51 begin
52 dec(b[p^.g]);
53 p:=p^.next;
54 end;
55 c[x]:=1;
56 dfs(x+1);
57 p:=a[x];
58 while p<>nil do
59 begin
60 inc(b[p^.g]);
61 p:=p^.next;
62 end;
63 end;
64 c[x]:=0;
65 dfs(x+1);
66 end;
67 end;
68
69 begin
70 readln(n,m);
71 for i:=1 to m do a[i]:=nil;
72 for i:=1 to m do
73 begin
74 for j:=1 to n do
75 begin
76 read(c1);
77 if c1='1' then add(j,i);
78 end;
79 readln(b[i]);
80 end;
81 t:=0;
82 dfs(1);
83 IF t=0 then write('IMPOSSIBLE') else for i:=1 to n do write(d[i]);
84 writeln;
85 readln;
86 end.