Cod sursa(job #3371570)

Utilizator PrisecaruTudorPrisecaru Tudor PrisecaruTudor Data 30 octombrie 2026 20:01:43
Problema Restante Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
using namespace std;

// cuv[i] = cuvântul original citit
char cuv[36005][20];

int main() {
    ifstream fin("restante.in");
    ofstream fout("restante.out");

    int N;
    fin >> N;  // citim numărul de cuvinte

    // Pentru fiecare cuvânt:
    for (int i = 0; i < N; i++) {
        fin >> cuv[i];              // citim cuvântul original (max 16 caractere)

        for (int k = 0; k < strlen(cuv[i]); k++) {
            for (int j = 0; j < strlen(cuv[i]) - k - 1; j++) {
                if (cuv[i][j] > cuv[i][j+1]) swap(cuv[i][j], cuv[i][j+1]);
            }
            // sortăm literele cuvântului -> două anagrame vor avea aceeași formă sortată
            // ex: "abc" -> "abc"; "cba" -> "abc"
        }
    }
    // Sortăm toate formele sortate pentru a grupa anagramele consecutive
    for(int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N - i - 1; j++) 
        if(strcmp(cuv[j], cuv[j+1]) > 0) {
            char aux[20];
            strcpy (aux, cuv[j]);
            strcpy (cuv[j], cuv[j+1]);
            strcpy (cuv[j+1], aux);
        }
    }
    int originale = 0;

    // Parcurgem grupurile de anagrame
    for (int i = 0; i < N;) {
        // i ul indica prima poz din grup
        // j incepe imediat dupa ea
        int j = i + 1;

        // Avansăm cât timp key[j] este identic cu key[i]
        // -> toate cuvintele sunt anagrame între ele
        while (j < N && (strcmp(cuv[j],cuv[i]) == 0))
            j++;

        // Dacă grupul are un singur element (j - i == 1),
        // înseamnă că acest cuvânt NU are anagrame -> este ORIGINAL
        // de ce j - i?
        // i este prima pozitie, iar j este pozitia de dupa grup
        if (j - i == 1)
            originale++;

        // Sărim la următorul grup
        i = j;
    }

    // Afișăm numărul de cuvinte originale
    fout << originale;
}