PKU 2381 - Random Gap

Autor da análise: pivapiva

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2381

Resumo

Dados, $a$, $R0$, $c$ e $m$, e um gerador de números com a seguinte propriedade $R[n] = (a*R[n - 1] + c)%m$, devolver a maior diferença entre dois números gerados tal que não exista nenhum outro número entre eles.

Solução

Notamos inicialmente que $m <= 16*10^6$. Pelo princípio da casa dos pombos, só podemos gerar $16*10^6$ números distintos, o que é pequeno e rápido de ser gerado. Note que pelo enunciado, não precisamos usar long long (o que pode dar TLE, já que operações com long long são mais demoradas), basta gerar usando $R[n] = ((A*R[n-1])%m + c%m) %m$ (mod é distributivo).

Agora nos resta apenas usar uma estrutura tal que consigamos achar o valor pedido em tempo linear. Podemos usar um vetor booleano $V$ (inicialmente todo falso) e conforme geramos os números $R[i]$, marcamos $V[ R[i] ] = true$. Assim que gerarmos um $R[i]$ tal que $V[ R[i] ] == true$, podemos parar. Depois, é só percorrer o vetor mantendo o índice do último número gerado e ir atualizando a resposta.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License