1

Estou resolvendo o problema 1120 do Uri online judge. O problema consiste em dado um númeno D tal que 1 ≤ D ≤ 9, e um número N tal que 1 ≤ N < 10¹⁰⁰, eu removo toda ocorrência de D em N. Exemplos e casos de teste:

Entradas:

5 5000000  
3 123456  
9 23454324543423  
9 99999999991999999  
7 777  
0 0  

Saídas:(uma linha em braco apos a saída final)

0  
12456  
23454324543423  
1  
0  

Já fiz algumas pesquisas pra tentar resolver o problema,alterei meu código de forma que podia ver os resultados das variáveis a cada execução e nada. Estou sempre recebendo a mensagem de "Wrong answer (90%)".

Os casos de testes dados apresentam respostas idênticas as minhas, mas testando aqui observei que a partir de 20 casas decimais o programa produz resultados inesperados.

Meu código:

/*Esta dando certo pra números de ate 19 dígitos*/

#include<bits/stdc++.h>

#include <math.h>


using namespace std;

int main(){

    int d = 0;
    long long int n = 0, resp = 0;

    while(scanf("%d %lld", &d, &n) && d && n){

        long long int aux = 0;

        for(long long int i = 0; n != 0;){

            //Separo o ultimo número
            aux = n % 10;
            n = n / 10;

            //avalio o número
            if(aux != d){

                resp += ( aux * (int)pow(10, i) );
                i++;
            }

        }//end for

        //Printa a resposta
        printf("%lld\n", resp);
        resp = 0;
    }//end wile

    return 0;
}//end main

OBS: O programa é testado com mais casos de testes que o dado, e diz que o número N pode ser um número grande.

0

1 Resposta 1

6

Esse é um problema de programação competitiva. Quem faz esse tipo de problema sabe qual algoritmo você precisa usar para resolvê-lo. E tentar remar contra a corrente, resolver o problema de um modo distinto do que a concepção original resultará em perca de tempo ou em falha miserável.

A perca de tempo acontece quando você tenta matar moscas com bazucas. Por exemplo, em uma competição dentro da faculdade, o realizador da prova elaborou uma questão para buscar uma string dentro da outra. O problema era semelhante a este, mas podia usar a biblioteca string.h. Minha equipe demorou muito tempo nela, implementando a busca de substring KMP, quando quem elaborou a prova simplesmente queria um strstr como o @Isac observou em sua resposta.

Já a falha miserável é quando você tenta matar dragões com mata-moscas. Veja essa pergunta e minha resposta para perceber que qualquer solução diferente de sequência de Pisano não vai retornar em tempo hábil.


Antes de atacar sua questão, vou falar de uma questão de programação competitiva que eu e meu bando criamos, para estimular os calouros da faculdade.

Fenício-português

Rudy, associado da Uece, União dos Estudantes de Culturas Épicas, estava pesquisando em uma tumba portuguesa e encontrou uma tabuleta com caracteres semelhantes aos encontrados no alfabeto português do século catorze. Como um bom pesquisador, percebeu que não haviam vogais nessas escrituras, tão logo ele percebeu que se tratava de uma cultura residual fenícia naquela área. Depois de muito estudo, ele percebeu que esse foi uma das primeiras formas de escrita que apareceu em Portugal, com relatos de escrita semelhante em Lisboa.

Como a tábua, mesmo colocando vogais nas palavras, permanecia ilegível, Rudy teorizou que os “fenícios-portugueses” liam seus escritos da direita para a esquerda.

Você, como bom amigo do Rudy e programador, se prontificou a ajudar seu amigo em sua pesquisa, transformando palavras da nossa escrita para a escrita fenício-portuguesa.

Exemplo de entrada/saída

thiago       | ght
maratona     | ntrm
kiwi         | wk

Notou alguma semelhança com o seu problema? Sim, é quase a mesma coisa. Você lê uma informação e devolve após fazer algumas remoções. Existem três diferenças entre as questões:

  1. em "fenício-português", a saída é invertida
  2. no seu problema, você precisa se preocupar com o caso de apagar todas as informações
  3. em "fenício-português", são 5 os caracteres a serem removidos, no lugar de apenas 1

Dicas de quem escreveu a questão

O autor da pergunta é muito cônscio do que deseja. Então já deixa claro para os competidores qual o tipo de dados informados. No caso, temos que 1 <= N <= 10^100. Esse tamanho absurdo é a dica que ele deixou.

Para representar esse número, seriam necessários quantos bits? Bem, só aplicar o log2 no número, certo? Isso daria 100 * log2(10), porém estamos falando de programação competitiva e não podemos peder tempo calculando o log2.

Sabemos que 10^3 ~~ 2^10, então 10^100 ~~ (10^3)^33. Com isso, 10^100 ~~ (10^3)^33 ~~ (2^10)^33 = 2^330. Ou seja, por volta de 330 bits. Bem, você vai ter um tempo difícil tentando montar seu próprio tipo inteiro com esse tamanho...

Ou então, podemos tratar como um problema de processamento de texto. Simples assim. Onde está a matemática? Não importa muito, a aritmética não está aqui por perto.

Tudo que você precisa é transformar uma string em outra. Tudo o que precisa é ler a linha inteira, separar o primeiro caracter que é o caracter a ser ignorado, ignorar o espaço, e então processar o resto da linha, até o \n.

Para ler uma linha, você pode usar o fgets. A quantidade de caracteres a serem lidas é limitada por dois fatores:

  1. o argumento numérico que você passa
  2. encontrar um EOL

Leia mais sobre fgets; aqui também

No caso, o formato da entrada é:

  • um caracter dígito
  • um espaço
  • entre 1 e 100 caracteres dígitos
  • a quebra de linha \n

Então o fgets limitado a 1+1+100+1 e o terminador nulo \0 é o suficiente para ler qualquer linha do problema dado. Portanto, fgets(entrada, 104, stdin) faz a entrada perfeitamente.

Após isso, vamos processar os caracteres a partir de entrada[2] até encontrar a quebra de linha.

O processamento a ser feito é: se o caracter for distinto de entrada[0], imprima esse caracter. E somente isso. Como a intenção é ler até encontrar um índice i tal que entrada[i] == '\n', então podemos iterar desse jeito aqui:

char entrada[200]; // sim, posso alocar somente 104, mas 200 é mais bonito 
fgets(entrada, 104, stdin);
int i = 2;

while (entrada[i] != '\n') {
  if (entrada[i] != entrada[0]) {
    imprime(entrada[i]);
  }
  i++;
}

Falta definir como seria essa rotina de imprimir o caracter. Então, vamos lá? Imprimir esse caracter?

Como estamos lidando com programação competitiva, não precisamos perder performance com I/O mal feita. Então o melhor é bufferizar minha saída e imprimir uma única string. Como? Assim:

char entrada[200]; // sim, posso alocar somente 104, mas 200 é mais bonito 
fgets(entrada, 104, stdin);
int i = 2;
int j = 0;
char saida[200];

while (entrada[i] != '\n') {
  if (entrada[i] != entrada[0]) {
    saida[j] = entrada[i];
    j++;
  }
  i++;
}
saida[j] = '\0'; // pondo o terminador nulo para o C tratar como string 
printf("%s\n", saida);

Parece tudo tranquilo, mas ainda não tratou o caso especial: quando se manda ignorar um dígito e a string seguinte é composta exclusivamente desse dígito. Nesse caso, deveria imprimir uma linha apenas com o caracter '0' nela:

char entrada[200]; // sim, posso alocar somente 104, mas 200 é mais bonito 
fgets(entrada, 104, stdin);
int i = 2;
int j = 0;
char saida[200];

while (entrada[i] != '\n') {
  if (entrada[i] != entrada[0]) {
    saida[j] = entrada[i];
    j++;
  }
  i++;
}

// o j só é igual a zero no caso de exceção 
if (j != 0) {
  saida[j] = '\0'; // pondo o terminador nulo para o C tratar como string 
  printf("%s\n", saida);
} else {
  printf("0\n");
}

Bem, agora faltam os casos de impressão de zeros a esquerda, coisa que deveria ser evitada... Se por acaso entrada[i] == '0' e j == 0, então não devo permitir que se insira esse valor:

char entrada[200]; // sim, posso alocar somente 104, mas 200 é mais bonito 
fgets(entrada, 104, stdin);
int i = 2;
int j = 0;
char saida[200];

while (entrada[i] != '\n') {
  if (entrada[i] != entrada[0]) {
    if (j == 0 && entrada[i] == '0') {
      // ignora
    } else {
      saida[j] = entrada[i];
      j++;
    }
  }
  i++;
}

// o j só é igual a zero no caso de exceção 
if (j != 0) {
  saida[j] = '\0'; // pondo o terminador nulo para o C tratar como string 
  printf("%s\n", saida);
} else {
  printf("0\n");
}

Posso simplificar essa lógica em um ponto ainda: não precisa de duas condicionais uma dentro da outra. O exemplo anterior foi meramente ilustrativo. Também posso usar !j, já que em C o valor 0 já é falsidade:

char entrada[200]; // sim, posso alocar somente 104, mas 200 é mais bonito 
fgets(entrada, 104, stdin);
int i = 2;
int j = 0;
char saida[200];

while (entrada[i] != '\n') {
  if (entrada[i] != entrada[0] && !(!j && entrada[i] == '0')) 
    saida[j] = entrada[i];
    j++;
  }
  i++;
}

// o j só é igual a zero no caso de exceção 
if (j != 0) {
  saida[j] = '\0'; // pondo o terminador nulo para o C tratar como string 
  printf("%s\n", saida);
} else {
  printf("0\n");
}

Pronto, algoritmo terminado. Mas, para resolver totalmente a questão, precisamos identificar quando a questão parou. E a condição de parada é: o dígito D informado que será ignorado é '0'. Então fica mais ou menos assim:

#include <stdio.h>

int main() {
  // for (;;) é uma das maneiras de fazer laço infinito
  for (;;) {
    char entrada[200]; // sim, posso alocar somente 104, mas 200 é mais bonito 
    fgets(entrada, 104, stdin);
    // detectando se o dígito D é 0, condição para parar execução do programa
    if (entrada[0] == '0') {
      return 0;
    }
    int i = 2;
    int j = 0;
    char saida[200];

    while (entrada[i] != '\n') {
      if (entrada[i] != entrada[0] && !(!j && entrada[i] == '0')) 
        saida[j] = entrada[i];
        j++;
      }
      i++;
    }

    // o j só é igual a zero no caso de exceção 
    if (j != 0) {
      saida[j] = '\0'; // pondo o terminador nulo para o C tratar como string 
      printf("%s\n", saida);
    } else {
      printf("0\n");
    }
  }
}

Se por acaso for exigido que o C usado seja ANSI-C 89, então a declaração das variáveis precisa estar em começo de bloco.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .