1 | #include <stdio.h>
|
2 | #include <stdlib.h>
|
3 | #include <string.h>
|
4 |
|
5 | #define MAXPIECES 15
|
6 |
|
7 | struct info {
|
8 | int sum, maxp;
|
9 | } psetprops[1<<MAXPIECES];
|
10 |
|
11 | #define MAXHASHBITS 19
|
12 |
|
13 | int htable[1<<MAXHASHBITS];
|
14 | int hashbits, hashmask;
|
15 |
|
16 | int maxprime(int n) {
|
17 | static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
|
18 | int i, maxi = sizeof primes / sizeof *primes;
|
19 |
|
20 | for (i = 0; n > 1 && i < maxi; i++)
|
21 | while (n % primes[i] == 0)
|
22 | n /= primes[i];
|
23 | return i==0 || i==maxi ? n : primes[i-1];
|
24 | }
|
25 |
|
26 | int check(int x, int y, int pset) {
|
27 | int pset1 = pset & (pset - 1), subset, complset, tindex, maxp, sum, hash, res = 0;
|
28 |
|
29 | tindex = (x<y ? y*(y+1)/2+x : x*(x+1)/2+y) | (pset<<13);
|
30 | hash = (tindex ^ (tindex >> (26 - hashbits))) & hashmask;
|
31 | if (htable[hash] >> 1 == tindex)
|
32 | return htable[hash] & 0x1;
|
33 |
|
34 | maxp = psetprops[pset].maxp;
|
35 | if (maxp <= x || maxp <= y) {
|
36 | if (pset1)
|
37 | for (subset = (~pset1 + 1) & pset1; subset; subset = ((subset | ~pset1) + 1) & pset1) {
|
38 | complset = pset ^ subset;
|
39 | sum = psetprops[subset].sum;
|
40 | if (sum % x == 0 && check(x, sum / x, subset) && check(x, y - sum / x, complset)) {
|
41 | res = 1;
|
42 | break;
|
43 | }
|
44 | if (y != x && sum % y == 0 && check(sum / y, y, subset) && check(x - sum / y, y, complset)) {
|
45 | res = 1;
|
46 | break;
|
47 | }
|
48 | }
|
49 | else
|
50 | res = 1;
|
51 | }
|
52 | htable[hash] = tindex << 1 | res;
|
53 | return res;
|
54 | }
|
55 |
|
56 | int compare(const void *a, const void *b) {
|
57 | return *(int *)a > *(int *)b;
|
58 | }
|
59 |
|
60 | int main(int argc, char *argv[]) {
|
61 | static int pieces[MAXPIECES];
|
62 | int caseno, i, j, k, n, x, y, maxp, res;
|
63 |
|
64 | for (caseno = 1; ; caseno++) {
|
65 | scanf("%d", &n);
|
66 | if (n==0)
|
67 | break;
|
68 | scanf("%d %d", &x, &y);
|
69 | if(x<0 || x>100 || y<0 ||y>100) while(1);
|
70 | memset(psetprops, 0, (1<<n) * sizeof *psetprops);
|
71 | for (i = 0; i < n; i++)
|
72 | scanf("%d", &pieces[i]);
|
73 |
|
74 | qsort(pieces, n, sizeof *pieces, compare);
|
75 |
|
76 | for (i = 0; i < n; i++) {
|
77 | maxp = maxprime(pieces[i]);
|
78 | for (j = 1<<i; j < 1<<n; j += 2<<i)
|
79 | for (k = 0; k < 1<<i; k++) {
|
80 | psetprops[j+k].sum += pieces[i];
|
81 | if (maxp > psetprops[j+k].maxp)
|
82 | psetprops[j+k].maxp = maxp;
|
83 | }
|
84 | }
|
85 | if (psetprops[(1<<n)-1].sum != x*y)
|
86 | res = 0;
|
87 | else {
|
88 | hashbits = n + (MAXHASHBITS - MAXPIECES);;
|
89 | hashmask = (1 << hashbits) - 1;
|
90 | memset(htable, 0, (1<<hashbits) * sizeof (int));
|
91 | res = check(x, y, (1<<n)-1);
|
92 | }
|
93 | printf("Case %d: %s\n", caseno, res ? "Yes" : "No");
|
94 | }
|
95 | return 0;
|
96 | }
|