Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1609
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1609
Counting Sheep
By Bruno Adami, Universidade de São Paulo - São Carlos 
Brazil
Timelimit: 1
You have decided to count sheep to sleep. You are taking too long to fall asleep and you realized that some of the sheep are repeating! Each one is identified by a unique integer, thus you can avoid counting repeated ones.
Given the sheep sequence, output how many you really counted, it is, output the number of distinct ones.
Input
The first line contains an integer T (T = 100*) indicating the number of test cases.
In the first line of each case we have an integer N (1 ≤ N ≤ 100* or 1 ≤ N ≤ 104**), indicating the number of sheep. The next line contains N integers separated by space indicating the sequence of sheep.
The sheep identifiers will be between 0 and 109, inclusive.
*For around 90% of the cases;
**For the other cases.
Output
Output the number of distinct sheep for each test case.
| Sample Input | Sample Output |
|
3 3 1 2 3 3 1 2 1 5 100 1 1 0 0 |
3 2 3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <unistd.h>
void quickSort(long long *carneiros, unsigned tam);
void quickSortInterno(long long *carneiros, long inicio, long fim);
int main (void)
{
unsigned casos, i;
unsigned qtsCarneiros;
unsigned qtsVistos;
scanf("%u", &casos);
while (casos--)
{
scanf("%u", &qtsCarneiros);
long long carneiros[qtsCarneiros];
for (i = 0; i < qtsCarneiros; i++)
scanf("%lld", &carneiros[i]);
// Ordenar antes de ver quem não é repetido é bem menos custoso;
quickSort(carneiros, qtsCarneiros);
qtsVistos = 0;
// Aqui se o elemento da próxima posição é diferente do elemento da posição
// Atual, então quer dizer que não é um repetido, conta 1 nos carneiros
// vistos;
for (i = 0; i < qtsCarneiros; i++)
if (carneiros[i + 1] != carneiros[i])
qtsVistos++;
printf("%u\n", qtsVistos);
}
}
// QuickSort;
void quickSortInterno(long long *carneiros, long inicio, long fim)
{
long long pivo;
long long temp;
long int i, j;
if (fim - inicio > 0)
{
i = inicio;
j = fim;
pivo = carneiros[(i + j) / 2];
do
{
while (carneiros[i] < pivo)
i++;
while (carneiros[j] > pivo)
j--;
if (i < = j)
{
temp = carneiros[i];
carneiros[i] = carneiros[j];
carneiros[j] = temp;
i++; j--;
}
} while (i < = j);
quickSortInterno(carneiros, inicio, j);
quickSortInterno(carneiros, i, fim);
}
}
// Função que dispara a chamada recursiva;
void quickSort(long long *carneiros, unsigned tam)
{
quickSortInterno(carneiros, 0, tam - 1);
}
Input
3
1 2 3
3
1 2 1
5
100 1 1 0 0
Output
2
3
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <set>
using namespace std;
int main(void) {
int i, n, k, g, q;
set < int> st;
cin >> q;
for (g = 0; g < q; ++g) {
cin >> k;
st.clear();
for (i = 0; i < k; ++i) {
cin >> n;
if(st.insert(n).second == false)
st.insert(n);
}
cout << st.size() << endl;
}
return 0;
}
Input
3
1 2 3
3
1 2 1
5
100 1 1 0 0
Output
2
3
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner leitor = new Scanner(System.in);
int T = leitor.nextInt();
for (int i = 0; i < T; i++) {
int N = leitor.nextInt();
HashSet < Integer> numeros = new HashSet<>();
for (int j = 0; j < N; j++) {
numeros.add(leitor.nextInt());
}
System.out.println(numeros.size());
}
}
}
Input
3
1 2 3
3
1 2 1
5
100 1 1 0 0
Output
2
3