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