P3005 [USACO10DEC]槽的游戏The Trough Game

    • 52通过
    • 126提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2010 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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(1<=N<=20)个槽,并且他已经把其中的一些装上了食物。贝西以“在这个表里(表由贝西提供)有多少个槽里有食物?”的形式问了M(1<=M<=100)个问题。

    现在,贝西想知道,哪几个槽里有食物?

    这里有一个样例:

    (1)在第一个槽里有多少个槽里有食物?——1个

    (2)在第二个和第三个槽里有多少个槽里有食物?——1个

    (3)在第一个和第四个槽里有多少个槽里有食物?——1个

    (4)在第三个和第四个槽里有多少个槽里有食物?——1个

    从第一个问题可以知道,第一个槽是有食物的。

    从第二个问题可以知道,第四个槽是没有食物的。

    从第三个问题可以知道,第三个槽是有食物的。

    从第四个问题可以知道,第二个槽是没有食物的。

    输入输出格式

    输入格式:

    * 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.

    输出格式:

    * 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.

    输入输出样例

    输入样例#1: 复制
    4 4 
    1000 1 
    0110 1 
    1001 1 
    0011 1 
    
    输出样例#1: 复制
    1010 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。