O recente terremoto em Nlogônia não chegou a afetar muito as edificações da capital, principal epicentro do abalo. Mas os cientistas detectaram que o principal dique de contenção teve um dano significativo na sua parte subterrânea que, se não for consertado rapidamente, pode causar o seu desmoronamento, com a consequente inundação de toda a capital.
O conserto deve ser feito por mergulhadores, a uma grande profundidade, em condições extremamente difíceis e perigosas. Mas como é a sobrevivência da própria cidade que está em jogo, seus moradores acudiram em grande número como voluntários para essa perigosa missão.
Como é tradicional em missões perigosas, cada mergulhador recebeu no início do mergulho uma pequena placa com um número de identificação. Ao terminar o mergulho, os voluntários devolviam a placa de identificação, colocando-a em um repositório.
O dique voltou a ser seguro, mas aparentemente alguns voluntários não voltaram do mergulho. Você foi contratado para a penosa tarefa de, dadas as placas colocadas no repositório, determinar quais voluntários perderam a vida salvando a cidade.
Entrada
A entrada contém vários casos de teste e termina com EOF. Cada caso de teste é composto de duas linhas. A primeira linha contém dois inteiros N e R ( 1 ≤ R ≤ N ≤ 104), indicando respectivamente o número de voluntários que mergulhou e o número de voluntários que retornou do mergulho. Os voluntários são identificados por números de 1 a N. A segunda linha da entrada contém R inteiros, indicando os voluntários que retornaram do mergulho (ao menos um voluntário retorna do mergulho).
Saída
Seu programa deve produzir uma única linha para cada caso de teste, contendo os identificadores dos voluntários que não retornaram do mergulho, na ordem crescente de suas identificações. Deixe um espaço em branco após cada identificador (note que isto significa que deve haver um espaço em branco também após o último identificador). Se todos os voluntários retornaram do mergulho, imprima apenas o caractere ‘*’ (asterisco).
| Entrada | Saída |
| 5 3 3 1 5 6 6 6 1 3 2 5 4 |
2 4 * |
A solução apresentada definiu um vetor de 10001 posições. Isso porque o enunciado disse que a entrada teria um valor de N ≤ 104. Veja que 104 = 1000 e entre 0 e 1000 existem 10001 números inteiros.
#include<stdio.h>
int main(){
int n, r, i, idVoluntario, v[10001]; //10001 = 10^4+1 (porque é menor igual)
while(scanf("%i %i",&n, &r) != EOF) {
//zera o vetor (somente a parte que interessa)
for(i=0; i<=n; i++) {
v[i] = 0;
}
//lê os identificadores dos voluntários
for(i=0; i<r; i++) {
scanf("%i",&idVoluntario);
v[idVoluntario] = 1;
}
//resolve o enunciado
if(n==r) { //mergulharam o mesmo número de voluntários que voltaram
printf("*\n");
} else{
for(i=1; i<=n ; i++){
if(v[i]==0) {
printf("%i ", i);
}
else{
v[i]=0;
}
}
printf("\n");
}
}
return 0;
}
Teste o código: http://ideone.com/X4PMIF
Dica de melhoria
A solução envolve encontrar os números inteiros de 1 a N que não aparecem na entrada. O problema foi resolvido utilizando um vetor com N posições para identificar os números que apareceram na entrada. Quando o valor i é informado, foi alterado o valor do vetor nesse índice para 1. Com isso, a complexidade de tempo desse algoritmo é O(N). Em linguagem C++, é possível utilizar o std::set que faz inserções e busca em complexidade de tempo O(log N). Com isso, é possível obter uma solução com complexidade de O(N.log N).