#include #include #include class Permutations { inline void _swap(int &x, int &y) { int h = x; x = y; y = h; } public: Permutations(int val_n, bool *range = 0) : n(val_n), _more(true), _range(range) { a = new int[n]; for (int i = 0; i < n; i++) a[i] = i; } ~Permutations() { delete []a; } bool more() { return _more; } void next() { _more = false; int k = n; for (int i = n-2; i >= 0; i--) if (_range != 0 && !_range[i]) { k = i+1; } else if (a[i] < a[i+1]) { _more = true; for (int j = k-1; j > i; j--) if (a[j] > a[i]) { _swap(a[j], a[i]); break; } i++; for (int j = k-1; j > i; j--, i++) _swap(a[j], a[i]); for (int j = k; j < n; j++) a[j] = j; break; } } inline int operator[](int i) { return a[i]; } int n; int *a; private: bool _more; bool *_range; }; FILE *fresults = 0; long gcd(long a, long b) { while (b != 0) { long c = a % b; a = b; b = c; } return a; } long lcm(long a, long b) { return a * (b / gcd(a, b)); } inline long sumUpTo(long n) { return n*(n+1)/2; } #define ROUND_UP_DIV(X,Y) (((X)+(Y)-1)/(Y)) #define MAX_N 40 #define MAX_PIECES 100 #define MAX_NR_SET 200000 bool selected[MAX_NR_SET+1]; int sel_values[100]; int nr_sel_values = 0; int n; long basemul; // = base * multiplier long divn; // = basemul/n; bool found_set; int assigned_to[MAX_NR_SET+1]; int buckets[MAX_N]; bool knapsack(int nr_buckets, int nr_buckets_in_use, int sel[], int nrsel, int left, FILE* fout) { if (left == 0) { if (nr_buckets == nr_buckets_in_use) { if (fout) { for (int b = 0; b < nr_buckets; b++) { const char *sep = " "; for (int i = 0; i < nrsel; i++) if (assigned_to[sel[i]] == b) { fprintf(fout, "%s%d", sep, sel[i]); sep = "+"; } } } return true; } return false; } left--; // Skip buckets that are full int i_first = 0; while (buckets[i_first] == 0) i_first++; int value = sel[left]; // If there is an exact fit for the value at hand in one of // the half filled buckets, take it, because any solution // that has this value in some other bucket, can be made // by swapping the other values that need to be put in this // bucket with that value. for (int i = i_first; i < nr_buckets_in_use; i++) if (buckets[i] - value == 0) { assigned_to[value] = i; buckets[i] -= value; if (knapsack(nr_buckets, nr_buckets_in_use, sel, nrsel, left, fout)) return true; buckets[i] += value; return false; } // See if the value fits in one of the half filled buckets for (int i = i_first; i < nr_buckets_in_use; i++) if (buckets[i] - value >= 0) { assigned_to[value] = i; buckets[i] -= value; if (knapsack(nr_buckets, nr_buckets_in_use, sel, nrsel, left, fout)) return true; buckets[i] += value; } // If there is still a bucket that is not filled at all, try it: if (nr_buckets_in_use < nr_buckets) { assigned_to[value] = nr_buckets_in_use; buckets[nr_buckets_in_use] -= value; if (knapsack(nr_buckets, nr_buckets_in_use+1, sel, nrsel, left, fout)) return true; buckets[nr_buckets_in_use] += value; } return false; } int nr_buckets; int bucket_size; bool knapsack2(int bucket_nr, int sel_left) { if (bucket_nr == nr_buckets) return true; sel_left--; for (int i = 0; i < nr_sel_values; i++) if (assigned_to[sel_values[i]] == -1 && buckets[bucket_nr] >= sel_values[i]) { assigned_to[sel_values[i]] = bucket_nr; buckets[bucket_nr] -= sel_values[i]; int add = buckets[bucket_nr] == 0 ? 1 : 0; if ( sel_left > 3 * (nr_buckets - bucket_nr - 1) - add && knapsack2(bucket_nr+add, sel_left)) return true; buckets[bucket_nr] += sel_values[i]; assigned_to[sel_values[i]] = -1; if (buckets[bucket_nr] == bucket_size) break; } return false; } long tried; void printSolution(int sel[], int nrsel, FILE* fout) { fprintf(fout, "\n%d set: ", n); for (int j = 1; j <= divn; j++) if (selected[j]) fprintf(fout, " %d", j); fprintf(fout, "\n"); for (nr_buckets = n/2 > 1 ? n/2+1 : 2; nr_buckets <= n; nr_buckets++) { for (int j = 0; j < nr_buckets; j++) buckets[j] = basemul / nr_buckets; fprintf(fout, "%d buckets with %d: ", nr_buckets, basemul / nr_buckets); knapsack(nr_buckets, 0, sel, nrsel, nrsel, fout); fprintf(fout, "\n"); } } int count = 0; void checkSet() { tried++; // See if there are enough pairs for (nr_buckets = n-2; nr_buckets > n/2; nr_buckets--) { int nr_pairs = 3 * nr_buckets - nr_sel_values; if (nr_pairs <= 0) break; bucket_size = basemul / nr_buckets; for (int i = 0; i < nr_sel_values; i++) if (2*sel_values[i]-1 > bucket_size && selected[bucket_size - sel_values[i]]) { if (--nr_pairs == 0) break; } if (nr_pairs > 0) return; } for (nr_buckets = n-2; nr_buckets > n/2; nr_buckets--) { bucket_size = basemul / nr_buckets; for (int j = 0; j < nr_buckets; j++) buckets[j] = bucket_size; for (int j = 0; j < nr_sel_values; j++) assigned_to[sel_values[j]] = -1; int sel_left = nr_sel_values; int bucket_nr = 0; for (int i = 0; i < nr_sel_values; i++) if (2*sel_values[i]-1 >= bucket_size && selected[bucket_size - sel_values[i]]) { assigned_to[sel_values[i]] = bucket_nr; assigned_to[bucket_size - sel_values[i]] = bucket_nr; bucket_nr++; sel_left -= 2; } if (!knapsack2(bucket_nr, sel_left)) return; } found_set = true; count++; printSolution(sel_values, nr_sel_values, stderr); fprintf(stderr, "\n"); if (fresults != 0) { printSolution(sel_values, nr_sel_values, fresults); fflush(fresults); } } bool filled[MAX_N][MAX_N]; int to_go_i[MAX_N]; int left_i[MAX_N]; int to_go_j[MAX_N]; int left_j[MAX_N]; int fill_mode[MAX_PIECES]; int fill_i[MAX_PIECES]; int fill_j[MAX_PIECES]; bool fill_other_is_1[MAX_PIECES]; void fill_path(int nr_pieces) { if (nr_pieces == 0) return; nr_pieces--; int min_to_go = 1000; int minor_min_to_go = 1000; int pos_i; int pos_j; int mode; for (int i = 0; i < n; i++) if (to_go_i[i] > 0) for (int j = 0; j < n; j++) if (to_go_j[j] > 0) if (filled[i][j]) if (to_go_i[i] == 1 && to_go_j[j] == 1) { fill_mode[nr_pieces] = 0; fill_i[nr_pieces] = i; fill_j[nr_pieces] = j; filled[i][j] = false; to_go_i[i]--; to_go_j[j]--; fill_path(nr_pieces); to_go_j[j]++; to_go_i[i]++; filled[i][j] = true; return; } else if (to_go_i[i] <= to_go_j[j]) { if (to_go_i[i] < min_to_go || (to_go_i[i] == min_to_go && to_go_j[j] < minor_min_to_go)) { min_to_go = to_go_i[i]; mode = min_to_go == 1 ? 1 : 3; minor_min_to_go = to_go_j[j]; pos_i = i; pos_j = j; } } else { if (to_go_j[j] < min_to_go || (to_go_j[j] == min_to_go && to_go_i[i] < minor_min_to_go)) { min_to_go = to_go_j[j]; mode = min_to_go == 1 ? 2 : 3; minor_min_to_go = to_go_i[i]; pos_i = i; pos_j = j; } } fill_mode[nr_pieces] = mode; fill_i[nr_pieces] = pos_i; fill_j[nr_pieces] = pos_j; filled[pos_i][pos_j] = false; to_go_i[pos_i]--; to_go_j[pos_j]--; fill_path(nr_pieces); to_go_j[pos_j]++; to_go_i[pos_i]++; filled[pos_i][pos_j] = true; } void fill_along_path(int nr_pieces) { if (nr_pieces == 0) { for (int i = 0; i < n; i++) if (left_i[i] > 0) return; for (int j = 0; j < n-1; j++) if (left_j[j] > 0) return; checkSet(); return; } nr_pieces--; int i = fill_i[nr_pieces]; int j = fill_j[nr_pieces]; switch (fill_mode[nr_pieces]) { case 0: { int left = left_i[i]; if (left > 0 && !selected[left] && left_j[j] == left) { selected[left] = true; sel_values[nr_sel_values++] = left; left_i[i] = 0; left_j[j] = 0; fill_along_path(nr_pieces); left_j[j] = left; left_i[i] = left; nr_sel_values--; selected[left] = false; } break; } case 1: { int left = left_i[i]; if (left > 0 && !selected[left] && left_j[j] > left) { selected[left] = true; sel_values[nr_sel_values++] = left; left_i[i] = 0; left_j[j] -= left; fill_along_path(nr_pieces); left_j[j] += left; left_i[i] = left; nr_sel_values--; selected[left] = false; } break; } case 2: { int left = left_j[j]; if (left > 0 && !selected[left] && left_i[i] > left) { selected[left] = true; sel_values[nr_sel_values++] = left; left_i[i] -= left; left_j[j] = 0; fill_along_path(nr_pieces); left_j[j] = left; left_i[i] += left; nr_sel_values--; selected[left] = false; } break; } case 3: { int left = left_i[i]; if (left_j[j] < left) left = left_j[j]; for (int l = 1; l < left; l++) { if (!selected[l]) { selected[l] = true; sel_values[nr_sel_values++] = l; left_i[i] -= l; left_j[j] -= l; fill_along_path(nr_pieces); left_j[j] += l; left_i[i] += l; nr_sel_values--; selected[l] = false; } } break; } } } class DivisionsIterator { public: DivisionsIterator(int buckets, int pieces, bool one) : _pieces(pieces), _buckets(buckets) { _i = 0; if (one) { _div[_i++] = 1; _pieces--; } while (_i < buckets-1) { _div[_i++] = 2; _pieces -= 2; } _div[_i] = _pieces; } bool more() { return _i > 0; } void next() { _i--; for (; _i >= 0; _i--) { int v = _div[_i] + 1; if (v * (_buckets-_i-1) + 1 <= _pieces) { _div[_i++]++; _pieces--; while (_i < _buckets-1) { _div[_i++] = v; _pieces -= v; } _div[_i] = _pieces; return; } _pieces += _div[_i]; } } int operator[](int i) { return _div[i]; } private: int _pieces; int _buckets; int _div[MAX_N]; int _i; }; void solve(int tot_nr_pieces) { fprintf(stderr, "solve n=%d ", n); for (DivisionsIterator divisionIt1(n, tot_nr_pieces, true); divisionIt1.more(); divisionIt1.next()) { for (DivisionsIterator divisionIt2(n-1, tot_nr_pieces, false); divisionIt2.more(); divisionIt2.next()) { for (int i = 0; i < n; i++) fprintf(stderr, "%d ", divisionIt1[i]); fprintf(stderr, " - "); for (int j = 0; j < n-1; j++) fprintf(stderr, "%d ", divisionIt2[j]); fprintf(stderr, "\n"); int placed_i[MAX_N]; for (int i = 0; i < n; i++) placed_i[i] = 0; int placed_j[MAX_N]; for (int j = 0; j < n-1; j++) placed_j[j] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n-1; j++) filled[i][j] = false; int i = 0; int j = 0; int p = 0; while (j >= 0) { while (i < n && j < n-1) { if ( placed_i[i] < divisionIt1[i] && placed_j[j] < divisionIt2[j] && !(i > 0 && divisionIt1[i-1] == divisionIt1[i] && placed_i[i-1] == 0)) { filled[i][j] = true; placed_i[i]++; placed_j[j]++; p++; } bool not_full = (i == n-1 && placed_j[j] < divisionIt2[j]); i++; if (i == n) { i = 0; j++; } if (not_full) break; } if (p == tot_nr_pieces) { bool smaller = false; bool range[MAX_N]; for (int j = 0; j < n-2; j++) range[j] = divisionIt2[j] == divisionIt2[j+1]; for (Permutations j_perm(n-1, range); j_perm.more() && !smaller; j_perm.next()) { bool equal = true; for (int j = 0; j < n-1 && equal; j++) equal = divisionIt2[j] == divisionIt2[j_perm[j]]; if (equal) { int cmp = 0; bool used[MAX_N]; for (int i = 0; i < n; i++) used[i] = false; for (int i = 0; i < n && cmp == 0; i++) { int i1 = 0; while (i1 < n && (used[i1] || divisionIt1[i1] != divisionIt1[i])) i1++; for (int i2 = i1+1; i2 < n; i2++) if (!used[i2] && divisionIt1[i2] == divisionIt1[i]) { int cmp2 = 0; for (int j = 0; j < n-1 && cmp2 == 0; j++) if (filled[i1][j_perm[j]] != filled[i2][j_perm[j]]) cmp2 = filled[i1][j_perm[j]] ? 1 : -1; if (cmp2 < 0) i1 = i2; } used[i1] = true; for (int j = 0; j < n-1 && cmp == 0; j++) if (filled[i][j] != filled[i1][j_perm[j]]) cmp = filled[i][j] ? 1 : -1; } if (cmp < 0) smaller = true; } } if (!smaller) { for (int i = 0; i < n; i++) { for (int j = 0; j < n-1; j++) fprintf(stderr, " %c", filled[i][j] ? 'X' : '_'); fprintf(stderr, "\n"); } fprintf(stderr, "\n"); for (int i = 0; i < n; i++) { to_go_i[i] = divisionIt1[i]; left_i[i] = divn; } for (int j = 0; j < n-1; j++) { to_go_j[j] = divisionIt2[j]; left_j[j] = basemul/(n-1); } fill_path(tot_nr_pieces); fill_along_path(tot_nr_pieces); } } for (;;) { if (i == 0) { i = n-1; j--; } else i--; if (j < 0) break; if (filled[i][j]) { filled[i][j] = false; placed_i[i]--; placed_j[j]--; p--; i++; if (i == n) { i = 0; j++; } break; } } } } } } int main(int argc, char *argv[]) { fresults = fopen("chocobar_results.txt", "wt"); clock_t start_time = clock(); long base = 1; for (n = 1; n <= 9; n++) { base = lcm(base, n); if (n < 7) continue; long max = base / n; fprintf(stderr, "%ld : %ld %ld ", n, base, max); long min_multiple = 1; while (sumUpTo(max * min_multiple) < base) min_multiple++; fprintf(stderr, " need %ld %ld\n", min_multiple, base * min_multiple); // Generate all sets found_set = false; for (int tot_nr_pieces = 2*n/*-1*/; !found_set && tot_nr_pieces <= 2*n+1; tot_nr_pieces++) { fprintf(stderr, "Try %d\n", tot_nr_pieces); long multiple = min_multiple; basemul = base * multiple; divn = basemul/n; for (int i = 1; i <= divn; i++) selected[i] = false; solve(tot_nr_pieces); } } clock_t end_time = clock(); fprintf(stderr, "Elapsed time: %ld\n", end_time - start_time); return 0; }