Frequência na aula
Certa vez, numa aula, a professora passou um filme para os alunos assistirem. Durante este filme, ela passou uma lista de presença em sua sala para verificar a presença dos alunos, onde cada aluno deveria inserir apenas seu número de registro. Alguns alunos contudo, como possuem amigos que fogem da aula, decidiram ser camaradas e inseriram os números de registro de seus amigos fujões. O problema é que muitos alunos são amigos de alunos que fogem da aula e alguns números de registro acabaram sendo repetidamente inseridos na lista de presença. Além de tudo, alguns dos alunos que se esperava que não estivessem na aula de fato estavam!
A professora, ao notar que a lista de presença continha alguns números repetidos, ficou sem entender, mas decidiu dar um voto de confiança e dar presença a todos os alunos cujos números de registro estavam na lista. Como são muitos alunos na sala e muitos números com repetição, ela pediu a sua ajuda para determinar o total de alunos que receberam presença na aula.
Entrada
A primeira linha da entrada contém um número inteiro N , que informa a quantidade de números de registro que apareceram na lista de presença. Cada uma das N linhas seguintes contém um número de registro Vi que foi inserido na lista de presença.
Saída
Seu programa deve imprimir uma única linha, contendo apenas um número inteiro, o número de alunos que receberam presença.
Restrições
A professora, ao notar que a lista de presença continha alguns números repetidos, ficou sem entender, mas decidiu dar um voto de confiança e dar presença a todos os alunos cujos números de registro estavam na lista. Como são muitos alunos na sala e muitos números com repetição, ela pediu a sua ajuda para determinar o total de alunos que receberam presença na aula.
Entrada
A primeira linha da entrada contém um número inteiro N , que informa a quantidade de números de registro que apareceram na lista de presença. Cada uma das N linhas seguintes contém um número de registro Vi que foi inserido na lista de presença.
Saída
Seu programa deve imprimir uma única linha, contendo apenas um número inteiro, o número de alunos que receberam presença.
Restrições
- 1 ≤ N ≤ 10^5
- Para cada elemento Vi, 0 ≤ Vi ≤ 10^6
Informações sobre a pontuação
- Em um conjunto de casos que totaliza 40 pontos, N ≤ 10^3 e Vi ≤ 10^3
Exemplos
Entrada ..............................................Saída
3 ........................................... 3
2
3
1
Entrada........................................... Saída
7 ........................................... 5
0
5
12
41
7
5
41
Se preferirem, olha o link da questão: http://olimpiada.ic.unicamp.br/pratique/programacao/nivel2/2012f1p2_frequencia
Abaixo vem a solução disponibilizada pela coordenação da OBI:
[code=C]
#include
int freq[1123456];
int main() {
int i, n, x, res = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &x);
if (freq[x] == 0) {
freq[x] = 1;
res += 1;
}
}
printf("%d\n", res);
return 0;
}
[/code]
Agora, eu não entendi porque criar um vetor de 1123456 posições, sendo que o vetor corresponde a quantidade alunos e a quantidade máxima é 10^5, que é igual a 100.000 alunos. Eu até tentei colocar 100000, mas só valida 40% dos casos de testes. Resultando em 40 pontos de 100.
- Olha o gabarito(10,3 MB): http://olimpiada.ic.unicamp.br/passadas/OBI2012/res_fase1_prog/programacao_n2/gabaritos/frequencia.zip