back to listing index

### ACM-ICPC Live Archive

[web search]
Original source (icpcarchive.ecs.baylor.edu)
Tags: acm
Clipped on: 2016-06-11

 Search:

 Home Browse Problems Saturday, 11 June 2016
 Online Judge

Root

Regionals 2006 >> North America - Rocky Mountain

### 3577 - Toothpick Arithmetic

Time limit: 3.000 seconds

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.

## Input

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.

## Output

Each line of input will give rise to one line of output, consisting of: the number of toothpicks used in the expression, the expression, and the given integer from the input, formatted as shown in the sample output. The word ``toothpicks" (even if the answer is 1) will be preceded by one blank space and followed by a colon and one blank space. An equal sign (but no blank spaces) will separate the expression from the given number. The expression should not contain any spaces.

If there are multiple expressions which use the smallest number of toothpicks, any such expression is acceptable.

```
35
37
53
```

## Sample Output

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

 ACM-ICPC Live Archive