#include <stdio.h>
#include <time.h>

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 MAX_N 20
#define MAX_NR_SET 200000
bool selected[MAX_NR_SET+1];
int sel_values[100];
int nr_sel_values = 0;
int n;
// base = lcm(1, .. , 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;
}

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 (int 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");
    }
}

void checkSet()
{
    tried++;

    bool all = true;
    for (int nr_buckets = n; all && nr_buckets > n/2; nr_buckets--)
    {
        long bucket_size = basemul / nr_buckets;
        for (int j = 0; j < nr_buckets; j++)
            buckets[j] = bucket_size;
        all = knapsack(nr_buckets, 0, sel_values, nr_sel_values, nr_sel_values, 0);
    }

    if (all)
    {
        found_set = true;
        printSolution(sel_values, nr_sel_values, stderr);
        fprintf(stderr, "\n");
        printSolution(sel_values, nr_sel_values, fresults);
        fflush(fresults);
    }
}



bool partial_knapsack(int nr_buckets, int nr_buckets_in_use, int nr_placed, int over)
{
    if (nr_placed == nr_sel_values)
    {
        // Count half filled buckets
        int c = 0;
        for (int i = 0; i < nr_buckets; i++)
            if (buckets[i] > 0)
            {
                c++;
                if (selected[buckets[i]])
                    c++;
            }
        return c <= over;
    }
    
    // Skip buckets that are full
    int i_first = 0;
    while (buckets[i_first] == 0)
        i_first++;
    
    int value = sel_values[nr_placed++];
    // 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 (partial_knapsack(nr_buckets, nr_buckets_in_use, nr_placed, over))
                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 (partial_knapsack(nr_buckets, nr_buckets_in_use, nr_placed, over))
                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 (partial_knapsack(nr_buckets, nr_buckets_in_use+1, nr_placed, over))
            return true;
        buckets[nr_buckets_in_use] += value;
    }    
    return false;
}

bool check_partial(int over)
{
    for (int nr_buckets = n-1; nr_buckets > n/2; nr_buckets--)
    {
        long bucket_size = basemul / nr_buckets;
        for (int j = 0; j < nr_buckets; j++)
            buckets[j] = bucket_size;
        if (!partial_knapsack(nr_buckets, 0, 0, over))
            return false;
    }
    return true;
}



int buckets_n[MAX_N];
int tot_nr_pieces;
int nr_buckets;

#define ROUND_UP_DIV(X,Y) (((X)+(Y)-1)/(Y))

int recdepth = 0;
class IncRecDepth
{
public:
    IncRecDepth() { recdepth++; }
    ~IncRecDepth() { recdepth--; }
};
void indent() { printf("%*.*s", recdepth*2, recdepth*2, ""); }

void generateAllPartitions(int nr_bucket, int min_this, int next_min_all, int nr_pieces)
{
    if (nr_bucket == n)
    {
        if (nr_pieces == tot_nr_pieces)
            checkSet();
        return;
    }
    if (nr_pieces == tot_nr_pieces)
        return;

    int left = buckets_n[nr_bucket];
    bool first = left == divn;
    if (ROUND_UP_DIV(left, min_this) + ROUND_UP_DIV(divn, next_min_all)*(n - nr_bucket - 1) > tot_nr_pieces - nr_pieces)
        return;
        
    if (nr_pieces > 2 && !check_partial(tot_nr_pieces - nr_pieces))
        return;

    if (left <= min_this && !selected[left])
    {
        if (first)
            next_min_all = left-1;
        selected[left] = true;
        sel_values[nr_sel_values++] = left;
        generateAllPartitions(nr_bucket+1, next_min_all, next_min_all-1, nr_pieces+1);
        nr_sel_values--;
        selected[left] = false;
    }

    // Still possible with number left
    for (int i = left < min_this ? left : min_this; i > 1; i--)
        if (!selected[i])
        {
            if (first)
                next_min_all = i-1;
            buckets_n[nr_bucket] -= i;
            selected[i] = true;
            sel_values[nr_sel_values++] = i;
            generateAllPartitions(nr_bucket, i-1, next_min_all, nr_pieces+1);
            nr_sel_values--;
            selected[i] = false;
            buckets_n[nr_bucket] += i;
        }
}

int main(int argc, char *argv[])
{
    fresults = fopen("chocobar_new_results.txt", "wt");

    long base = 1;
    for (n = 1; n <= 7; n++)
    {
        base = lcm(base, n);
        if (n < 5)
            continue;
        long max = base / n;
        fprintf(stderr, "%ld : %ld %ld\n", 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 (tot_nr_pieces = 2*n; !found_set && tot_nr_pieces <= 2*n; tot_nr_pieces++)
        {
            printf("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;
            for (int i = 0; i < n; i++)
                buckets_n[i] = divn;
            
            generateAllPartitions(0, divn, divn-1, 0);
        }
    }

    return 0;
}