| Contests - ACM Student Chapter - PSUT |
|---|
| Private |
| Spectator |
| Hakam Round #1 |
|---|
| Finished |
Suppose you want to count the number of ways to represent $$$n$$$ as the sum of $$$k$$$ positive integers. The stars and bars method gives a useful way to represent each such sum.
Write $$$n$$$ stars in a row and place $$$k-1$$$ bars in the gaps between them. The bars divide the stars into $$$k$$$ non-empty groups, and the size of each group is one of the positive integers in the sum.
For example, the string **|*|** represents the ordered tuple $$$(2, 1, 2)$$$, or the sum $$$2 + 1 + 2 = 5$$$. It has $$$5$$$ stars divided into $$$3$$$ non-empty groups, so it represents one way to write $$$5$$$ as a sum of $$$3$$$ positive integers.
Every different placement of the bars gives a different ordered tuple, and every ordered tuple of $$$k$$$ positive integers with sum $$$n$$$ corresponds to exactly one placement. Thus, counting these tuples is equivalent to choosing $$$k-1$$$ gaps for the bars among the $$$n-1$$$ gaps between consecutive stars. This gives $$$\binom{n-1}{k-1}$$$ possible tuples.
In this problem, you are given a valid stars-and-bars string. Write the sum represented by the string as an equation.
The input consists of a string $$$s$$$ containing only the characters * and | ($$$1 \le |s| \le 1000$$$). The first and last characters of $$$s$$$ are guaranteed to be *, and no two bars are adjacent.
Print the sizes of the groups of stars in order, separated by + , followed by = and the total number of stars.
*|**|*
1 + 2 + 1 = 4
**|*|**
2 + 1 + 2 = 5
| Name |
|---|

