fork(1) download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4.  
  5.  
  6. typedef unsigned long long R;
  7. typedef unsigned long long T;
  8.  
  9. #define __ctz __builtin_ctzll 
  10.  
  11. const int SIZE = 36;
  12. const int PART_SIZE = 18;
  13. const int MAX_STEP = 1000;
  14. int step = 0;
  15. int score[SIZE];
  16.  
  17.  
  18. T e = 1u;
  19.  
  20. R DP[SIZE][PART_SIZE+1][MAX_STEP];
  21.  
  22. void printMask(T mask){
  23. 	cout <<"@ ";
  24. 	for ( ; mask ; mask &= (mask - 1) )
  25. 		cout <<  __ctz(mask) + 1<<" ";
  26. 	cout << "\n";
  27. }
  28. void getSolution(int size, int part_size, R r_score, T mask ){
  29. 	if (!DP[size][part_size][r_score])
  30. 		return;
  31. 	if (size == 0){
  32. 		if (part_size > 0)
  33. 			mask |= 1;
  34. 		printMask(mask);
  35. 		return;
  36. 	}
  37. 	if(part_size > 0)
  38. 		getSolution(size-1, part_size-1, r_score - score[size], mask | (e << size) );
  39. 	getSolution(size-1, part_size, r_score, mask );
  40.  
  41. }
  42.  
  43. void generateCalc(){
  44. 	memset(DP, 0, sizeof(DP));
  45. 	DP[0][0][0] = 1;
  46. 	DP[0][1][score[0]] = 1;
  47. 	for (int i=1; i < SIZE; i++)
  48. 		for (int z=0; z <= PART_SIZE; z++)
  49. 			for (int j = MAX_STEP - score[i] - 1; j >=0; j--){
  50. 				if (z < PART_SIZE)
  51. 					DP[i][z+1][j + score[i] ] += DP[i-1][z][j];
  52. 				DP[i][z][j] += DP[i-1][z][j];
  53. 			}
  54. 	for (int i=0; i < MAX_STEP; i++){
  55. 		if (DP[SIZE-1][PART_SIZE][i])
  56. 			cout << "score " << 2*i - step <<" count " << DP[SIZE-1][PART_SIZE][i] << "\n";
  57. 		if (DP[SIZE-1][PART_SIZE][i] < 30)
  58. 			getSolution(SIZE-1,PART_SIZE,i,0);
  59. 	}
  60. 	cout << endl;
  61.  
  62. }
  63.  
  64.  
  65. int main() {
  66. 	// your code goes here
  67. 	int tmp;
  68. 	while (cin >> tmp){
  69. 		if (!tmp)
  70. 			continue;
  71. 		score[tmp-1]++;
  72. 		step++;
  73. 		cout << "#step " << step<<" "<<tmp<<endl;
  74. 		generateCalc();
  75. 	}
  76. 	return 0;
  77. }
Success #stdin #stdout 0.01s 20584KB
comments (?)
stdin
copy 
27 8 28 35 33 30 14 8 5 6 9 19 14 5 34 35
stdout
copy 
#step 1 27
score -1 count 4537567650
score 1 count 4537567650

#step 2 8
score -2 count 2203961430
score 0 count 4667212440
score 2 count 2203961430

#step 3 28
score -3 count 1037158320
score -1 count 3500409330
score 1 count 3500409330
score 3 count 1037158320

#step 4 35
score -4 count 471435600
score -2 count 2262890880
score 0 count 3606482340
score 2 count 2262890880
score 4 count 471435600

#step 5 33
score -5 count 206253075
score -3 count 1325912625
score -1 count 3005401950
score 1 count 3005401950
score 3 count 1325912625
score 5 count 206253075

#step 6 30
score -6 count 86493225
score -4 count 718559100
score -2 count 2181340125
score 0 count 3102350400
score 2 count 2181340125
score 4 count 718559100
score 6 count 86493225

#step 7 14
score -7 count 34597290
score -5 count 363271545
score -3 count 1425142215
score -1 count 2714556600
score 1 count 2714556600
score 3 count 1425142215
score 5 count 363271545
score 7 count 34597290

#step 8 8
score -8 count 34597290
score -6 count 311375610
score -4 count 1069854660
score -2 count 1958358690
score 0 count 2326762800
score 2 count 1958358690
score 4 count 1069854660
score 6 count 311375610
score 8 count 34597290

#step 9 5
score -9 count 13123110
score -7 count 150319260
score -5 count 660331035
score -3 count 1523427885
score -1 count 2190366360
score 1 count 2190366360
score 3 count 1523427885
score 5 count 660331035
score 7 count 150319260
score 9 count 13123110

#step 10 6
score -10 count 4686825
score -8 count 67490280
score -6 count 373497345
score -4 count 1077799320
score -2 count 1890829080
score 0 count 2246529600
score 2 count 1890829080
score 4 count 1077799320
score 6 count 373497345
score 8 count 67490280
score 10 count 4686825

#step 11 9
score -11 count 1562275
score -9 count 28120950
score -7 count 194347010
score -5 count 696803055
score -3 count 1495011960
score -1 count 2121722400
score 1 count 2121722400
score 3 count 1495011960
score 5 count 696803055
score 7 count 194347010
score 9 count 28120950
score 11 count 1562275

#step 12 19
score -12 count 480700
score -10 count 10815750
score -8 count 93015450
score -6 count 412680950
score -4 count 1083148200
score -2 count 1845363600
score 0 count 2184126000
score 2 count 1845363600
score 4 count 1083148200
score 6 count 412680950
score 8 count 93015450
score 10 count 10815750
score 12 count 480700

#step 13 14
score -13 count 480700
score -11 count 9734175
score -9 count 75710250
score -7 count 311349390
score -5 count 799026095
score -3 count 1433499840
score -1 count 1907767200
score 1 count 1907767200
score 3 count 1433499840
score 5 count 799026095
score 7 count 311349390
score 9 count 75710250
score 11 count 9734175
score 13 count 480700

#step 14 5
score -14 count 480700
score -12 count 8652600
score -10 count 60448025
score -8 count 232081960
score -6 count 592722765
score -4 count 1118510240
score -2 count 1615361760
score 0 count 1818619200
score 2 count 1615361760
score 4 count 1118510240
score 6 count 592722765
score 8 count 232081960
score 10 count 60448025
score 12 count 8652600
score 14 count 480700

#step 15 34
score -15 count 134596
score -13 count 3114936
score -11 count 27515268
score -9 count 129688053
score -7 count 390535101
score -5 count 844053264
score -3 count 1383814688
score -1 count 1758711744
score 1 count 1758711744
score 3 count 1383814688
score 5 count 844053264
score 7 count 390535101
score 9 count 129688053
score 11 count 27515268
score 13 count 3114936
score 15 count 134596

#step 16 35
score -16 count 134596
score -14 count 2768832
score -12 count 21977604
score -10 count 96755296
score -8 count 288141194
score -6 count 641865600
score -4 count 1109357712
score -2 count 1527164672
score 0 count 1698804288
score 2 count 1527164672
score 4 count 1109357712
score 6 count 641865600
score 8 count 288141194
score 10 count 96755296
score 12 count 21977604
score 14 count 2768832
score 16 count 134596
https://ideone.com/z9fxoC
language:
C++14 (gcc 8.3)
created:
4 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!