首页 > ACM题库 > HDU-杭电 > hdu 2402 Toothpick Arithmetic[解题报告]hoj
2014
01-26

hdu 2402 Toothpick Arithmetic[解题报告]hoj

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 add[10000], gadd[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)
				add[i] = add[j] + mul[i-j]+2,
				gadd[i]=j;
	

}

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
	{
		print(gadd[N]);
		printf("+");
		printmul(N-gadd[N]);
	}
}

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);

		}
	}
}