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:
- em "fenício-português", a saída é invertida
- no seu problema, você precisa se preocupar com o caso de apagar todas as informações
- 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:
- o argumento numérico que você passa
- 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.