Problem Forge
Problema del mes, peldaño 07 Vista previa
Vista previa. Este es el problema del mes de diciembre, abierto antes para que puedas probarlo. La vista previa dura un mes, con sus propios grafos y su propia clasificación. El día 1 la clasificación y todos los cronómetros empiezan vacíos, y nada se conserva. Diciembre empieza con grafos nuevos y una clasificación vacía.
- Vértices: 4000000, numerados del 0 al 3999999.
- Cada par de vértices está unido con probabilidad p = 1/2, cada par por su cuenta.
La regla. Tu grafo está dado por una clave K de 64 dígitos hexadecimales. Los vértices i y j, con i < j, están unidos cuando el primer bit de SHA-256(K, i, j) es 1. Aquí K cuenta como sus 32 bytes, e i y j como números de 8 bytes en big-endian. El archivo tiene la clave en la línea k.
La regla en código, de uso libre (CC0): C, C++, JavaScript. Puedes escribir tu programa antes de mostrar tu clave. El reloj empieza solo entonces.
Tu respuesta. Los n vértices en el orden del ciclo, cada uno exactamente una vez, separados por espacios o saltos de línea. Cada vértice debe estar unido al siguiente, y el último al primero. Se acepta cualquier ciclo así. Escríbelo, o sube un archivo de texto, o un .gz o .tar.gz con ese único archivo.