1285 - Dígitos Diferentes
Como pré-calcular resultados para ter uma resposta rápida do computador.
Descrição
Solução
Uma maneira simples e viável de resolver este problema é, para cada intervalo, fazer um looping de cada número perguntando no intervalo, perguntando se ele tem dígito repetido e contando caso não tenha. Com essa abordagem, é fácil perceber que durante para vários casos de teste, vamos ter que verificar diversas vezes se o mesmo número tem dígitos repetidos diversas vezes.
Para mitigar isso, é mais fácil perguntar logo se todos os números entre 1 e 5000 têm dígitos repetidos e guardar em um vetor a quantidade de números repetidos entre 0 e 5000 baseado nas respostas que for encontrando. Com isso, teremos um vetor onde para qualquer índice i
teremos a informação de quantos números com dígitos não repetidos tem entre 0
e i
, inclusive. Logo, para vermos quantos números com dígitos não repetidos existem entre a e b, basta diminuirmos o valor do índice b
pelo valor do índice a - 1
(para conseguirmos a quantidade de números não repetidos entre a
e b
).
Repare que só precisamos fazer esse cálculo geral uma vez, o que nas implementações abaixo é feito executando no começo de tudo a função preCalcula()
. Uma vez calculado, só precisamos acessar o vetor resposta
.
#include <string.h>
#include <stdio.h>
int resposta[5001];
int repetido(int n){
int digitos[10];
memset(digitos, 0, sizeof(digitos));
while(n){
if(digitos[n%10]) return 1;
digitos[n%10] += 1;
n /= 10;
}
return 0;
}
void preCalcula(){
memset(resposta, 0, sizeof(resposta));
for(int i = 1; i < 5001; ++i){
resposta[i] = resposta[i - 1];
if(!repetido(i)) resposta[i] += 1;
}
}
int digitosDiferentes(int a, int b){
return resposta[b] - resposta[a - 1];
}
int main(){
int N, M;
preCalcula();
while(scanf("%d %d", &N, &M) != EOF){
printf("%d\n", digitosDiferentes(N, M));
}
return 0;
}
Last updated
Was this helpful?