coreBugZJ

此 blog 已弃。

How many people have ipad II, ACM-DIY Group Contest 2011 Spring 之 8,HDOJ 3807

How many people have ipad II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)


Problem Description
hh found more and more of his friends are having ipad IIs (Lost , AC and so on). One day when they get together, hh asked his five friends, "How many of you have ipad II now?"

"One!"
"Three!"
"Everyone!"
"Four!"
"Two!"

hh's friends knew each other. They were clear about the "how many" question, while the answers are different, so there must be some people telling lies.

One of hh's friends told him(hh):
1.The number of people, who had ipad IIs, and lied, was no more than 1.
2.The number of people, who didn't have ipad IIs, and told the truth, was no more than 2.
3.At least one have ipad II.

Given the information, hh realized there may be one or two people having ipad IIs.

Now hh asks N people the "how many" question. These N friends answer one by one. Some tell the truth, some lie. What hh knows is:
1.The number of people, who have ipad IIs, and lie, is no more than A.
2.The number of people, who don't have ipad IIs, and tell the truth, is no more than B.
3.At least one have ipad II.

How many ipad IIs do these N people have?
 

Input
The input begins with an integer T(1<=T<=100).
The next T blocks each indicates a case.
The first line of each case contain a number N(1<=N<=20) then N positive integers follow, integers won't be lager than N.
Then following two numbers A , B(0 <= A,B <= N).
 

Output
Output the number of people have ipad II.
There may be many answers, output them by increasing order. (separated by space)
Output "impossible" if that's impossible.
 

Sample Input
3

5
1 2 3 4 5
1 2

3
1 1 1
1 1

5
4 4 5 5 3
1 1
 

Sample Output
1 2
impossible
1
 

Author
NotOnlySuccess
 

Source
ACM-DIY Group Contest 2011 Spring


枚举 有且说真话,有且说假话,无且说真话,无且说假话 的人数

感谢 cy 的思路

 1 #include <stdio.h>
 2 
 3 #define  L  30
 4 
 5 int a, b, n, lie[ L ], ans[ L ], nans;
 6 
 7 void solve() {
 8         int i, j, k, p, v, tot, tr, fa;
 9         nans = 0;
10         for ( i = 0; i <= n; ++i ) { /* have  true */
11                 for ( j = 0; j <= n-i; ++j ) { /* have false */
12                         for ( k = 0; k <= n-i-j; ++k ) { /* not have, true*/
13                                 p = n-i-j-k;  /* not have, false */
14                                 tot = i + j;
15                                 if ( (tot==0|| (j>a) || (k>b) ) {
16                                         continue;
17                                 }
18                                 tr = fa = 0;
19                                 for ( v = 0; v < n; ++v ) {
20                                         if ( lie[ v ] == tot ) {
21                                                 ++tr;
22                                         }
23                                         else {
24                                                 ++fa;
25                                         }
26                                 }
27                                 if ( (tr!=i+k) || (fa!=j+p) ) {
28                                         continue;
29                                 }
30                                 for ( v = 0; (v<nans)&&(ans[v]!=tot); ++v )
31                                         ;
32                                 if ( v >= nans ) {
33                                         ans[ nans++ ] = tot;
34                                 }
35                         }
36                 }
37         }
38         for ( i = 0; i < nans; ++i ) {
39                 for ( j = i+1; j < nans; ++j ) {
40                         if ( ans[ i ] > ans[ j ] ) {
41                                 int tmp = ans[ i ];
42                                 ans[ i ] = ans[ j ];
43                                 ans[ j ] = tmp;
44                         }
45                 }
46         }
47 }
48 
49 int main() {
50         int td, i;
51         scanf( "%d"&td );
52         while ( td-- > 0 ) {
53                 scanf( "%d"&n );
54                 for ( i = 0; i < n; ++i ) {
55                         scanf( "%d", lie+i );
56                 }
57                 scanf( "%d%d"&a, &b );
58                 solve();
59                 if ( nans > 0 ) {
60                         printf( "%d", ans[ 0 ] );
61                         for ( i = 1; i < nans; ++i ) {
62                                 printf( " %d", ans[ i ] );
63                         }
64                         printf( "\n" );
65                 }
66                 else {
67                         printf( "impossible\n" );
68                 }
69         }
70         return 0;
71 }
72 


posted on 2011-03-26 21:19 coreBugZJ 阅读(228) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理