Gemäß Lukes Bitte und Peter Taylors Hinzufügung zu dieser Herausforderung.
Einführung
Jeder kennt das Spiel Tic-Tac-Toe, aber bei dieser Herausforderung werden wir eine kleine Wendung einführen. Wir werden nur Kreuze verwenden . Die erste Person, die drei Kreuze hintereinander platziert, verliert. Eine interessante Tatsache ist, dass die maximale Anzahl an Kreuzen, bevor jemand verliert, gleich 6 ist :
X X -
X - X
- X X
Das bedeutet, dass für eine 3 x 3-Platine der maximale Betrag beträgt 6 . Für N = 3 müssen wir also 6 ausgeben.
Ein weiteres Beispiel für N = 4 oder eine 4 x 4-Karte:
X X - X
X X - X
- - - -
X X - X
Dies ist eine optimale Lösung. Sie können sehen, dass die maximale Anzahl von Kreuzen 9 beträgt . Eine optimale Lösung für eine 12 x 12-Platine ist:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X
Dies ergibt 74 .
Die Aufgabe
Ihre Aufgabe ist es, die Ergebnisse so schnell wie möglich zu berechnen. Ich werde Ihren Code für den Testfall ausführen13
. Dies wird 5 Mal durchgeführt und dann wird der Durchschnitt der Laufzeiten ermittelt. Das ist dein Endergebnis. Je niedriger, desto besser.
Testfälle
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
10 52
11 64
12 74
13 86
14 100
15 114
Weitere Informationen finden Sie unter https://oeis.org/A181018 .
Regeln
- Dies ist der schnellste Code , also gewinnt die schnellste Einreichung!
- Sie müssen ein vollständiges Programm bereitstellen .
- Bitte geben Sie auch an, wie ich das Programm ausführen muss. Ich bin nicht mit allen Programmiersprachen vertraut und weiß nicht, wie sie funktionieren. Deshalb brauche ich hier ein bisschen Hilfe.
- Natürlich muss Ihr Code für jeden Testfall das richtige Ergebnis berechnen .
Einsendungen:
- Feersum (C ++ 11): 28s
- Peter Taylor (Java): 14 m 31 s
Antworten:
C ++ 11, 28s
Dies verwendet auch einen dynamischen Programmieransatz, der auf Zeilen basiert. Es dauerte 28 Sekunden, bis ich mit Argument 13 lief. Mein Lieblingstrick ist die
next
Funktion, die ein bisschen Bashing verwendet, um die lexikografisch nächste Zeilenanordnung zu finden, die eine Maske und die Regel Nr. 3 in einer Reihe erfüllt.Anleitung
g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
<executable name> <n>
quelle
Java, 14m 31s
Dies ist im Wesentlichen das Programm, das ich bei OEIS gepostet habe, nachdem ich es zum Erweitern der Sequenz verwendet habe. Es ist also eine gute Referenz für andere Leute, die es zu schlagen gilt. Ich habe es so angepasst, dass die Boardgröße als erstes Befehlszeilenargument verwendet wird.
Speichern unter
A181018.java
; kompilieren alsjavac A181018.java
; laufen alsjava A181018 13
. Auf meinem Computer dauert die Ausführung dieser Eingabe ungefähr 20 Minuten. Es wäre wahrscheinlich eine Parallelisierung wert.quelle
n=16
. Ich habe hochgerechnet, dass es ungefähr einen Monat dauern würden=17
, also habe ich nicht versucht, es dafür auszuführen. Die Speichernutzung wurde ebenfalls zu einem großen Ärgernis. (PS Ich verwende derzeit 2 meiner 4 Kerne für eine Nicht-PPCG-Programmierherausforderung: azspcs.com/Contest/Tetrahedra/Standings )