#include <iostream> #include <string.h> using namespace std; typedef unsigned long long R; typedef unsigned long long T; #define __ctz __builtin_ctzll const int SIZE = 36; const int PART_SIZE = 18; const int MAX_STEP = 1000; int step = 0; int score[SIZE]; T e = 1u; R DP[SIZE][PART_SIZE+1][MAX_STEP]; void printMask(T mask){ cout <<"@ "; for ( ; mask ; mask &= (mask - 1) ) cout << __ctz(mask) + 1<<" "; cout << "\n"; } void getSolution(int size, int part_size, R r_score, T mask ){ if (!DP[size][part_size][r_score]) return; if (size == 0){ if (part_size > 0) mask |= 1; printMask(mask); return; } if(part_size > 0) getSolution(size-1, part_size-1, r_score - score[size], mask | (e << size) ); getSolution(size-1, part_size, r_score, mask ); } void generateCalc(){ memset(DP, 0, sizeof(DP)); DP[0][0][0] = 1; DP[0][1][score[0]] = 1; for (int i=1; i < SIZE; i++) for (int z=0; z <= PART_SIZE; z++) for (int j = MAX_STEP - score[i] - 1; j >=0; j--){ if (z < PART_SIZE) DP[i][z+1][j + score[i] ] += DP[i-1][z][j]; DP[i][z][j] += DP[i-1][z][j]; } for (int i=0; i < MAX_STEP; i++){ if (DP[SIZE-1][PART_SIZE][i]) cout << "score " << 2*i - step <<" count " << DP[SIZE-1][PART_SIZE][i] << "\n"; if (DP[SIZE-1][PART_SIZE][i] < 30) getSolution(SIZE-1,PART_SIZE,i,0); } cout << endl; } int main() { // your code goes here int tmp; while (cin >> tmp){ if (!tmp) continue; score[tmp-1]++; step++; cout << "#step " << step<<" "<<tmp<<endl; generateCalc(); } return 0; }
27 8 28 35 33 30 14 8 5 6 9 19 14 5 34 35 10 35 33 26
#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 #step 17 10 score -17 count 33649 score -15 count 908523 score -13 count 9229440 score -11 count 50012028 score -9 count 175042098 score -7 count 445205112 score -5 count 868658112 score -3 count 1336150224 score -1 count 1652328464 score 1 count 1652328464 score 3 count 1336150224 score 5 count 868658112 score 7 count 445205112 score 9 count 175042098 score 11 count 50012028 score 13 count 9229440 score 15 count 908523 score 17 count 33649 #step 18 35 score -18 count 33649 score -16 count 908523 score -14 count 9128493 score -12 count 47906562 score -10 count 158861736 score -8 count 381709449 score -6 count 716660772 score -4 count 1089299412 score -2 count 1384022700 score 0 count 1498072708 score 2 count 1384022700 score 4 count 1089299412 score 6 count 716660772 score 8 count 381709449 score 10 count 158861736 score 12 count 47906562 score 14 count 9128493 score 16 count 908523 score 18 count 33649 #step 19 33 score -19 count 33649 score -17 count 807576 score -15 count 7268184 score -13 count 35403555 score -11 count 115550666 score -9 count 285362748 score -7 count 558898528 score -5 count 898790136 score -3 count 1220614416 score -1 count 1414838192 score 1 count 1414838192 score 3 count 1220614416 score 5 count 898790136 score 7 count 558898528 score 9 count 285362748 score 11 count 115550666 score 13 count 35403555 score 15 count 7268184 score 17 count 807576 score 19 count 33649 #step 20 26 score -20 count 7315 score -18 count 237006 score -16 count 2791404 score -14 count 17038098 score -12 count 65968551 score -10 count 185765052 score -8 count 407770704 score -6 count 723261600 score -4 count 1069535688 score -2 count 1342558544 score 0 count 1445267376 score 2 count 1342558544 score 4 count 1069535688 score 6 count 723261600 score 8 count 407770704 score 10 count 185765052 score 12 count 65968551 score 14 count 17038098 score 16 count 2791404 score 18 count 237006 score 20 count 7315