Problem Forge
Problema do mês, degrau 07 Prévia
Prévia. Este é o problema do mês de dezembro, aberto antes para você experimentar. A prévia dura um mês, com grafos próprios e classificação própria. No dia 1, a classificação e todos os cronômetros começam vazios, e nada passa adiante. Dezembro começa com grafos novos e uma classificação vazia.
- Vértices: 4000000, numerados de 0 a 3999999.
- Cada par de vértices é ligado com probabilidade p = 1/2, cada par de forma independente.
A regra. Seu grafo é dado por uma chave K de 64 dígitos hexadecimais. Os vértices i e j, com i < j, são ligados quando o primeiro bit de SHA-256(K, i, j) é 1. Aqui K conta como seus 32 bytes, e i e j como números big-endian de 8 bytes. O arquivo traz a chave na linha k.
A regra em código, de uso livre (CC0): C, C++, JavaScript. Você pode escrever seu programa antes de mostrar sua chave. O cronômetro só começa nesse momento.
Sua resposta. Todos os n vértices na ordem do ciclo, cada um exatamente uma vez, separados por espaços ou quebras de linha. Cada vértice deve estar ligado ao seguinte, e o último ao primeiro. Qualquer ciclo assim é aceito. Digite-o, ou faça upload de um arquivo de texto, ou de um .gz ou .tar.gz só com esse arquivo.