URI (BEECROWD) - 3138 - Tobias Birthday (Aniversário do Tobias) - Math (Matemática) - C e C++

Plataforma: URI (BEECROWD)

Problema: 3138

Linguagens: C e C++

Enunciado:

Hoje é aniversário do Tobias (parabéns!) e como atualmente estamos passando por um momento de isolamento social, ele decidiu fazer uma festa online para poder comemorar a data com os seus amigos.

Como todo bom maratonista de programação, Tobias gosta muito de balões. E é claro que não seria no seu aniversário que eles iriam ficar de fora. Ele decidiu pendurar alguns na sua parede afim de deixar seu quarto decorado para a festa virtual de mais tarde.

O Tobias tinha balões de várias cores guardado em casa e começou a pendurá-los um do lado do outro. Enquanto pendurava ele ficou se perguntando se aquela ordem estava boa, ou se devia colocá-los em alguma ordem distinta e de quantas formas ele poderia trocar aqueles balões de lugar para obter uma sequência diferente.

Dada a lista de quantos balões de cada cor o Tobias encontrou em casa, você consegue ajudá-lo a saber qual o número de sequências distintas ele pode obter reordenando a posição dos seus balões?

Note que trocar dois balões da mesma cor de lugar não gera uma nova sequência e é garantido que o Tobias vai usar todos os balões que ele achou e que esse número não ultrapassa 20.

Solução:

Tanto a resposta em C quanto em C++ utilizam da mesma lógica, diferindo apenas nos tipos de estruturas usados e em comandos próprios de E/S, pois em C foram utilizados scanf e printf, enquanto em C++ foram utilizados std::cin e std::cout.

Código em C:

#include <stdio.h>
#include <string.h>
unsigned long long fat(int a) {
    unsigned long long fat = a;
    while (a-- > 1)
        fat *= a;
    return fat;
}
int jaTem(char *a, char (*b)[16], unsigned long long t) {
    int i;
    for (i = 0; i < t; i++)
        if (!strcmp(a, b[i]))
            return i;
    return -1;
}
int main() {
    unsigned long long n, b, ac = 0, fatoriais = 1, i, pos, repeticoes[20], k;
    char s[16], cores[20][16];
    scanf("%llu", &n);
    memset(s, 0, sizeof(s));
    memset(cores, 0, sizeof(cores));
    k = 0;
    while (n--) {
        scanf("%s %llu", s, &b);
        pos = jaTem(s, cores, k);
        if (pos != -1)
            repeticoes[pos] += b;
        else {
            repeticoes[k] = b;
            strcpy(cores[k++], s);
        }
        ac += b;
    }
    for (i = 0; i < k; i++)
        fatoriais *= fat(repeticoes[i]);
    printf("Feliz aniversario Tobias!\n");
    printf("%llu\n", fat(ac) / fatoriais);
    return 0;
}

Código em C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
unsigned long long fat(int a) {
    unsigned long long fat = a;
    while (a-- > 1)
        fat *= a;
    return fat;
}
int jaTem(string a, vector<string> b) {
    for (int i = 0; i < b.size(); i++)
        if (a.compare(b.at(i)) == 0)
            return i;
    return -1;
}
int main() {
    unsigned long long n, b, ac = 0, fatoriais = 1, i, pos;
    vector<unsigned long long> repeticoes;
    string s;
    vector<string> cores;
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> s >> b;
        pos = jaTem(s, cores);
        if (pos != -1)
            repeticoes[pos] += b;
        else {
            repeticoes.push_back(b);
            cores.push_back(s);
        }
        ac += b;
    }
    for (i = 0; i < repeticoes.size(); i++)
        fatoriais *= fat(repeticoes.at(i));
    cout << "Feliz aniversario Tobias!" << endl;
    cout << fat(ac) / fatoriais << endl;
    return 0;
}