URI (BEECROWD) - 2174 - Coleção de Pomekon - Strings - C e C++

Pra quem não conhece a estrutura set, esse exercício é uma boa oportunidade de conhecer! Além de ajudar muito, o set (ou conjunto disjunto) trabalha da mesma forma que os conjuntos matemáticos, aqueles mesmos que aprendemos no ensino fundamental. Bora ver a solução?

Antes de resolver qualquer algoritmo do URI (BEECROWD agora), recomendamos seguir os seguintes passos:

1. Ler todo enunciado do problema.
2. Ler os tópicos do fórum em caso de dúvidas
3. Preparar arquivos de entrada para teste, considerando as entradas de exemplo do URI, do udebug e outros valores limite;
4. Preparar o ambiente de desenvolvimento e utilizar os mesmos parâmetros dos compiladores do URI
5. Preparar um código-fonte padrão, já contendo a chamada às bibliotecas padrão, pré-processadores, retorno de função e um comando de escrita com "\n", pois no URI a grande maioria dos problemas exige a quebra de linha final.

Plataforma: URI (BEECROWD)

Problema: 2174

Enunciado:

Desde que foi lançado oficialmente o Pomekon no Brasil, Dabriel está tentando realizar seu maior sonho: Ser um Mestre Pomekon. Sua meta é conquistar os 151 Pomekons disponíveis. Ele já conseguiu capturar muitos monstrinhos, porém em sua cidade aparecem muitos Pomekons repetidos, fazendo com que ele capture diversas vezes o mesmo Pomekon.

Vendo que sua mochila está bem cheia, Dabriel pediu para que você fizesse um programa de computador que informasse a ele quantos Pomekons faltam para completar a coleção.

Linguagens: C e C++

Solução em C:

A ideia é armazenar os pomekons em uma matriz de caracteres, ou seja, o que seria um array de palavras. No entanto, essa solução pura permitiria contar pomekons duplicados. Portanto, realizou-se a ordenação do array de palavras em ordem alfabética e comparou-se, assim, cada pomekon com o pomekon anterior. Se os nomes fossem diferentes, incrementa o contador (variável "r"). A resposta final é a subtração 151 - r, ou seja, 151 menos o total de pomekons diferentes lidos pelo programa.

Observações: Quicksort é um algoritmo de ordenação estável, disponível na biblioteca stdlib através da função qsort. Caso prefira, você pode implementar sua própria função de ordenação para resolver este exercício. A função strcmp realiza a comparação entre duas cadeias de caracteres.

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

#define MAX 1010

int compara(const void *p1, const void *p2) {
    return strcmp(p1, p2);
}

int main() {
    
    unsigned int n, i, r = 1;
    char pomekon[MAX][MAX];

    scanf("%u", &n);
    for (i = 0; i < n; i++)
        scanf("%s", pomekon[i]);
    
    qsort(pomekon, n, MAX, compara);
    
    for (i = 1; i < n; i++) {
        if (strcmp(pomekon[i-1], pomekon[i]))
            r++;
    }
    
    printf("Falta(m) %u pomekon(s).\n", 151 - r);

    return 0;
}

Solução em C++:

A ideia é inserir cada pomekon em uma estrutura set (conjunto), garantindo que assim não haverá elementos repetidos. A função size terá o número de elementos do conjunto, bastando, portanto, subtrair este valor de 151 para saber quantos pomekons faltam. É necessário quebrar a linha no comando de escrita (endl;).

#include <iostream>
#include <set>

using namespace std;

int main() {
    
    unsigned int n;
    string pomekon;
    set<string> pomekons;

    cin >> n;
    while (n--) {
        cin >> pomekon;
        pomekons.insert(pomekon);
    }
    
    cout << "Falta(m) " << 151 - pomekons.size() << " pomekon(s)." << endl;

    return 0;
}