Problem Forge
Problème du mois, échelon 06 Aperçu
Aperçu. Voici le problème du mois de décembre, ouvert en avance pour que vous puissiez l'essayer. L'aperçu dure un mois, sur ses propres graphes et son propre classement. Le 1er, le classement et tous les chronos repartent de zéro, et rien n'est conservé. Décembre commence avec de nouveaux graphes et un classement vide.
- Sommets : 1000000, numérotés de 0 à 999999.
- Chaque paire de sommets est reliée avec la probabilité p = 1/2, chaque paire indépendamment des autres.
La règle. Votre graphe est donné par une clé K de 64 chiffres hexadécimaux. Les sommets i et j, avec i < j, sont reliés quand le premier bit de SHA-256(K, i, j) vaut 1. Ici, K compte comme ses 32 octets, et i et j comme des nombres de 8 octets en big-endian. Le fichier contient la clé sur la ligne k.
La règle en code, libre d'utilisation (CC0) : C, C++, JavaScript. Vous pouvez écrire votre programme avant d'afficher votre clé. Le chrono ne démarre qu'à ce moment-là.
Votre réponse. Les n sommets dans l'ordre du cycle, chacun exactement une fois, séparés par des espaces ou des retours à la ligne. Chaque sommet doit être relié au suivant, et le dernier au premier. Tout cycle de ce genre est accepté. Tapez-le, ou envoyez un fichier texte, ou un .gz ou un .tar.gz de ce seul fichier.