fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <algorithm>
  6. using namespace std;
  7. #define re(i, n) for (int i=0; i<n; i++)
  8. #define re1(i, n) for (int i=1; i<=n; i++)
  9. #define re2(i, l, r) for (int i=l; i<r; i++)
  10. #define re3(i, l, r) for (int i=l; i<=r; i++)
  11. #define rre(i, n) for (int i=n-1; i>=0; i--)
  12. #define rre1(i, n) for (int i=n; i>0; i--)
  13. #define rre2(i, r, l) for (int i=r-1; i>=l; i--)
  14. #define rre3(i, r, l) for (int i=r; i>=l; i--)
  15. const int M = 101, S = 1024, MAXN = 11, INF = ~0U >> 2;
  16. struct sss {
  17.     int v, sum;
  18. 	bool operator< (sss s0) const {
  19. 		if (sum < s0.sum) return 1; else if (sum > s0.sum) return 0; else return v < s0.v;
  20. 	}
  21. } V0[S];
  22. bool F[M][S];
  23. int n, A[MAXN], res;
  24. void prepare()
  25. {
  26. 	int i0, KK, tmp;
  27. 	re2(i, 1, M) {
  28. 		i0 = i; KK = 0; while (i0) {tmp = 1 << (i0 % 10); if (KK & tmp) {KK = -1; break;} else KK |= tmp; i0 /= 10;} if (KK >= 0) F[i][KK] = 1;
  29. 		for (int j=1; j+j<=i; j++) {
  30. 			KK = 0; i0 = j; while (i0) {tmp = 1 << (i0 % 10); if (KK & tmp) {KK = -1; break;} else KK |= tmp; i0 /= 10;}
  31. 			if (KK >= 0) {
  32. 				i0 = i - j; while (i0) {tmp = 1 << (i0 % 10); if (KK & tmp) {KK = -1; break;} else KK |= tmp; i0 /= 10;}
  33. 				if (KK >= 0) F[i][KK] = 1;
  34. 			}
  35. 		}
  36. 		re(j, S) if (F[i][j]) {
  37. 			re(k, 10) F[i][j | (1 << k)] = 1;
  38. 		}
  39. 	}
  40. 	re(i, S) {
  41. 		KK = 0; re(j, 10) if (i & (1 << j)) KK++;
  42. 		V0[i].v = i; V0[i].sum = KK;
  43. 	}
  44. 	sort(V0, V0 + S);
  45. }
  46. void solve()
  47. {
  48. 	bool FF; int x;
  49. 	re(i, S) {
  50. 		x = V0[i].v; FF = 1; re(j, n) if (!F[A[j]][x]) {FF = 0; break;}
  51. 		if (FF) {res = x; break;}
  52. 	}
  53. }
  54. int main()
  55. {
  56. 	int testno = 0; prepare();
  57. 	while (1) {
  58. 		scanf("%d", &n); if (!n) break; else testno++;
  59. 		re(i, n) scanf("%d", &A[i]);
  60. 		solve();
  61. 		printf("Case %d: ", testno); rre(i, 10) if (res & (1 << i)) printf("%d", i); puts("");
  62. 	}
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 2796KB
comments (?)
stdin
copy 
2 10 11
1 30
0
stdout
copy 
Case 1: 654
Case 2: 30
https://ideone.com/ghNhcX
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!