URI (BEECROWD) - 1318 - Bilhetes Falsos - Ad-hoc - C e C++

Bilhetes Falsos! Esse foi o problema resolvido que trago nessa postagem. É um problema da categoria ad-hoc que resolvi manipulando arrays. Veja a minha resposta, que é basicamente a mesma em C e C++.

Plataforma: URI (BEECROWD)

Problema: 1318

Enunciado:

Sua escola organizou uma grande festa para celebrar a brilhante vitória do seu time no prestigiado, e mundialmente famoso CCIP (Competição Colegial Internacional de Poesia). Todos na sua escola foram convidados para a noite, que incluía coquetel, jantar e uma sessão onde a poesia de seu time era lida para a audiência. O evento foi um sucesso – mais pessoas mostraram interesse em sua poesia do que você esperava – porém alguns de seus críticos disseram que tamanho público esteve presente graças à comida, e não graças a sua poesia.

Independente do motivo, no dia seguinte você descobriu o motivo pelo qual o salão esteve tão cheio: o diretor da escola lhe confidenciou que diversos dos bilhetes usados pelos visitantes eram falsos. O número real de bilhetes foram numerados sequencialmente de 1 a N (N ≤ 10000). O diretor suspeita que algumas pessoas usaram o scanner e a impressora da Sala da Computação para produzir cópias dos bilhetes verdadeiros. O diretor lhe deu um pacote contendo todos os bilhetes coletados dos visitantes na entrada da festa, e lhe pediu para que determinasse quantos bilhetes no pacote continham “clones”, isto é, outro bilhete com o mesmo número da sequência.

Linguagens: C e C++

Solução:

Esse problema eu resolvi utilizando dois arrays. Um deles armazena os valores dos bilhetes e em outro eu inicializo tudo com zero, pois ele vai servir como um contador de frequência (quantas vezes cada número aparece). No fim eu percorro o array contador de frequência procurando por valores maiores que 1, pois isso indica que há repetição de bilhetes. Basta contar a quantidade de valores que satisfazem esta condição.

Obs.: coloquei aqui a solução que obtive aceite, que não é necessariamente a melhor! Inclusive todos os valores original[i][0] nem são necessários, ou seja, original poderia ser unidimensional!

Código em C:

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

int main() {
    
    int i, r, n, m, original[20000][2], total[20000];
    while (1) {
        r = 0;
        scanf("%d %d", &n, &m);
        
        if (!n && !m)
            exit(0);
        
        for (i = 0; i < n; i++) {
            original[i][0] = i + 1;
            original[i][1] = 0;
        }
        
        for (i = 0; i < m; i++) {
            scanf("%d", &total[i]);
            original[total[i]-1][1]++;
        }
        
        for (i = 0; i < n; i++)
            if (original[i][1] > 1)
                r++;

        printf("%d\n", r);
    }
    return 0;
}

Código em C++:

#include <iostream>
using namespace std;

int main() {
    
    int i, r, n, m, original[20000][2], total[20000];
    while (true) {
        
        r = 0;
        cin >> n >> m;
        
        if (!n && !m)
            break;
    
        for (i = 0; i < n; i++) {
            original[i][0] = i + 1;
            original[i][1] = 0;
        }
        
        for (i = 0; i < m; i++) {
            cin >> total[i];
            original[total[i]-1][1]++;
        }
            
        for (i = 0; i < n; i++)
            if (original[i][1] > 1)
                r++;
    
        cout << r << endl;
    }
    return 0;
}