Según la solicitud de Luke y la adición de Peter Taylor a este desafío.
Introducción
Todos conocen el juego de tres en raya, pero en este desafío, vamos a introducir un pequeño giro. Solo vamos a usar cruces . La primera persona que coloca tres cruces seguidas pierde. Un hecho interesante es que la cantidad máxima de cruces antes de que alguien pierda, es igual a 6 :
X X -
X - X
- X X
Eso significa que para un tablero de 3 x 3, la cantidad máxima es 6 . Entonces, para N = 3, necesitamos generar 6.
Otro ejemplo, para N = 4, o un tablero de 4 x 4:
X X - X
X X - X
- - - -
X X - X
Esta es una solución óptima, puede ver que la cantidad máxima de cruces es igual a 9 . Una solución óptima para una placa de 12 x 12 es:
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
Esto da como resultado 74 .
La tarea
Su tarea es calcular los resultados lo más rápido posible. Ejecutaré su código en el caso de prueba 13
. Esto se hará 5 veces y luego se tomará el promedio de los tiempos de ejecución. Ese es tu puntaje final. Cuanto más bajo, mejor.
Casos de prueba
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
Se puede encontrar más información en https://oeis.org/A181018 .
Reglas
- Este es el código más rápido , por lo que gana la presentación más rápida.
- Debe proporcionar un programa completo .
- Indique también cómo tengo que ejecutar el programa. No estoy familiarizado con todos los lenguajes de programación y cómo funcionan, así que necesito un poco de ayuda aquí.
- Por supuesto, su código necesita calcular el resultado correcto para cada caso de prueba.
Presentaciones:
- Feersum (C ++ 11): 28s
- Peter Taylor (Java): 14m 31s
Respuestas:
C ++ 11, 28s
Esto también utiliza un enfoque de programación dinámica basado en filas. Me tomó 28 segundos correr con el argumento 13 para mí. Mi truco favorito es la
next
función que utiliza un poco de bashing para encontrar la disposición lexicográfica de la siguiente fila que satisface una máscara y la regla de no 3 en fila.Instrucciones
g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
<executable name> <n>
fuente
Java, 14m 31s
Este es esencialmente el programa que publiqué en OEIS después de usarlo para extender la secuencia, por lo que es una buena referencia para otras personas. Lo modifiqué para tomar el tamaño del tablero como el primer argumento de la línea de comandos.
Guardar
A181018.java
; compilar comojavac A181018.java
; correr comojava A181018 13
. En mi computadora, se tarda unos 20 minutos en ejecutar esta entrada. Probablemente valdría la pena ponerlo en paralelo.fuente
n=16
; Extrapolé que tomaría alrededor de un mesn=17
, así que no intenté ejecutarlo para eso. El uso de la memoria también se estaba convirtiendo en una molestia importante. (PD: Actualmente estoy usando 2 de mis 4 núcleos para un desafío de programación que no es PPCG: azspcs.com/Contest/Tetrahedra/Standings )