fork download
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <climits>
  4. #include <map>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <set>
  8. #include <stack>
  9. #include <deque>
  10. #include <vector>
  11. #include <stdlib.h>
  12. #include <string>
  13. #include <string.h>
  14. #include <utility>
  15. #include <queue>
  16. using namespace std;
  17. #define ll long long
  18. #define scl(n) scanf("%lld", &n)
  19. ll n, n1, n2, ar[50], p1[40000], p2[40000], v1=0, v2=0, k;
  20.  
  21. void solve1(ll i, ll x)
  22. {
  23. if(i>=n1 || x>=k)
  24. {
  25. p1[v1]=x;
  26. v1++;
  27. return;
  28. }
  29.  
  30. solve1(i+1, x);
  31. solve1(i+1, x+ar[i]);
  32. }
  33.  
  34. void solve2(ll i, ll x)
  35. {
  36. if(i>=n || x>=k)
  37. {
  38. p2[v2]=x;
  39. v2++;
  40. return;
  41. }
  42.  
  43. solve2(i+1, x);
  44. solve2(i+1, x+ar[i]);
  45. }
  46.  
  47. int main()
  48. {
  49. ll t, i, j, m, tmp, f, pkp, cs=0, ans, d;
  50. scl(t);
  51. while(t--)
  52. {
  53. f=v1=v2=ans=0;
  54. scl(n);
  55. scl(k);
  56. for(i=0; i<n; i++)
  57. scl(ar[i]);
  58. n1 = n/2;
  59. solve1(0, 0);
  60. solve2(n1, 0);
  61. sort(p2, p2+v2);
  62. sort(p1, p1+v1);
  63. for(i=0; i<v1; i++)
  64. {
  65. if(p1[i]>k)
  66. break;
  67. d = k-p1[i];
  68. pkp = upper_bound(p2, p2+v2, d)-p2;
  69. ans+=pkp;
  70. }
  71. printf("Case %lld: %lld\n", ++cs, ans);
  72. }
  73. return 0;
  74.  
  75.  
  76. }
  77.  
  78.  
  79.  
Success #stdin #stdout 0.01s 5280KB
stdin
100
4 9
4 0 6 8
1 20
4
1 4
0
1 16
9
2 2
8 6
2 16
8 6
3 11
3 4 6
3 10
4 2 9
4 5
5 6 4 6
1 12
1
1 2
7
2 20
8 9
3 13
6 5 8
2 18
2 2
4 5
3 7 9 2
3 14
0 3 0
4 6
3 0 7 7
5 19
6 7 9 4 9
4 12
8 4 9 0
4 5
6 1 4 7
1 12
3
1 6
5
5 3
8 6 0 7 5
1 15
4
3 11
4 0 1
5 7
0 6 4 5 4
3 10
2 2 0
3 19
7 2 4
3 13
2 4 0
3 15
6 3 6
2 18
8 7
4 5
0 9 0 5
5 8
6 8 0 8 7
1 9
9
5 1
3 8 4 5 7
1 2
0
3 20
8 7 7
4 13
7 3 4 4
5 3
2 7 4 0 4
5 19
5 0 0 0 8
2 17
5 7
5 18
6 9 5 3 8
2 18
7 4
3 4
3 6 5
3 1
5 8 4
2 6
6 8
1 5
5
4 12
4 3 8 0
5 7
5 2 7 5 9
2 8
2 6
4 6
0 5 6 8
2 31
3 7
4 25
1 8 4 2
5 2
2 4 3 8 1
6 10
6 6 8 5 0 6
1 28
6
6 26
6 6 0 1 3 5
3 21
3 6 0
8 2
3 3 8 3 6 5 9 3
4 10
8 5 8 9
7 17
6 3 3 3 3 4 8
1 31
5
4 31
5 2 9 0
8 32
4 4 6 5 7 1 4 7
7 19
8 2 9 5 6 4 0
2 13
8 2
6 6
7 9 1 0 1 1
10 9
5 3 1 0 2 2 7 2 9 1
1 22
2
6 12
6 5 9 7 6 3
3 20
0 3 2
3 5
6 2 1
2 6
2 4
3 13
3 4 5
5 29
7 9 4 6 5
2 22
4 7
1 19
9
2 15
3 5
1 32
7
2 12
7 5
30 650029462
217408763 243187990 354639749 18515748 450692028 384545018 163813104 380023777 32923709 501372049 243977421 238060199 519789310 179023900 486672075 52554799 379447256 487383440 80659103 516129002 359521149 96612579 519823472 495366011 165402836 231445900 360843152 203779179 479773520 486319198
28 876898394
288699577 455073848 256776460 293351429 304006504 220910390 425957011 503029366 100256762 409080462 248755239 488502135 418454878 253448188 38765105 113962418 75248904 412015181 347439781 514392640 93388288 82979437 285848769 185270622 295862499 141361985 535846416 178265820
22 9481143
176078771 470275186 121757683 392775586 333889083 524131440 355270626 522878073 282847823 285388783 35924889 206040839 113594727 398848708 88921713 94872036 515757738 201711113 307070612 314694615 318677246 78225358
11 583540236
63588176 16032900 25977677 501064727 361217893 31122231 97473088 410802818 426774673 273978375 277497320
20 700225015
186450035 474836962 375369335 199816589 477321780 268384752 299684987 165895010 396049325 178439069 488921564 423254812 186830996 434745966 492375928 341591837 1465048 49840299 74767220 451453921
29 183903597
106354663 514022636 161140113 33916850 158250960 292841019 193886037 487012984 237821245 471402423 273472161 430368339 36618589 218353287 363086797 62376181 208897183 398864122 331909845 156771933 494625866 102118672 296029616 98195670 407818077 53959088 168421020 316344325 370484644
4 516689148
243101297 120274403 90502029 208971957
10 1065992249
178983056 193697668 50583768 32792043 111069525 206459393 154271561 4330804 307265889 327152845
22 664601669
436525633 66881517 71741908 318878328 311613163 11360957 443897009 160407584 114877453 513950072 64136333 14064377 82340804 145644005 496761170 239890509 276830795 458152345 427020267 32098498 394960912 98465408
9 580155394
242971226 277115525 307451863 310037171 32521478 59583038 237408299 355363184 531271300
27 517575699
59140111 520887722 355540015 31455381 2300968 13874018 145355396 26807660 98388507 514855059 298132644 226469331 363357526 202003077 167813738 36019737 278485143 303423676 165466965 336955185 268111400 148165110 501753029 175428479 115443006 62999050 370788795
30 708886809
50261198 10233837 83548755 85206906 311859896 93689302 150853512 427908729 56309042 53525170 474323681 58511205 507655562 87334658 512951827 285475407 302381186 369193583 201472655 240083351 124905109 163552773 304665964 316532935 524753063 122288965 87469036 448001219 343051609 447263252
30 466784257
353473727 436189212 425507164 493947484 243871914 414804949 153257532 423616024 36367904 12436233 267562278 119061663 120131175 91318995 17690452 160500644 429261493 36215648 164747419 420511737 312179773 451055324 518268330 427923569 305575394 48127542 70838980 334816934 492467164 54109287
20 1019086073
363500363 95355380 446233970 236993961 123733314 53484050 310380065 17378550 24405790 445506992 391759097 91809730 138924932 41700645 165015105 108694399 382683790 11892442 154817186 465270373
15 774575140
64729090 374280169 387045826 244458269 49320042 256155966 418159113 273782365 468220549 183872105 106284013 503386908 414621182 535898743 256919356
27 678287320
401070752 491008180 52054906 153244701 157925085 110422764 449153770 113795801 85384028 441107994 162332975 111814293 218289025 140177199 346074684 248669213 474858077 200217569 491423181 297959527 22750363 349042536 518976192 125083667 210695970 362108571 441212894
21 512526544
333109583 12989102 25444817 366519423 365926533 142446856 210847362 480246747 452747029 179890837 498627733 429909448 36124441 377411371 64238439 526911683 51983489 374208657 441541470 355694114 474123638
4 934581594
319242608 523479336 119598895 503319485
7 539455092
4439069 221418901 513178144 238208018 258141600 58755537 119000745
15 717730038
242042249 122780185 503586780 510129939 203085631 248488348 197869672 356913767 292337945 456639264 193291331 268363191 82007976 495692477 246708667
stdout
Case 1: 8
Case 2: 2
Case 3: 2
Case 4: 2
Case 5: 1
Case 6: 4
Case 7: 7
Case 8: 5
Case 9: 3
Case 10: 2
Case 11: 1
Case 12: 4
Case 13: 6
Case 14: 4
Case 15: 4
Case 16: 8
Case 17: 4
Case 18: 19
Case 19: 10
Case 20: 4
Case 21: 2
Case 22: 2
Case 23: 2
Case 24: 2
Case 25: 8
Case 26: 10
Case 27: 8
Case 28: 8
Case 29: 8
Case 30: 8
Case 31: 4
Case 32: 8
Case 33: 10
Case 34: 2
Case 35: 1
Case 36: 2
Case 37: 7
Case 38: 12
Case 39: 4
Case 40: 32
Case 41: 4
Case 42: 21
Case 43: 4
Case 44: 2
Case 45: 1
Case 46: 2
Case 47: 2
Case 48: 14
Case 49: 7
Case 50: 4
Case 51: 6
Case 52: 4
Case 53: 16
Case 54: 3
Case 55: 12
Case 56: 2
Case 57: 64
Case 58: 8
Case 59: 1
Case 60: 5
Case 61: 83
Case 62: 2
Case 63: 16
Case 64: 247
Case 65: 80
Case 66: 4
Case 67: 16
Case 68: 181
Case 69: 2
Case 70: 16
Case 71: 8
Case 72: 4
Case 73: 4
Case 74: 8
Case 75: 31
Case 76: 4
Case 77: 2
Case 78: 4
Case 79: 2
Case 80: 4
Case 81: 2255
Case 82: 10719
Case 83: 1
Case 84: 189
Case 85: 718
Case 86: 37
Case 87: 13
Case 88: 845
Case 89: 6284
Case 90: 46
Case 91: 9143
Case 92: 36621
Case 93: 3675
Case 94: 40173
Case 95: 318
Case 96: 4678
Case 97: 421
Case 98: 10
Case 99: 43
Case 100: 230