To analyze this code, let's apply some transformations:
Correcting the indentation.
Place variable declarations in the smallest possible scope.
-
The variable tam
can be declared where it receives numero
. And this statement can be moved to stay just before while (tam != 1)
.
-
The variables numero
and pulo
can be declared immediately before the scanf
that reads them.
-
The variable indice
can be declared in the place where zero is assigned to it.
-
Variables i
can be declared in for
where they are used.
-
The variable posi
is only used in while
of removeElem
. Its value is always set to zero before this while
is executed. So we can move your statement to stay immediately before this while
. This way, while
looks like this:
int posi = 0;
while (cont != pulo) {
removeElem(vetor, &posi, &tam, &cont);
}
-
The variable cont
is set to zero before the while
of the removeNum
where it is used and set to zero again before the while
of the removeElem
where it is used. In this way, we can exchange for two different variables each declared before their respective while
.
int indice = 0, conta = 0;
while (indice != pulo - 1) {
removeNum(vetor, &conta, &tam, &indice);
}
int contb = 0, posi = 0;
while (cont != pulo) {
removeElem(vetor, &posi, &tam, &contb);
}
We can copy and paste the body of functions removeElem
, removeNum
and carregaVetor
back to main
to make it easier for us to parse and debug the code. The variables i
of carregaVetor
and removeElem
are renamed to j
so as not to collide with i
already in main
. References and dereferences to pointers are eliminated. The result so far is this:
for (int j = 0; j < numero; j++) {
vetor[i] = j + 1;
}
int tam = numero;
while (tam != 1) {
int indice = 0, conta = 0;
while (indice != pulo - 1) {
tam++;
vetor[tam] = vetor[indice];
conta++;
indice++;
}
int contb = 0, posi = 0;
while (contb != pulo) {
for (int j = posi; j < tam; j++) {
vetor[j] = vetor[j + 1];
}
tam--;
contb++;
}
}
Note that the posi
variable always has a value of zero. In fact, the removeElem
function read its value from its address, but never wrote in it. So you can delete this variable.
Note that the variable conta
(which is the cont
of your original code when used in while
of removeNum
) always has the same value of indice
and its value never is used for nothing. Therefore, it can be deleted.
We can rewrite the two while
s above (those of removeElem
and removeNum
) as for
loops. The first uses the variable indice
as the counter and the second uses contb
.
Your while (scanf("%d", &teste) != EOF)
will only (or should be) run once. In this case, it is not necessary to use while
, just use scanf
alone. Your problem also does not need to consider malformed entries where the number of NC
of the problem statement would not be reported or something, so you do not need to check the return of scanf
.
Your while (tam != 1)
looks like this:
while (tam != 1) {
for (int indice = 0; indice != pulo - 1; indice++) {
tam++;
vetor[tam] = vetor[indice];
}
for (int contb = 0; contb != pulo; contb++) {
for (int j = 0; j < tam; j++) {
vetor[j] = vetor[j + 1];
}
tam--;
}
}
-
Note that tam++
will be executed a number of times that is exactly pulo - 1
. So you can put tam += pulo - 1
after this for
and replace vetor[tam]
with vetor[tam + indice]
.
-
The variable tam
is decremented whenever contb
is incremented. At this point it is possible to conclude that it will be decremented contb
times and it is possible to put tam -= pulo
after for
of contb
. The value of tam
in the loop j
can be substituted for tam - contb
. At this point we'll have this in the code:
tam += pulo - 1;
for (int contb = 0; contb != pulo; contb++) {
for (int j = 0; j < tam - contb; j++) {
vetor[j] = vetor[j + 1];
}
}
tam -= pulo;
-
We can then change the tam
of the loop from j
to tam + pulo - 1
, delete tam += pulo - 1;
and change tam -= pulo;
to tam--;
.
-
With this, we can finally change the while (tam != 1)
by a for
loop.
The resulting code looks like this:
#include <stdio.h>
int main(int argc, char** argv) {
int vetor[90000];
int teste;
scanf("%d", &teste);
for (int i = 0; i < teste; i++) {
int numero, pulo;
scanf("%d %d", &numero, &pulo);
for (int j = 0; j < numero; j++) {
vetor[j] = j + 1;
}
for (int tam = numero; tam != 1; tam--) {
for (int indice = 0; indice != pulo - 1; indice++) {
vetor[tam + indice] = vetor[indice];
}
for (int contb = 0; contb != pulo; contb++) {
for (int j = 0; j < tam + pulo - 1 - contb; j++) {
vetor[j] = vetor[j + 1];
}
}
}
printf("Case %d: %d\n", i + 1, vetor[0]);
}
return 0;
}
Looking at the resulting code, we see that it has a high complexity since we have for
within a for
within a for
within a for
. The operation that is executed a greater number of times is the vetor[j] = vetor[j + 1];
that is intended to remove an element from the middle of the vector and to move all subsequent elements. In the indice
loop, the vetor[tam + indice] = vetor[indice];
statement is also deleting elements from the middle of the vector.
Vectors are not structures that count on removing elements in the middle as something efficient to do, so it would be best to look for a data structure that has such a characteristic, which suggests that the ideal solution would be done through of dynamically linked (and perhaps circular) lists.