Beispiel ARC061: Viele Formeln
Sie erhalten die Zeichenfolge S, die nur aus Zahlen> 1 und 9 oder weniger besteht. Innerhalb dieser Zeichenfolge können Sie an einigen Stellen zwischen diesen Zeichen ein + setzen. Sie müssen keine eingeben. Das + darf jedoch nicht fortlaufend sein. Alle auf diese Weise erstellten Zeichenketten können als mathematische Formeln betrachtet und die Summe berechnet werden. Berechnen Sie die Werte aller möglichen Formeln und geben Sie die Summe aus.
Einschränkungen ・ 1 ≤|S|≤10 ・ Alle in S enthaltenen Buchstaben sind Zahlen von 1 bis 9.
Beispiel für Eingabe und Ausgabe
[in] 125
[out] 176
# 125、1+25、12+5、1+2+4 Muster von 5 können berücksichtigt werden.
Wenn es 125 ist, gibt es zwei Stellen (1 {a} 2 {b} 5), an denen Sie "+" setzen können, sodass 2 ^ 2 = 4 Arten von Formeln berücksichtigt werden können. ab Es gibt zwei Möglichkeiten, mit oder ohne "+". Und da es um Bit geht, suchen Sie nach der Stelle, an der Bit steht. Das Bild sieht wie folgt aus.
| index | a | b |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
Sie können sehen, dass es insgesamt 4 Muster gibt.
Verwenden Sie den Python-Bit-Operator Rechtsverschiebung ">>" bitAND "&". Für Details zu Bitoperatoren war hier sehr hilfreich.
Versuchen Sie, 11 ein Bit nach rechts zu verschieben. Die 1 ganz rechts verschwindet und ganz links wird eine 0 eingefügt. 1011 = 11 0101 = 5
Nehmen wir 10 & 12 BitAND. (Lassen Sie 1 nur dort, wo beide für jeden Ort 1 sind.) 1010 = 10 1100 = 12 1000 = 08
#Eingabe: 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]]
Ich konnte alle Muster durch vollständige Suche finden. Die Antwort auf das von mir gelöste Beispiel lautet übrigens so. (Obwohl der Code schmutzig ist und es einen intelligenteren Weg geben sollte, ihn zu lösen)
Recommended Posts