URI (BEECROWD) - 1609 - Contando Carneirinhos - Ad-Hoc - C e C++

Resolvendo e postando os códigos do problema "Contando Carneirinhos" para vocês! Veja como ficaram as soluções!

Plataforma: URI (BEECROWD)

Problema: 1609

Enunciado:

Para dormir você resolveu contar carneirinhos. O sono está demorando muito para vir e você percebeu que alguns carneirinhos estão se repetindo! Cada um deles é identificado por um número inteiro único, desta forma você vai evitar contar os repetidos.

Dado a sequência dos carneirinhos, imprima quantos de verdade você contou, ou seja, imprima o número de carneirinhos distintos.

Linguagens: C e C++

Solução:

Basicamente um problema de contagem de valores sem repetição, ou seja, valores que se repetem devem ser ignorados.

Código em C:

A solução que fiz em C foi ordenar os valores armazenados em um array. A ordenação foi feita com o Quick Sort (qsort). Assim, caso o valor seja igual ao valor anterior, não adiciona 1 ao contador, só adicionará se o valor atual for diferente do valor anterior.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compara(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    
    int t, n, i;
    scanf("%d", &t);
    
    while (t--) {
        scanf("%d", &n);
        int v[n];
        memset(v, 0, sizeof(v));
        for (i = 0; i < n; i++)
            scanf("%d", &v[i]);
        qsort(v, n, sizeof(int), compara);
        int r = 1;
        for (i = 1; i < n; i++) {
            if (v[i-1] != v[i]) {
                r++;
            }
        }
        printf("%d\n", r);
    }
    return 0;
}

Código em C++:

C++ dispõe do set, uma estrutura que representa conjuntos disjuntos. Dessa forma, mesmo que diversos valores sejam repetidos, a estrutura trata os elementos como se ela fosse um conjunto, então elementos repetidos são ignorados. Na teoria de conjuntos, A = {a, a, a, a} é o mesmo que {a}, e ambos têm um elemento. Assim, bastava ler os valores, jogar todos para um set (através do método insert) e depois verificar o tamanho do conjunto com o método size.

#include <iostream>
#include <set>

using namespace std;

int main() {
    
    int t, n, i, x;
    cin >> t;
    
    while (t--) {
        
        cin >> n;
        set<int> v;
        v.clear();
        
        for (i = 0; i < n; i++) {
            cin >> x;
            v.insert(x);
        }
        
        cout << v.size() << endl;
    }
    
    return 0;
}