#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];
bool forbidden[MAX_NR_SET+1];
int n;
// base = lcm(1, .. , n)
long basemul; // = base * multiplier
long divn; // = basemul/n;
long divn1; // = basemul/(n-1);

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;

bool used_chain = false;
int chain_sel[6];

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);
    if (used_chain && false)
    {
        fprintf(fout, " |");
        for (int i = 0; i < 6; i++)
            fprintf(fout, " %d", chain_sel[i]);
    }
    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++;

    int sel[100];
    int nrsel = 0;
    for (int i = 1; i <= divn; i++)
        if (selected[i])
            sel[nrsel++] = i;
    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, nrsel, nrsel, 0);
    }

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

void generateSets(long i, long left, long nn, bool exact)
{
    if (exact && nn < 0)
        return;
    if (i == 0)
    {
        if (left == 0 && nn <= 0)
            checkSet();
        return;
    }
    if (left > sumUpTo(i))
        return;
    if (nn > i)
        return;
    generateSets(i-1, left, nn, exact);
    if (found_set)
        return;
    if (left >= i)
    {
        selected[i] = true;
        generateSets(i-1, left - i, nn-1, exact);
        selected[i] = false;
    }
}

void generateSetsSplit(int extra_split, int from)
{
    if (extra_split == 0)
    {
        checkSet();
        return;
    }
    extra_split--;
    for (int i = from; i > 0; i--)
    {
        if (selected[i])
        {
            selected[i] = false;
            for (int j = 1; j < i-j; j++)
                if (!selected[j] && !selected[i-j])
                {
                    selected[j] = true;
                    selected[i-j] = true;
                    generateSetsSplit(extra_split, i-1);
                    selected[i-j] = false;
                    selected[j] = false;
                }
            selected[i] = true;
        }
    }
}

int max_bucket_filled;

bool knapsack2(int bucket_nr, int nr_buckets, int bucket_size, int sel[], int nrsel, bool printsol)
{
    if (bucket_nr == nr_buckets)
    {
        if (printsol)
        {
            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(stderr, "%s%d", sep, sel[i]);
                        sep = "+";
                    }
            }
        }
        return true;
    }

    for (int i = nrsel-1; i >= 0; i--)
        if (assigned_to[sel[i]] == -1 && buckets[bucket_nr] >= sel[i])
        {
            assigned_to[sel[i]] = bucket_nr;
            buckets[bucket_nr] -= sel[i];
            if (buckets[bucket_nr] == 0)
            {
                if (bucket_nr+1 > max_bucket_filled)
                    max_bucket_filled = bucket_nr+1;
            }
            if (knapsack2(buckets[bucket_nr] == 0 ? bucket_nr+1 : bucket_nr, nr_buckets, bucket_size, sel, nrsel, printsol))
                return true;
            buckets[bucket_nr] += sel[i];
            assigned_to[sel[i]] = -1;
            if (buckets[bucket_nr] == bucket_size)
                break;
        }
    
    return false;
}

void preSplit(int extra_split)
{
    if (extra_split == 0)
        checkSet();

    // Some pre check if splitting is going to be useful    
    int sel[100];
    int nrsel = 0;
    for (int i = 1; i <= divn; i++)
        if (selected[i])
            sel[nrsel++] = i;
    for (int nr_buckets = n - 2; nr_buckets > n/2; nr_buckets--)
    {
        for (int j = 0; j < nr_buckets; j++)
            buckets[j] = basemul / nr_buckets;
        for (int j = 0; j < nrsel; j++)
            assigned_to[sel[j]] = -1;
        max_bucket_filled = 0;
        if (!knapsack2(0, nr_buckets, basemul / nr_buckets, sel, nrsel, false))
        {
            int needed = ((nr_buckets - max_bucket_filled)+1)/2;
            if (needed > extra_split)
                return;
        }
    }
    
    generateSetsSplit(extra_split, divn);
}

void generateSetsMinimal(long i, long nn, int extra_split)
{
    if (nn == 0)
    {
        preSplit(extra_split);
        return;
    }
    if (i > divn/2 + nn)
    {
        generateSetsMinimal(i-1, nn, extra_split);
        if (found_set)
            return;
    }
    selected[i] = true;
    selected[divn-i] = true;
    generateSetsMinimal(i-1, nn-1, extra_split);
    selected[divn-i] = false;
    selected[i] = false;
}

void generateNecklageSets(int extra_split)
{
    bool trace = false;
    tried = 0;

    int s = divn;
    long left = basemul;
    for (int i = 1; ; i++)
    {
        selected[s] = true;
        left -= s;
        if (trace) fprintf(stderr, " %3d left: %d\n", s, left);
        long div = i%2 == 0 ? divn : divn1;
        long next_s = div - s;
        for (int j = 1; j < next_s - j; j++)
        {
            if (trace) fprintf(stderr, "   split %d", j);
            long s_left = left - j;
            long s_s = j;
            for (int i2 = i+1; s_left > 0; i2++)
            {
                long next_s_s = (i2%2 == 0 ? divn : divn1) - s_s;
                if (trace) fprintf(stderr, " %d", next_s_s);
                if (next_s_s == s_s || next_s_s == 0 || next_s_s >= divn || selected[next_s_s])
                {
                    if (trace) fprintf(stderr, "!");
                    break;
                }
                s_s = next_s_s;
                s_left -= s_s;
            }
            if (trace) fprintf(stderr, " left %d %s\n",s_left, s_s + j == next_s ? "correct" : "");
            if (s_left == 0 && s_s + j == next_s)
            {
                // set selected
                s_left = left - j;
                s_s = j;
                selected[s_s] = true;
                for (int i2 = i+1; s_left > 0; i2++)
                {
                    s_s = (i2%2 == 0 ? divn : divn1) - s_s;
                    selected[s_s] = true;
                    s_left -= s_s;
                }
                if (trace) {
                    fprintf(stderr, "Solution:");
                    for (int k = 1; k <= divn; k++)
                        if (selected[k])
                            fprintf(stderr, " %d", k);
                    fprintf(stderr, "\n");
                }
                preSplit(extra_split);
                // reset selected
                s_left = left - j;
                s_s = j;
                selected[s_s] = false;
                for (int i2 = i+1; s_left > 0; i2++)
                {
                    s_s = (i2%2 == 0 ? divn : divn1) - s_s;
                    selected[s_s] = false;
                    s_left -= s_s;
                }
            }
        }
        
        if (next_s == s)
            break;
        s = next_s;
    }
    if (!found_set)
        fprintf(stderr, "tried %ld\n", tried);
}


bool divn1_allowed(int s)
{
    long divn1_s = divn1 - s;
    return divn1_s >= divn || !selected[divn1_s];
}

void generateChains(int nr_chain, int start, int left, int extra_split)
{
    if (nr_chain == 3)
    {
        if (left == 0)
        {
            buckets[0] = buckets[1] = divn1;
            if (extra_split > 0 || knapsack(2, 0, chain_sel, 6, 6, 0))
            {
                preSplit(extra_split);
            }
        }
        return;
    }
    
    for (int s = start; s < divn/2; s++)
    {
        long s_e = s;
        long s_o = divn - s;
        if (!selected[s_e] && divn1_allowed(s_e) && divn1_allowed(s_o))
        {
            chain_sel[2*nr_chain] = s_e;
            int t = 1;
            for (; left - t - (2-nr_chain) >= 0; t++)
            {
                selected[s_e] = true;
                selected[s_o] = true;
                chain_sel[2*nr_chain+1] = s_o;
                generateChains(nr_chain + 1, s, left - t, extra_split);
                s_e = divn1 - s_o;
                if (s_e >= divn || s_e <= s)
                    break;
                s_o = divn - s_e;
                if (s_o <= s || !divn1_allowed(s_o))
                    break;
            }
            
            // remove selected
            s_e = s;
            for (int i = 1; i <= t; i++)
            {
                selected[s_e] = false;
                long s_o = divn - s_e;
                selected[s_o] = false;
                s_e = divn1 - s_o;
            }
        }
    }                
}

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

    long base = 1;
    for (n = 1; ; n++)
    {
        base = lcm(base, n);
        if (n < 9)
            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++;
        if (min_multiple > 1)
            fprintf(stderr, "  need %ld %ld\n", min_multiple, base * min_multiple);

        // Generate all sets
        found_set = false;
        for (long nn = n*2-1; nn <= n*2+6 && !found_set; nn++)
        {
            basemul = base * min_multiple;
            divn = basemul/n;
            divn1 = n == 1 ? 0 : basemul/(n-1);

            if (divn <= MAX_NR_SET)
            {
                fprintf(stderr, "for %d try %d, %d\n", n, divn, nn);
                for (int i = 1; i <= divn; i++)
                    selected[i] = false;
                if (n >= 4 && nn >= n*2)
                {
                    fprintf(stderr, "chains(\n"); used_chain = true;
                    generateChains(0, 1, n, nn - n*2);
                    fprintf(stderr, ")chains\n"); used_chain = false;
                }
                if (n >= 4 && nn >= n*2-1)
                {
                    fprintf(stderr, "necklage(\n");
                    generateNecklageSets(nn - (n*2-1));
                    fprintf(stderr, ")necklage\n");
                }
            }
        }
    }

    return 0;
}