Wir erhalten eine Liste von ganzen Zahlen p1, ..., pk (nicht unbedingt verschieden), wobei jede einen Wert zwischen 1 und 9 einschließlich hat. Mit jedem der p1, ..., pk genau einmal können wir Verkettungen von Ziffern bilden, um eine neue Liste von Zahlen zu erhalten; Wir geben dann das Produkt dieser neuen Liste aus. Ziel ist es, dieses Produkt zu maximieren, indem die besten Verkettungen von Ziffern ausgewählt werden.
Zum Beispiel erhalten wir die Liste: 2 3 2 (durch Leerzeichen getrennt). Wir können die folgenden Verkettungen bilden:
2 3 2
(Produkt dieser Verkettungen ist12
)23 2
(Produkt ist46
)32 2
(Produkt ist64
)22 3
(Produkt ist66
)
Da das größte Produkt, das wir aus Verkettungen bilden können, 66 ist, geben wir das aus.
Regeln:
- Es muss mindestens eine Multiplikation geben (dh Sie können nicht einfach alle Ziffern verketten und diese ausgeben).
- Sie können keine anderen Operatoren als die Multiplikation verwenden oder Klammern usw. einfügen.
- Angenommen, die Liste der angegebenen Ganzzahlen ist durch Leerzeichen getrennt, und alle Ganzzahlen haben Werte zwischen 1 und 9.
Der kürzeste Code (in Bytes) gewinnt!
Testfälle:
Eingabe : 1 2 3
; Ausgabe: 63
(dh 21*3
)
Eingabe : 2 5 9
; Ausgabe: 468
( 52*9
)
Eingabe : 1 2 3 4
; Ausgabe: 1312
( 41*32
)
Antworten:
CJam,
32282312 BytesProbieren Sie es online im CJam-Interpreter aus .
Vielen Dank an @ user23013, der mir geholfen hat, 16 ganze Bytes zu sparen!
Idee
Durch Zulassen der Zeichen in der Eingabezeichenfolge wird diese in Ganzzahlen (Gruppen aufeinanderfolgender Ziffern) unterteilt, die durch Leerzeichen getrennt sind. Durch Drücken einer Null und anschließendes Auswerten der permutierten Eingabezeichenfolge werden zwei oder mehr Ganzzahlen verschoben. Das Multiplizieren der obersten zwei ergibt entweder das Produkt der Eingabe, das in genau zwei ganze Zahlen geteilt wird, oder einen suboptimalen Wert.
Code
quelle
l2%_,,1>\e!m*{~S+m<~*}%$W=
.l2%S+e!{0\~*}%$W=
.CJam,
3635 BytesZiemlich einfach. Iteriert alle möglichen Kombinationen und sortiert sie nach Produkt. Dann wird die größte ausgegeben. Dies alles unter Berücksichtigung, dass mindestens 1 Multiplikation vorhanden sein sollte.
Wird bald eine Erklärung hinzufügen.
Probieren Sie es hier online aus
quelle
JavaScript (ES6) 125
Bearbeiten Ich denke, @oberon hat es richtig gemacht: "Jede neue Ziffer muss mit der kleinsten Zahl verkettet werden."
Ich werde diese Antwort nicht ändern, um seine Idee zu stehlen. Die Implementierung in ES6 würde 70 Bytes betragen (Vorzeichen geändert im Vergleich zum Vergleich als Zahl und nicht als Zeichenfolgen)
Meine Lösung
Wie ich in den Kommentaren sagte, ist für jedes Zahlenpaar a, b das Produkt a * b kleiner als die einfache Verkettung ab (= a * 10 ^ (Ziffern von b) + b). Es ist also besser, Produkte zu vermeiden und Verkettung zu bevorzugen, aber da mindestens 1 Produkt angefordert wird, müssen wir 2 Zahlen erstellen und diese multiplizieren.
Ich versuche alle möglichen Gruppierungen von Ziffern und baue ein Zahlenpaar, um es zu multiplizieren. Jede Zahl wird offensichtlich in absteigender Reihenfolge mit Ziffern erstellt.
Zum Beispiel mit einer Liste von 4 Zahlen, [1 2 3 4] - versuchen Sie:
Das Maximum dieser Werte ist das Ergebnis, das wir brauchen.
Die Gruppierungen können in einer Bitmap von 4 Bits mit dem Minimalwert 0001 und dem Maximalwert 0111 (dh 1 << (4 -1) - 1) in einer Schleife aufgelistet werden.
Nicht so golfen
Testen Sie mit dem folgenden Snippet in Firefox.
quelle
Python 3, 111 Bytes
Es ist wahrscheinlich viel golffähiger. Ich mag die Laufzeit (O ( n log n ), oder?).
Ungolfed mit Erklärung.
quelle
Pyth, 25 Bytes
Ich durchlaufe jede Permutation der Eingabe. Da dann jede optimale Kombination aus zwei ganzen Zahlen besteht, teile ich sie lediglich an jeder möglichen Position und multipliziere die verketteten Teilungen. Ich sortiere und erhalte dann das letzte Element.
quelle
R, 164
Als Methode bin ich mir nicht sicher, ob dies robust ist. Mit den Fällen, die ich getestet habe, scheint es jedes Mal zu funktionieren. Ich habe versucht, es gegen die Optimiererlösung zu testen, und es scheint auch dagegen in Ordnung zu sein. Ich bin mehr als bereit, mich als falsch zu erweisen :) Es gibt Raum zum Golfen, aber ich hatte gehofft, zuerst ein Feedback zur Methode zu bekommen.
Der allgemeine Prozess ist:
Mit einigen Kommentaren erweitert
Und einige Testläufe (implementiert als Funktion namens g)
quelle