# 2102: [Usaco2010 Dec]The Trough Game

## 2102: [Usaco2010 Dec]The Trough Game

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 117  Solved: 84

[Submit][Status]

## 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

1010

## Source

Silver

 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;
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
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
77                        if c1='1' then add(j,i);
78                   end;
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;
86 end.               

251 篇文章37 人订阅

0 条评论

## 相关文章

### HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

28960

### 1441: Min

1441: Min Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 320  Solved: 213 [Submi...

22140

239100

### 2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 1737...

26450

### HDU 1000 A + B Problem(指针版)

A + B Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

28340

8420

### HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

37760

### POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

33360

### 1257: [CQOI2007]余数之和sum

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2001  So...

29480

### UVALive 6933 Virus synthesis（回文树）

Viruses are usually bad for your health. How about ghting them with... other vir...

36570 