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 0s 20584KB
comments (?)
stdin
copy 
27 8 28 35 33 30 14
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
https://ideone.com/PUNPli
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!