> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/d-doubleplusgood.md).

# D: Doubleplusgood

https\://open.kattis.com/problems/doubleplusgood

Since there are at most 18 digits in the input, there can be at most 8 plus signs, so the problem is brute-forceable in at most $$2^8=256$$ evaluations of the input expression.

To brute force search over all binary strings of length $$n$$, we increment a counter $$i$$ from $$0$$ to $$2^n-1$$; the $$j$$th digit in the binary string is then $$0$$ if $$(2^j) & i = 0$$ and $$1$$ otherwise, where $$&$$ is the bitwise AND function. For a given binary string, we then evaluate the input by using the binary string to decide which symbols to interpret as $$\boxplus$$. Since $$\boxplus$$ has higher precedence than $$+$$, we iterate from left to right, keeping track of the sum of previous concatenated terms and the current number; if the next operation is $$\boxplus$$, we concatenate the next number to the current number, and if the next operation is $$+$$, then we add the current number to the running sum and reset the current number to $$0$$. We use a set to keep track of the distinct values that we obtain trying all binary strings. In code:

```python
ints = input().split('+')
lens = list(map(len, ints))
ints = list(map(int, ints))
n = len(ints) - 1
possibilities = set()
for i in range(1 << n):
    curr_num = ints[0]
    curr_sum = 0
    for j in range(n):
        if (1 << j) & i:
            curr_num = curr_num * pow(10, lens[j+1]) + ints[j+1]
        else:
            curr_sum += curr_num
            curr_num = ints[j+1]
    curr_sum += curr_num
    possibilities.add(curr_sum)

print(len(possibilities))
```