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

Sample Output

1010

HINT

Source

Silver

题解:一上来居然没有别的想法——只有暴力。。。然后写了个纯粹的二进制穷举,然后,然后,然后,居然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.               

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

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

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

28960
来自专栏HansBug's Lab

1441: Min

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

22140
来自专栏函数式编程语言及工具

Cats(1)- 从Free开始,Free cats

  cats是scala的一个新的函数式编程工具库,其设计原理基本继承了scalaz:大家都是haskell typeclass的scala版实现。当然,cat...

239100
来自专栏HansBug's Lab

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
来自专栏Android中高级开发

Android开发之漫漫长途 X——Android序列化

该文章是一个系列文章,是本人在Android开发的漫漫长途上的一点感想和记录,我会尽量按照先易后难的顺序进行编写该系列。该系列引用了《Android开发艺术探索...

8420
来自专栏ml

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
来自专栏HansBug's Lab

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

扫码关注云+社区

领取腾讯云代金券