fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. const int marbValues[] = {1, 2, 3, 4, 5, 6, 10, 100, 200, 1000};
  9. const int MC = 10;
  10.  
  11. void changeMarbleCount(int marblesCount[]){
  12.     int count;
  13. 	count = 2*(marblesCount[0]/4-1);
  14. 	marblesCount[1] += count; //constructing 2 based on 1
  15. 	marblesCount[0] %= 4;
  16. 	if(count >= 2 && marblesCount[0]==0){
  17. 		marblesCount[1] -= 2;
  18. 		marblesCount[0] += 4;
  19. 	}
  20.  
  21. 	marblesCount[3] += 2*(marblesCount[1]/4); //constructing 4 based on 2
  22. 	marblesCount[1] %= 4;
  23.  
  24. 	marblesCount[5] += 2*(marblesCount[2]/4); //constructing 6 based on 3
  25. 	marblesCount[2] %= 4;
  26.  
  27. 	marblesCount[5] += 10*(marblesCount[4]/12); //constructing 6 based on 5
  28. 	marblesCount[4] %= 12;
  29.  
  30. 	marblesCount[5] += 4*(marblesCount[3]/6); //constructing 6 based on 4
  31. 	marblesCount[3] %= 6;
  32.  
  33. 	marblesCount[6] = 12*(marblesCount[5]/20); //constructing 10 based on 6
  34. 	marblesCount[5] %= 20;
  35.  
  36. 	marblesCount[7] = 2*(marblesCount[6]/20); //constructing 100 based on 10
  37. 	marblesCount[6] %= 20;
  38.  
  39. 	marblesCount[8] = 2*(marblesCount[7]/4); //constructing 200 based on 100
  40. 	marblesCount[7] %= 4;
  41.  
  42. 	marblesCount[9] = 2*(marblesCount[8]/10); //constructing 1000 based on 200
  43. 	marblesCount[8] %= 10;
  44. }
  45.  
  46. int main(){
  47. #ifndef ONLINE_JUDGE
  48. 	freopen("C:\\acm_inp\\divup.in", "r", stdin);
  49. 	freopen("C:\\acm_inp\\divup.out", "w", stdout);
  50. #endif
  51. 	int marblesCount[MC], I, J, K, tsum, sum, nextVal, caseNum=1;
  52. 	int gotValue[420000];
  53.  
  54. 	while(true){
  55. 		sum = 0;
  56. 		for(I=0; I<6; I++){
  57. 			scanf("%d", &marblesCount[I]);
  58. 			sum += marblesCount[I]*marbValues[I];
  59. 		}
  60. 		if(sum == 0)
  61. 			break;
  62.  
  63. 		if(caseNum==92)
  64. 			caseNum = 92;
  65.  
  66. 		changeMarbleCount(marblesCount);
  67. 		sum = 0;
  68. 		for(I=0; I<MC; I++)
  69. 			sum += marbValues[I]*marblesCount[I];
  70. 		tsum = sum;
  71. 		sum /=2 ;
  72. 		tsum -= sum;
  73. 		if(sum==tsum){
  74. 			memset(gotValue, 0, sizeof(gotValue));
  75. 			for(I=0; I<MC; I++){
  76. 				J = marblesCount[I];
  77. 				while(J>0){
  78. 					for(K = sum; K>=1; K--)
  79. 						if(K >= marbValues[I])
  80. 							gotValue[K] = max(gotValue[K], marbValues[I]+gotValue[K-marbValues[I]]);
  81. 					J --;
  82. 				}
  83. 			}
  84. 		}
  85. 		if(sum==tsum && gotValue[sum]==tsum)
  86. 			printf("Collection #%d:\nCan be divided.\n\n", caseNum++);
  87. 		else
  88. 			printf("Collection #%d:\nCan't be divided.\n\n", caseNum++);
  89. 	}
  90.  
  91.  
  92. 	return 0;
  93. }
  94.  
  95.  
  96.  
Success #stdin #stdout 0.23s 4416KB
comments (?)
stdin
copy 
710 745 731 702 701 736
929 953 943 1000 987 921
280 258 285 266 272 255
911 902 884 972 899 900
1180 1223 1215 1243 1199 1128
438 510 465 437 451 471
2825 2926 2840 2788 2923 2897
1039 1058 1111 1046 1013 1024
430 410 399 396 350 394
2305 2282 2323 2418 2361 2366
1300 1247 1288 1277 1208 1294
1845 1858 1891 1948 1876 1795
2829 2941 2871 2832 2837 2782
2822 2802 2803 2766 2744 2645
2453 2347 2383 2486 2331 2416
2386 2437 2338 2375 2371 2467
1176 1118 1097 1121 1071 1191
781 788 754 723 760 680
3113 3118 3114 3140 3229 3149
727 719 736 770 727 776
225 234 241 187 217 171
3120 3049 3077 3066 3072 3094
3225 2954 3072 3054 3049 3169
268 272 254 280 273 238
1786 1741 1767 1764 1803 1839
82 55 70 73 64 87
758 750 786 780 769 785
2121 2162 2180 2138 2221 2259
1451 1391 1426 1437 1471 1450
1440 1383 1377 1450 1479 1501
1071 1029 1069 1009 975 990
488 513 512 484 517 534
2890 2881 2928 2938 2984 2950
771 730 702 768 760 721
1817 1821 1887 1919 1922 1815
254 244 254 246 243 260
1103 1113 1063 1075 1045 1049
3055 3056 2967 3025 2995 2986
2949 3019 2990 2891 2894 2961
2774 2798 2816 2741 2718 2697
2809 2796 2638 2656 2752 2870
3023 3147 3109 3127 3178 3066
2309 2332 2333 2372 2261 2224
2165 2143 2058 2200 2188 2209
598 555 583 590 584 627
2346 2267 2348 2377 2342 2208
206 201 206 186 203 202
1516 1504 1484 1488 1490 1495
2918 2830 2811 2928 2901 2824
486 536 486 503 542 513
743 771 683 711 753 729
1400 1434 1461 1356 1374 1333
1697 1792 1747 1783 1687 1697
2435 2500 2465 2434 2551 2417
2100 2171 2167 2103 2131 2109
335 353 316 349 347 318
2724 2898 2850 2791 2840 2812
295 286 241 304 265 272
1320 1318 1297 1381 1314 1284
3310 3149 3321 3329 3193 3174
2766 2714 2767 2735 2768 2695
2344 2311 2350 2361 2359 2363
1282 1286 1186 1301 1231 1270
928 995 917 936 962 929
2291 2277 2326 2266 2189 2325
3301 3182 3161 3294 3310 3399
958 935 949 953 934 911
1719 1749 1677 1706 1693 1792
1836 1841 1786 1795 1844 1779
1778 1859 1768 1852 1758 1784
2659 2590 2610 2625 2681 2636
2342 2427 2334 2517 2354 2425
1063 1143 1031 1066 1065 1021
639 676 646 693 674 672
3345 3286 3336 3277 3221 3331
2046 2163 2104 2112 2047 2230
1629 1606 1599 1572 1627 1646
1680 1728 1677 1690 1741 1740
2369 2485 2493 2507 2448 2450
1090 1159 1017 1049 1082 1111
397 332 360 358 364 384
3113 3210 3179 3079 3161 3138
234 257 258 253 260 235
3264 3299 3225 3258 3339 3156
2712 2656 2647 2718 2716 2679
295 309 276 298 270 269
1808 1888 1818 1821 1868 1856
2143 2311 2138 2059 2071 2135
784 785 851 763 835 782
2764 2784 2780 2752 2738 2746
112 115 116 110 108 121
1176 1196 1216 1215 1152 1233
2862 2856 2927 2850 2724 2825
1489 1397 1436 1473 1398 1380
339 345 376 330 361 370
997 988 991 969 1013 1052
1467 1372 1415 1439 1434 1345
335 303 317 309 324 324
492 510 491 493 498 509
2836 2824 2888 2971 2862 2821
0 0 0 0 0 0
stdout
copy 
Collection #1:
Can be divided.

Collection #2:
Can't be divided.

Collection #3:
Can't be divided.

Collection #4:
Can be divided.

Collection #5:
Can be divided.

Collection #6:
Can be divided.

Collection #7:
Can be divided.

Collection #8:
Can't be divided.

Collection #9:
Can't be divided.

Collection #10:
Can't be divided.

Collection #11:
Can be divided.

Collection #12:
Can be divided.

Collection #13:
Can't be divided.

Collection #14:
Can't be divided.

Collection #15:
Can't be divided.

Collection #16:
Can't be divided.

Collection #17:
Can be divided.

Collection #18:
Can't be divided.

Collection #19:
Can be divided.

Collection #20:
Can be divided.

Collection #21:
Can't be divided.

Collection #22:
Can't be divided.

Collection #23:
Can be divided.

Collection #24:
Can't be divided.

Collection #25:
Can be divided.

Collection #26:
Can be divided.

Collection #27:
Can't be divided.

Collection #28:
Can be divided.

Collection #29:
Can be divided.

Collection #30:
Can be divided.

Collection #31:
Can't be divided.

Collection #32:
Can't be divided.

Collection #33:
Can be divided.

Collection #34:
Can't be divided.

Collection #35:
Can be divided.

Collection #36:
Can't be divided.

Collection #37:
Can't be divided.

Collection #38:
Can't be divided.

Collection #39:
Can't be divided.

Collection #40:
Can be divided.

Collection #41:
Can't be divided.

Collection #42:
Can be divided.

Collection #43:
Can't be divided.

Collection #44:
Can't be divided.

Collection #45:
Can't be divided.

Collection #46:
Can be divided.

Collection #47:
Can't be divided.

Collection #48:
Can be divided.

Collection #49:
Can be divided.

Collection #50:
Can be divided.

Collection #51:
Can't be divided.

Collection #52:
Can't be divided.

Collection #53:
Can't be divided.

Collection #54:
Can't be divided.

Collection #55:
Can be divided.

Collection #56:
Can be divided.

Collection #57:
Can be divided.

Collection #58:
Can't be divided.

Collection #59:
Can't be divided.

Collection #60:
Can be divided.

Collection #61:
Can't be divided.

Collection #62:
Can't be divided.

Collection #63:
Can't be divided.

Collection #64:
Can't be divided.

Collection #65:
Can be divided.

Collection #66:
Can be divided.

Collection #67:
Can't be divided.

Collection #68:
Can't be divided.

Collection #69:
Can be divided.

Collection #70:
Can be divided.

Collection #71:
Can be divided.

Collection #72:
Can be divided.

Collection #73:
Can't be divided.

Collection #74:
Can't be divided.

Collection #75:
Can be divided.

Collection #76:
Can't be divided.

Collection #77:
Can't be divided.

Collection #78:
Can be divided.

Collection #79:
Can be divided.

Collection #80:
Can't be divided.

Collection #81:
Can't be divided.

Collection #82:
Can't be divided.

Collection #83:
Can be divided.

Collection #84:
Can be divided.

Collection #85:
Can't be divided.

Collection #86:
Can't be divided.

Collection #87:
Can be divided.

Collection #88:
Can be divided.

Collection #89:
Can be divided.

Collection #90:
Can be divided.

Collection #91:
Can be divided.

Collection #92:
Can be divided.

Collection #93:
Can't be divided.

Collection #94:
Can't be divided.

Collection #95:
Can be divided.

Collection #96:
Can't be divided.

Collection #97:
Can be divided.

Collection #98:
Can be divided.

Collection #99:
Can't be divided.

Collection #100:
Can be divided.
https://ideone.com/xfOr9v
language:
C++ (gcc 8.3)
created:
11 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!