Exemple ARC061: plusieurs formules
Vous recevrez la chaîne S, qui se compose uniquement de nombres> 1 et 9 ou moins. Dans cette chaîne, vous pouvez mettre un + à certains endroits entre ces caractères. Vous n'êtes pas obligé d'en mettre un. Cependant, le + ne doit pas être consécutif. Toutes les chaînes de caractères créées de cette manière peuvent être considérées comme des formules mathématiques et la somme peut être calculée. Calculez les valeurs de toutes les formules possibles et sortez la somme.
Contraintes ・ 1 ≤|S|≤10 ・ Toutes les lettres contenues dans S sont des nombres de 1 à 9.
Exemple d'entrée / sortie
[in] 125
[out] 176
# 125、1+25、12+5、1+2+4 modèles de 5 peuvent être considérés.
Si c'est 125, il y a deux endroits (1 {a} 2 {b} 5) où vous pouvez mettre "+", donc 2 ^ 2 = 4 manières de formules peuvent être considérées. ab Il existe deux choix, avec ou sans "+". Et comme il s'agit de bit, cherchez l'endroit où se trouve bit. L'image ressemble à ce qui suit.
| index | a | b |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
Vous pouvez voir qu'il y a 4 modèles en tout.
Utilisez l'opérateur bit de python avec décalage vers la droite ">>" bitAND "&". Pour plus de détails sur les opérateurs de bits, ici a été très utile.
--Droite shift >>
Essayez de décaler 11 un peu vers la droite. Le 1 le plus à droite disparaît et le 0 le plus à gauche est inséré. 1011 = 11 0101 = 5
Prenons 10 et 12 bits ET. (Ne laissez 1 que là où les deux valent 1 pour chaque place.) 1010 = 10 1100 = 12 1000 = 08
#Entrée: 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]]
J'ai pu trouver tous les modèles par une recherche peu complète. Au fait, la réponse à l'exemple que j'ai résolu est comme ça. (Bien que le code soit sale et qu'il devrait y avoir un moyen plus intelligent de le résoudre)
Recommended Posts