This is a competitive programming problem. Whoever does this kind of problem knows which algorithm you need to use to solve it. And try to row against the current, solve the problem in a different way than the original design will result in waste of time or miserable failure.
A waste of time happens when you try to kill flies with bazookas. For example, in a competition within the college, the proof director elaborated a question to search for one string within the other. The problem was similar to this, but I could use the library string.h. My team spent a lot of time on it, implementing the search for substring KMP, when those who prepared the proof simply wanted a strstr like the @Isac noted in his reply.
The pitiful flaw is when you try to kill dragons with fly swatters. See that question and my answer to realize that any solution other than Pisano sequence will not return in a timely manner.
Before I address your question, I’m going to talk about a competitive scheduling issue that my crew and I created to stimulate college freshmen.
Phoenician-Portuguese
Rudy, associate of Uece, Union of Students of Epic Cultures, was researching
in a Portuguese tomb and found a tablet with characters similar to
found in the fourteenth century Portuguese alphabet. As a good researcher, he realized
that there were no vowels in these scriptures, as soon as he realized that it was a culture
residual expertise in that area. After much study, he realized that this was one of the
first forms of writing that appeared in Portugal, with reports of similar writing
in Lisbon.
As the tablet, even putting vowels in words, remained illegible, Rudy theorized that the "Phoenician-Portuguese" read their writings from right to left.
You, as Rudy’s good friend and programmer, volunteered to help his friend in
his research, transforming words from our writing into Phoenician-Portuguese writing.
Example of input/output
thiago | ght
maratona | ntrm
kiwi | wk
Notice any resemblance to your problem? Yes, it’s almost the same thing. You read information and return it after doing some deletions. There are three differences between the issues:
- in "Phoenician-English", the output is reversed
- in your problem, you need to worry about the case of erasing all information
- in "Phoenician-English", there are 5 characters to be removed, instead of only 1
Tips from the person who wrote the question
The author of the question is very aware of what he wants. So he already makes it clear to the competitors what kind of information he has. In this case, we have to 1 <= N <= 10^100. This absurd size is the tip he left.
To represent this number, how many bits would it take? Well, just apply the log2 number, right? That would be 100 * log2(10), but we are talking about competitive programming and we cannot spend time calculating the log2.
We know that 10^3 ~~ 2^10, then 10^100 ~~ (10^3)^33. Thereby, 10^100 ~~ (10^3)^33 ~~ (2^10)^33 = 2^330. That is, around 330 bits. Well, you will have a hard time trying to assemble your own whole type with that size...
Or we can treat it as a word processing problem. Simple as that. Where’s the math? Doesn’t matter much, arithmetic isn’t around.
All you need to do is turn one string into another. All you need to do is read the entire line, separate the first character that is the character to be ignored, skip the space, and then process the rest of the line, down to the \n.
To read a line, you can use the fgets. The number of characters to be read is limited by two factors:
- the numerical argument you pass
- find an EOL
Read more about fgets; here too
In this case, the format of the input is:
- a digit character
- a space
- between 1 and 100 digit characters
- the line break
\n
Then the fgets limited to 1+1+100+1 and the null terminator \0 is enough to read any line of the given problem. Therefore, fgets(entrada, 104, stdin) makes the entrance perfectly.
After that, we will process the characters from entrada[2] until you find the line break.
The processing to be done is: if the character is distinct from entrada[0], prints this character. And only this. As the intention is to read until you find an index i such that entrada[i] == '\n', so we can iterate this way here:
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++;
}
We still have to define what this character print routine would look like. So, come on? Print this character?
Since we’re dealing with competitive programming, we don’t need to miss performance with poorly made I/O. Then the best is to bufferize my output and print a single string. How? So:
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);
It seems all quiet, but has not yet dealt with the special case: when it is asked to ignore a digit and the following string is composed exclusively of that digit. In this case, you should print a line with only the character '0' on it:
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");
}
Well, now we’re missing the zeros print cases left, which should be avoided... If by any chance entrada[i] == '0' and j == 0, then I must not allow this value to be entered:
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");
}
I can simplify this logic at one point yet: it does not need two conditionals one within the other. The previous example was merely illustrative. I can also use !j, since in C the value 0 is already untrue:
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");
}
Okay, finished algorithm. But to fully solve the issue, we need to identify when the question stopped. And the stop condition is: the given digit D that will be ignored is '0'. So it looks something like this:
#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");
}
}
}
If by chance it is required that the C used is ANSI-C 89, then the declaration of variables needs to be in block start.