Solution for the ACM ICPC toothpick problem: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1578. Usage: gcc -o toothpick -std=c99 toothpick.c; echo -e "35\n37\n53\n10\n20\n50" | ./toothpick

toothpick.c

#include <stdio.h>
#include <stdlib.h>

typedef struct t_operation {
    char operand;
    int n;
    struct t_operation* next;
} t_operation;

int opCost(t_operation* op) {
    int cost = 0;
    t_operation* iterator = op;
    while (iterator != NULL) {
        cost += iterator->n;
        if (iterator->operand == '+' || iterator->operand == 'x') {
            cost += 2;
        }
        iterator = iterator->next;
    }
    return cost;
}

int opEval(t_operation* op) {
    int sum = 0;
    int first = 0;
    for (t_operation* iterator = op; iterator != NULL; iterator = iterator->next) {
        if (first == 0) {
            sum += iterator->n;
            first = -1;
        } else if (iterator->operand == '+') {
            sum += iterator->n;
        } else if (iterator->operand == 'x') {
            sum *= iterator->n;
        }
    }
    return sum;
}

void opPrint(int n, t_operation* op) {
    for (t_operation* iterator = op; iterator != NULL; iterator = iterator->next) {
        if (iterator->operand != ' ') {
            printf("%c", iterator->operand);
        }
        for (int i = iterator->n; i > 0; --i) {
            printf("|");
        }
        printf("(%i)", iterator->n);
    }
    printf("=%i, actual=%i (cost=%i)\n", n, opEval(op), opCost(op));
}

t_operation* opMake(char operand, int n) {
    t_operation* op = malloc(sizeof(t_operation));
    op->operand = operand;
    op->n = n;
    op->next = NULL;
    //printf("info: allocated %p\n", op);
    return op;
}

void opFree(t_operation* op) {
    while (op != NULL) {
        t_operation* old = op;
        op = op->next;
        //printf("hi %c %i op=%p\n", old->operand, old->n, op);
        //printf("info: freeing %p\n", old);
        free(old);
    }
    //printf("---\n");
}

// Returns the next position after removed item.
t_operation* opRemove(t_operation* op, t_operation* remove) {
    t_operation* iterator = op;
    t_operation* prev = NULL;
    while (iterator != NULL) {
        if (prev != NULL && iterator == remove) {
            //printf("iterator=%p next=%p\n", iterator, iterator->next);
            prev->next = iterator->next;
            free(iterator);
            return prev->next;
        }
        prev = iterator;
        iterator = iterator->next;
    }
    printf("error: opRemove :: removal not found in op\n");
    return op;
}

t_operation* opReduce(t_operation* op) {
    int additions = 0;
    t_operation* iterator = op;
    t_operation* prev = NULL;
    t_operation* last = NULL;
    while (iterator != NULL) {
        last = iterator;
        if (iterator->operand == '+' || (iterator->n == 1 && iterator->operand == 'x')) {
            if (iterator->operand == '+') {
                additions += iterator->n;
            }
            if (prev == NULL) {
                op = iterator->next;
                free(iterator);
                iterator = op;
            } else {
                iterator = opRemove(prev, iterator);
                //printf("iterator now = %p\n", iterator);
                last = prev;
                continue;
            }
        }
        prev = iterator;
        iterator = iterator->next;
    }
    if (last != NULL && additions > 0) {
        last->next = opMake('+', additions);
    }
    return op;
}

t_operation* opEnd(t_operation* op) {
    t_operation* end = op;
    if (end != NULL) {
        while (end->next != NULL) {
            end = end->next;
        }
    }
    return end;
}

t_operation* opAppend(t_operation* op, t_operation* append) {
    t_operation* end = opEnd(op);
    end->next = append;
    return append;
}

int getCost(int n, int i) {
    if (n % i == 0) {
        return 2 + i + n / i;
    } else {
        return 2 + 2 + i + n / i + n % i;
    }
}

int lowestCost(int n) {
    int lowest = n, value = n;
    for (int i = n / 2 + 1; i >= 2; --i) {
        int cost = getCost(n, i);
        if (cost < lowest) {
            lowest = cost;
            value = i;
        }
    }
    return value;
}

t_operation* opLow(char firstOperand, int n) {
    t_operation* best = NULL;
    for (int a = n; a > 0 && a > n - 4; --a) {
        int i = lowestCost(a);

        t_operation* op;
        if (lowestCost(a / i) < a / i) {
            op = opLow(' ', a / i);
        } else {
            op = opMake(firstOperand, a / i);
        }

        if (lowestCost(i) < i) {
            op->next = opLow('x', i);
        } else {
            op->next = opMake('x', i);
        }

        if (a % i != 0) {
            opAppend(op, opMake('+', a % i));
        }

        if (a != n) {
            opAppend(op, opMake('+', n - a));
            //printf("n=%i, a=%i, n-a=%i\n", n, a, n - a);
            //printf("sum=%i ", opEval(op));opPrint(n, op);
        }

        op = opReduce(op);

        if (opEval(op) == n) {
            if (best == NULL) {
                best = op;
            } else if (opCost(op) < opCost(best)) {
                opFree(best);
                best = op;
            }
        }/* else {
            printf("sum=%i ", opEval(op));opPrint(n, op);
        }*/
    }
    //printf("sum=%i ", opEval(best));opPrint(n, best);
    return best;
}

void toothpicks(int n) {
    t_operation* op = opLow(' ', n);
    //printf("n=%i, cost=%i\n", n, opCost(op));
    opPrint(n, op);
    opFree(op);
}

int main(size_t argc, const char** argv) {
    char buffer[BUF_SZ];
    int n;
    while (fgets(buffer, BUF_SZ, stdin) != NULL) {
        buffer[strlen(buffer)-1] = '\0';
        int n = atoi(buffer);
        //printf("%s\n", toothpicks(n));
        toothpicks(n);
    }
	return 0;
}