2014
01-26

# Toothpick Arithmetic

A toothpick expression uses toothpicks to represent a positive integer. The expression consists of operands and operators.

Each operand consists of one or more vertical toothpicks ("|"); the value of the operand is the number of toothpicks.

The operators that can appear in an expression are addition and multiplication. The addition operator is the plus sign ("+"), which consists of one vertical and one horizontal toothpick. The multiplication operator is the letter "x", which also consists of two toothpicks. Multiplication has precedence over addition.

The expression must begin with an operand. Thereafter, operators and operands alternate. Finally, the expression must end with an operand. Given a positive integer, your program must represent it as a toothpick expression, using the smallest number of toothpicks.

The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain one positive integer, not exceeding 5000.

The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain one positive integer, not exceeding 5000.

35
37
53

14 toothpicks: |||||||x|||||=35
17 toothpicks: ||||||x||||||+|=37
21 toothpicks: |||||x|||||x||+|||=53

//+option:-ansi -Wall -Wextra
//+source:http://acm.hdu.edu.cn/showproblem.php?pid=2402
//press <F7> to update the source to mark file.
#include "iostream"
#include "algorithm"
#include "cstdio"
#include "cstdlib"
#include "cstring"
using namespace std;
#define $FOREACH(a, b) for(__typeof(b.begin())a=b.begin(), a##ed__=b.end(); a!=a##ed__; a++) #define$FOREACHC(a, b, cond) for (__typeof(b) a=b;(cond); b++, a=b)
#define $QUEUEPROC(cond, U, V) \ for(int u=(U);cond;u=(U))\$FOREACH(v, V)
#define $STACKPROC(cond, U, V) \ for (int u=(U); cond; u=(U))\ for (bool child=false; !child; child=true)\$FOREACHC(v, (V), !child)
#define \$ASSERT(a) ({fprintf(stderr,"%s:%d: %s\n", __FILE__, __LINE__, #a); exit(-1);})

int mul[10000], gmul[10000];
int F[10000], G[10000];
void pre()
{
for (int i=1; i<=6000; i++)
mul[i] = add[i] = i,
gmul[i] = gadd[i] = 0,
F[i] = i, G[i]=0;
/*for (int i=1; i<=5000; i++)
for (int j=1; j<i; j++)
{
if (F[i] > F[j] + i-j + 2)
F[i] = F[j] + i-j + 2,
G[i] = j;
if (i%j == 0 && F[i] > F[j] + i/j + 2)
F[i] = F[j] + i/j + 2,
G[i] = -j;
}
*/

for (int i=1; i<=6000; i++)
for (int j=i-1; j>0; j--)
if (i%j == 0 &&
mul[i] > mul[j] + i/j + 2)
mul[i] = mul[j] + i/j + 2,
gmul[i] = j;
for (int i=1; i<=6000; i++)		add[i] = mul[i];
for (int i=1; i<=6000; i++)
for (int j=i-1; j>0; j--)
if (add[i] > add[j] + mul[i-j] + 2)

}

void printmul(int N)
{
if (gmul[N] == 0)
for (int i=0; i<N; i++)
printf("|");
else
{
printmul(gmul[N]);
printf("x");
for (int i=0; i<N/gmul[N]; i++)
printf("|");
}
}

void print(int N)
{
if (gadd[N] == 0) printmul(N);
else
{
printf("+");
}
}

void printT(int N)
{
if (G[N] == 0) for (int i=0; i<N; i++) printf("|");
else
if (G[N] < 0)
{
printT(-G[N]);
printf("x");
for (int i=0; i<-N/G[N]; i++) printf("|");
}else{
printT(G[N]);
printf("+");
for (int i=0; i<N-G[N]; i++) printf("|");
}
}
int main()
{
pre();
int N;
while (scanf("%d", &N)!=EOF)
{
if (N==0) break;
if (add[N] < mul[N])
{
printf("%d toothpicks: ", add[N]);
print(N);
printf("=%d\n", N);
}else{
printf("%d toothpicks: ", mul[N]);
printmul(N);
printf("=%d\n", N);

}
}
}