Dies ist eine Fortsetzung von Count-Arrays, die eindeutige Sätze erstellen . Der wesentliche Unterschied ist die Definition der Einzigartigkeit.
Betrachten Sie ein Array A
von Länge n
. Das Array enthält nur positive Ganzzahlen. Zum Beispiel A = (1,1,2,2)
. Definieren wir f(A)
als die Menge der Summen aller nicht leeren zusammenhängenden Subarrays von A
. In diesem Fall f(A) = {1,2,3,4,5,6}
. Die zu produzierenden Schritte f(A)
sind wie folgt:
Die Subarrays von A
sind (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)
. Ihre jeweiligen Beträge sind 1,1,2,2,2,3,4,4,5,6
. Das Set, das Sie aus dieser Liste erhalten, ist daher {1,2,3,4,5,6}
.
Wir nennen ein Array A
eindeutig, wenn es kein anderes Array B
mit der gleichen Länge gibt f(A) = f(B)
, außer dem A
umgekehrten Array . Zum Beispiel, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}
aber es gibt kein anderes Längenarray 3
, das den gleichen Satz von Summen erzeugt.
Aufgabe
Die Aufgabe für eine gegebene n
und s
ist es, die Anzahl der eindeutigen Arrays dieser Länge zu zählen. Sie können davon ausgehen, dass s
zwischen 1
und 9
. Sie müssen nur Arrays zählen, bei denen die Elemente entweder eine bestimmte Ganzzahl s
oder eine bestimmte Ganzzahl sind s+1
. ZB wenn s=1
die Arrays, die Sie zählen, nur 1
und enthalten 2
. Die Definition der Eindeutigkeit bezieht sich jedoch auf jedes andere Array gleicher Länge. Ein konkretes Beispiel [1, 2, 2, 2]
ist nicht eindeutig, da es die gleichen Summen wie ergibt [1, 1, 2, 3]
.
Sie sollten die Umkehrung eines Arrays sowie das Array selbst zählen (solange das Array natürlich kein Palindrom ist).
Beispiele
s = 1
Die Antworten für n = 2,3,4,5,6,7,8,9 lauten:
4, 3, 3, 4, 4, 5, 5, 6
Denn s = 1
die eindeutigen Arrays der Länge 4 sind
(1, 1, 1, 1)
(2, 1, 1, 2)
(2, 2, 2, 2)
s = 2
Die Antworten für n = 2,3,4,5,6,7,8,9 lauten:
4, 8, 16, 32, 46, 69, 121, 177
Ein Beispiel für ein Array, das nicht eindeutig s = 2
ist, ist:
(3, 2, 2, 3, 3, 3).
Dies hat die gleichen Summen wie: (3, 2, 2, 2, 4, 3)
und (3, 2, 2, 4, 2, 3)
.
s = 8
Die Antworten für n = 2,3,4,5,6,7,8,9 lauten:
4, 8, 16, 32, 64, 120, 244, 472
Ergebnis
Für einen bestimmten n
Fall sollte Ihr Code die Antwort für alle Werte von s
von 1
bis ausgeben 9
. Ihre Punktzahl ist der höchste Wert, n
für den dies in einer Minute abgeschlossen ist.
Testen
Ich muss Ihren Code auf meinem Ubuntu-Computer ausführen. Geben Sie daher so detaillierte Anweisungen wie möglich zum Kompilieren und Ausführen Ihres Codes an.
Bestenliste
- n = 13 von Christian Sievers in Haskell (42 Sekunden)
quelle
s
? Was stellt es dar?Antworten:
Haskell
Die
orig
Funktion erstellt alle Längenlistenn
mit Einträgens
oders+1
behält sie bei, wenn sie vor ihrer Umkehrung stehen, berechnet ihre Unterlistesums
und fügt diese in eine Karte ein, die sich auch an das erste Element der Liste erinnert. Wenn derselbe Satz von Summen mehrmals gefunden wird, wird das erste Element durch ersetztNothing
, sodass wir wissen, dass wir nicht nach anderen Wegen suchen müssen, um diese Summen zu erhalten.Die
construct
Funktion sucht nach Listen mit einer bestimmten Länge und einem bestimmten Startwert, die einen bestimmten Satz von Unterlistensummen enthalten. Sein rekursiver Teilconstr
folgt im Wesentlichen der gleichen Logik wie dieser , hat jedoch ein zusätzliches Argument, das die Summe angibt, die die verbleibenden Listeneinträge benötigen. Dies ermöglicht es, frühzeitig zu stoppen, wenn selbst die kleinstmöglichen Werte zu groß sind, um diese Summe zu erhalten, was zu einer massiven Leistungsverbesserung führte. Weitere große Verbesserungen wurden erzielt, indem dieser Test an einen früheren Ort verschoben wurde (Version 2) und die Liste der aktuellen Summen durch eineVector
(Version 3 (defekt) und 4 (mit zusätzlicher Strenge)) ersetzt wurde. Die neueste Version führt den Set-Mitgliedschaftstest mit einer Nachschlagetabelle durch und fügt etwas mehr Strenge und Parallelisierung hinzu.Wenn
construct
eine Liste gefunden wurde, die die Summen der Unterliste angibt und kleiner als die Rückseite ist, könnte sie zurückgegeben werden, aber wir sind nicht wirklich daran interessiert. Es würde fast ausreichen, nur zurückzukehren()
, um seine Existenz anzuzeigen, aber wir müssen wissen, ob wir es zweimal zählen müssen (weil es kein Palindrom ist und wir niemals mit seiner Umkehrung umgehen werden). Also setzen wir 1 oder 2 als seineweight
in die Ergebnisliste.Die Funktion
count
fügt diese Teile zusammen. Für jeden Satz von sublist Summen (ausorig
) , das war einzigartig unter den Listen , die nurs
unds+1
es nenntvalue
, die Anrufeconstruct
und überuniqueval
, prüft , ob es nur ein Ergebnis. Wenn ja, ist dies das Gewicht, das wir zählen müssen, andernfalls war der Satz von Summen nicht eindeutig und Null wird zurückgegeben. Beachten Sie, dass aufgrund von Faulheit aufgehörtconstruct
wird, wenn zwei Ergebnisse gefunden wurden.Die
main
Funktion verarbeitet E / A und die Schleifes
von 1 bis 9.Kompilieren und Ausführen
Auf debian muss diese die Pakete
ghc
,libghc-vector-dev
undlibghc-parallel-dev
. Speichern Sie das Programm in einer Dateiprog.hs
und kompilieren Sie es mitghc -threaded -feager-blackholing -O2 -o prog prog.hs
. Führen Sie mit./prog <n> +RTS -N
wo<n>
ist die Array-Länge, für die wir die eindeutigen Arrays zählen möchten.quelle