Example ARC061: Many mathematical formulas
You will be given the string S, which consists only of numbers> 1 and 9 and less. Within this string, you can put a + in some places between these characters. You don't have to put in one. However, the + must not be consecutive. All the strings created in this way can be regarded as mathematical expressions and the sum can be calculated. Calculate the values of all possible formulas and output the sum.
Constraints ・ 1 ≤|S|≤10 ・ All letters contained in S are numbers from 1 to 9.
Input / output example
[in] 125
[out] 176
# 125、1+25、12+5、1+2+4 patterns of 5 can be considered.
If it is 125, there are two places (1 {a} 2 {b} 5) where you can put "+", so 2 ^ 2 = 4 ways of formulas can be considered. ab There are two choices, with or without "+". And since it is about bit, look for the place where bit stands. The image looks like the following.
| index | a | b |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
You can see that there are 4 patterns in all.
Use the python bit operator right shift ">>" bitAND "&". For details on bit operators, here was very helpful.
--Right shift >>
Try shifting 11 to the right by 1 bit. The 1 on the far right disappears and the 0 on the far left is inserted. 1011 = 11 0101 = 5
Let's take 10 & 12 bitAND. (Leave 1 only where both are 1 for each place.) 1010 = 10 1100 = 12 1000 = 08
#Input: 125
s = ["1", "2", "5"]
n = len(s)
for i in range(2 ** (n-1)):
tmp = [False] * (n-1)
for j in range(n-1):
if i >> j & 1:
tmp[j] = True
pattern.append(tmp)
print(pattern)
[[False, False], [True, False], [False, True], [True, True]]
I was able to find all the patterns by bit full search. By the way, the answer to the example I solved is like this. (Although the code is dirty and there should be a smarter way to solve it)
Recommended Posts