TOPIC

PROBLEM 1285 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Erick Ricardo Budal replied 2 years ago

    Muito obrigado pela ajuda! Consegui resolver.

  • Unknown replied 2 years ago

    [size=150:1gfpkvft]Time Limit[/size:1gfpkvft] Para uma entrada como:

    1 5000
    1 5000
    1 5000
    1 5000
    1 5000

    Se, em cada caso de teste, você tiver que fazer 5000 conversões para string, e analisar em quase strlen²/2 iterações, certamente dá TLE!

    [size=150:1gfpkvft]Otimizando[/size:1gfpkvft] [list:1gfpkvft][:1gfpkvft]5000 números é uma quantidade bem pequena de elementos. Que tal então fazer o "trabalho pesado" uma vez apenas para cada número nesse intervalo?  [/:m:1gfpkvft] [:1gfpkvft]É mesmo necessário converter um número em string, para detectar dígitos duplicados?[/:m:1gfpkvft][/list:u:1gfpkvft]

  • Erick Ricardo Budal replied 3 years ago

    Tá dando Time limit exceeded. Alguém pode me ajudar? Como posso otimizar?

    #include <iostream>
    #include <sstream>
    
    using namespace std;
    
    int main()
    {
        int n, m, cont;
        string number;
        bool achou;
    
        while(cin >> n >> m){
            cont = 0;
            for(int i=n; i<=m; i++){
    
                //Convertendo o número atual em uma string
                stringstream convertendo;
                convertendo << i;
                number = convertendo.str();
    
                //Percorrendo a string para ver se tem dígitos repetidos
                achou = false;
                for(int j=0; j<number.length(); j++){
                    for(int k=0; k<number.length(); k++){
                        if(number[j] == number[k] && j != k){
                            //Se achar apenas um dígito repetido, dar BREAK nos dois FOR LOOPS
                            achou = true;
                            break;
                        }
                    }
                    if(achou){
                        break;
                    }
                }
                //Incrementa o contador apenas se não for número com dígitos repetidos
                if(!achou){
                    cont++;
                }
            }
            cout << cont << endl;
        }
    
        return 0;
    }
  • Rã Solo e o código em python replied 3 years ago

    Uma maneira simples de verificar se existem dígitos repetidos é trabalhar com string.

    Um dica para resolver o problema: "E se você soubesse quantos números tem dígitos distintos de 1 até x, onde x é um inteiro qualquer dentro do intervalo [1, 5000] ? "

  • Marco Antônio de Almeida Fernandes replied 4 years ago

    Gostaria de entender isso.. Abaixo o primeiro código, não funciona corretamente, porem dá 40 % de erro. O segundo código funciona perfeitamente, fiz vários testes, porém de 100% de erro.. Alguém pode me dar um help ?

    -----CÓDIGO 1 - 100% DE ERRO------
    #include <stdio.h>
    
    int main() {
    
        int N, M;
        int cont, a, b, c, d, aux, div, auxM, auxN, menorvalor;
        while(scanf("%d %d", &N, &M) != EOF)
        {
            cont = 0;
            if(M != N)
            {
                    if(N < M)
                        N = N - 1;
                    else
                        M = M - 1;
                do
                {
                    if(N < M)
                    {
                        N++;
                        menorvalor = N;
                    }
                    else
                    {
                        M++;
                        menorvalor = M;
                    }
                    auxN = N;
                    auxM = M;
                    aux = 0;
                    do
                    {
                        aux ++;
                        if(N <= M)
                        {
                            div = auxN%10;
                            auxN = auxN/10;
                        }
                        else if(N >= M)
                        {
                            div = auxM%10;
                            auxM = auxM/10;
                        }
    
                        if(menorvalor < 100)
                        {
                            if(aux == 1)
                            a = div;
                            else if(aux == 2)
                                b = div;
                        }
                        else if(menorvalor < 10)
                        {
                            if(aux == 1)
                                a = div;
                            else if(aux == 2)
                                b = div;
                        }
                        else if(menorvalor < 1000)
                        {
                            if(aux == 1)
                            a = div;
                            else if(aux == 2)
                                b = div;
                            else if(aux == 3)
                                c = div;
                        }
                        else
                        {
                            if(aux == 1)
                            a = div;
                            else if(aux == 2)
                                b = div;
                            else if(aux == 3)
                                c = div;
                            else if(aux == 4)
                                d = div;
                        }
    
                    }while(aux != 4);
                   if(menorvalor < 10)
                   {
                       if(a!= b)
                        {
                            cont++;
                        }
                   }
                   else if(menorvalor < 100)
                   {
                       if(a != b)
                       {
                           cont++;
                       }
                   }
                   else if(menorvalor < 1000)
                   {
                       if(a!= b && a != c && b!=c)
                       {
                           cont++;
                       }
                   }
                   else
                   {
                       if(a!= b && a != c && a != d && b!=c && b != d && c != d)
                       {
                           cont++;
                       }
                   }
    
            }while(N != M);
            }
            else
            {
                cont = 1;
            }
            printf("%d\n",cont);
        }
    
        return 0;
    }
    
    ------CÓDIGO 2 - 40% DE ERRO ------
    #include <stdio.h>
    
    int main() {
    
        int N, M;
        int cont, a, b, c, d, aux, div, auxM, auxN, menorvalor;
        while(scanf("%d %d", &N, &M) != EOF)
        {
            cont = 0;
            if(M != N)
            {
                    if(N < M)
                        N = N - 1;
                    else
                        M = M - 1;
                do
                {
                    if(N < M)
                    {
                        N++;
                        menorvalor = N;
                    }
                    else
                    {
                        M++;
                        menorvalor = M;
                    }
                    auxN = N;
                    auxM = M;
                    aux = 0;
                    do
                    {
                        aux ++;
                        if(N <= M)
                        {
                            div = auxN%10;
                            auxN = auxN/10;
                        }
                        else if(N >= M)
                        {
                            div = auxM%10;
                            auxM = auxM/10;
                        }
    
                        if(menorvalor < 100)
                        {
                            if(aux == 1)
                            a = div;
                            else if(aux == 2)
                                b = div;
                        }
                        else if(menorvalor < 10)
                        {
                            if(aux == 1)
                                a = div;
                            else if(aux == 2)
                                b = div;
                        }
                        else if(menorvalor < 1000)
                        {
                            if(aux == 1)
                            a = div;
                            else if(aux == 2)
                                b = div;
                            else if(aux == 3)
                                c = div;
                        }
                        else
                        {
                            if(aux == 1)
                            a = div;
                            else if(aux == 2)
                                b = div;
                            else if(aux == 3)
                                c = div;
                            else if(aux == 4)
                                d = div;
                        }
    
                    }while(aux != 4);
    
                   if(a!= b && a != c && a != d && b!=c && b != d && c != d)
                    {
                        cont++;
                    }
    
            }while(N != M);
            }
            else
            {
                cont = 1;
            }
            printf("%d\n",cont);
        }
    
        return 0;
    }
  • Andressa Julio replied 4 years ago

    Boa tarde!

    No teste usando DEV c++, o código não apresenta erros. Porém, na submissão no URI, acontece wrong 100%. Poderiam ajudar?

    #include <stdio.h>
    
    int main(){
        int n, m, i, j, k, nume[10], num, digitos, num_atual, pos_atual, repetidos, tot_num, repetiu; 
    
        while(scanf("%d %d", &n, &m) != EOF){
            if(n == m){
                printf("1\n");
                continue;
            }
    
            tot_num = m-n+1;   
            repetidos = 0;
    
            for(i=n; i<=m; i++){
                num = i;
                j=0;
                while(num>0){
                    nume[j] = num % 10;
                    num = num / 10;
                    j++;
                }
    
                digitos = j;
                repetiu = 0;
                pos_atual = 0;
    
                while(!repetiu){
                    num_atual = nume[pos_atual];
                    for(k=0; k<digitos; k++){
                        if(nume[k] == num_atual && k != pos_atual){
                            repetidos++;
                            repetiu = 1;
                            break;
                        }
                    }
                    if(pos_atual == digitos-1)
                        break;
                    pos_atual = pos_atual+1;
                }
            }
            printf("%d\n",tot_num-repetidos);
        }
        return 0;
    }
  • Rodrigo Barbosa da Silva replied 4 years ago

    William, vi que quando vc compara se s numeros são iguais já coloca o "1\n, porém eles podem ser iguais, mas repetidos, então tem que dar 0, exemplo: 55 55 são iguais porém repetidos, no seu codigo isso da 1

  • William Almeida Suzukayama replied 4 years ago

    WA 100%

    #include<stdio.h>
    
    int main(){
        int n,m,i,j,k,numero[10],num,digitos,numero_atual,posicao_do_atual,repetidos,total_de_numeros,ja_repetiu;  
    
        while(scanf("%d %d",&n,&m) != EOF){
            if(n == m){
                printf("1\n");continue;
            }
    
            total_de_numeros = m-n+1;   
            repetidos = 0;
    
            for(i=n;i<=m;i++){
                num = i;
                j=0;
                while(num>0){
                    numero[j] = num%10;
                    num = num / 10;
                    j++;
                }
                digitos = j;
                ja_repetiu = 0;
                posicao_do_atual = 0;
                while(!ja_repetiu){
                    numero_atual = numero[posicao_do_atual];
                    for(k=0;k<digitos;k++){
                        if(numero[k] == numero_atual && k != posicao_do_atual){
                            repetidos++;
                            ja_repetiu = 1;
                            break;
                        }
                    }
                    if(posicao_do_atual == digitos-1)
                        break;
                    posicao_do_atual = posicao_do_atual+1;
                }
            }
            printf("%d\n",total_de_numeros-repetidos);
        }
    
    }
  • Rodrigo Fabiam replied 5 years ago

    Pessoal, Fiz o codigo e as respostas estão batendo com o toolkit. Porem esta dando WA. Alguem saberia me ajudar em como eu posso identificar o que esta saindo errado?