|
|
Problema A - Trinta e três |
Tipo de problema: Matemática / Ad-hoc
Autor do Problema: Pedro Ribeiro (DCC/FCUP)
Problema:
Qual o n-ésimo número que possui C dígitos A?
Restrições:
1 <= A <= 9.
1 <= C <= 9.
1 <= Ni <= 1 000 000 000.
1 <= Si <= 2 000 000 000.
1 <= Q <= 1 000.
Solução base:
Para cada pedido, percorrer todos os números desde 1 até encontrar o ao número pedido, ou seja, verificar o número de ocorrências do dígito A e imprimir o N-ésimo que respeite a condição.
Esta solução daria aproximadamente 40 pontos.
Melhorar:
Uma vez que são Q pedidos e estamos a fazer o ciclo desde 1 até ao número pedido, podemos receber todos os pedidos, ordená-los e fazer um único ciclo que responde a todos os pedidos. Assim, cada número é verificado apenas uma vez.
Esta solução daria aproximadamente 60 pontos.
Necessitamos de ter cuidado porque devemos responder aos pedidos pela ordem que são feitos.
Saltar por ordem
O próximo patamar estava reservado para aqueles programas que conseguem iterar não pelos números a testar, mas gerar automaticamente qual o número seguinte.
O primeiro passo passa por determinar quantos digitos tem o número pedido. De seguida, determinar o menor número com esse número de digitos que respeita as restriçães dadas, usando este como ponto de partida para gerar os próximos números da sequência. O algoritmo para gerar o próximo número é semelhante ao next permutation e deixamos como exercício.
É uma solução que requer uma programação cuidada pois existem diversos casos a considerar. Esta solução daria aproximadamente 80 pontos.
Calcular o número
Considere-se a matriz
c[D][O] = K
D - número de dígitos
O - número de ocorrências do número pedido
K - quantidade de números que respeitam a condição
Conseguimos descobrir o número de dígitos necessários através desta matriz muito facilmente.
Olhando para o valor de c[D-1][O] sabemos o número de elementos possíveis com menos um dígito. Desta forma, conhecemos o dígito da esquerda.Temos que ter cuidado porque podemos precisar de verificar c[D-1][O-1], caso o dígito que vamos considerar seja A.
Ligações interessantes: