Final ONI 2004: Problema C - Em busca dos números perdidos

O último problema da final das ONI 2004 é bem mais interessante do que os outros. Este problema chama-se Em busca dos números perdidos.

Neste problema, são-nos dados 2 números parcialmente definidos, e.g. "?3" e "?", e temos de determinar quantas maneiras possíveis existem de substituir os '?' por um digito 0-9, de modo a que a soma dos 2 números seja um número primo (e.g. "03" + "0" = 3 que é primo).

Os números parcialmente definidos têm até 4 caracteres, i.e. "????" + "????" é um input válido, assim como "1234" + "5678" também. Existem até 100 casos de teste em cada execução.

Análise

Como os números parcialmente definidos, A e B, têm no máximo 4 caracteres, o máximo de casos que teremos de considerar é quando o input é "????" que dá origem a 10 000 números diferentes (0 - 9999). A abordagem natural é combinar os números possíveis de ambos de A e B, e verificar se a sua soma dá um número primo. No entanto, como existem 10 000 números possíveis para cada um, 10 000 * 10 000 = 10⁸, o que é demasiado, como já referi noutro post.

A soma dos 2 números é no máximo 19998. Portanto, só nos interessam os números primos menores ou iguais a 19998. De facto, isto reduz-nos a 2262 primos. Podemos pré-calcular estes primos.
Para determinarmos os primos, podemos usar algo como o Crivo de Eratóstenes. Aproveitamos também para marcarmos num array se o número i (<= 19998) é primo.

Assim, para cada número possível para A, podemos testar para cada primo P se P-A é um número possível de definir com B. Se sim, contabilizamos essa maneira para o resultado.

Para fazermos isto, podemos gerar todos os números possíveis de B e marcá-los num array e_possivel[i].
De seguida fazemos o mesmo para A e para cada número possível, testamos todos os primos P.
Se e_possivel[P-A] for verdade, então contabilizamos mais uma maneira para o resultado.

Esta abordagem reduz o pior caso de 10⁸ para 10 000 * 2262 ~ 22 * 10⁶ o que é um número de iterações muito menor e chega para passar no tempo limite. Volto a lembrar que existem 100 casos de teste por execução, o que poderia tornar o 10⁸ na ordem de 10¹⁰ na verdade.