Rezolvare completă PbInfo #2262 scrabble

Scrabble (jocul cuvintelor) este un joc în care participanții formează cuvinte prin plasarea de litere pe orizontală sau pe verticală, iar punctajul obținut este cu atât mai mare cu cât literele folosite sunt mai rare (mai valoroase). Vă propunem un altfel de scrabble, joc unde jucătorul primește n piese speciale de scrabble. Astfel, fiecare piesă are inscripționate două litere mari ale alfabetului englez A...Z, una dintre litere fiind consoană, cealaltă fiind vocală. Jucătorul poate forma cuvinte prin alăturarea pieselor pe orizontală. Un cuvânt este considerat valid dacă respectă următoarele condiții:
  • folosește cel puțin două piese;
  • cuvântul format nu conține pe poziții consecutive litere egale sau litere de același tip (vocale/consoane).

Cuvântul este cu atât mai valoros cu cât folosește mai multe piese de scrabble.

Cerința

Să se determine cuvântul de lungime maximă care se poate forma cu cele n piese. Dacă sunt mai multe cuvinte de lungime maximă atunci se va afișa cel mai mare lexicografic alfabetic.

Date de intrare

Fișierul de intrare scrabble.in conține pe prima linie numărul n, iar pe următoarele n linii descrierea pieselor de scrabble sub forma a două caractere literă mare ale alfabetului englez.

Date de ieșire

Fișierul de ieșire scrabble.out va conține pe prima linie cuvântul de lungime maximă format.

Restricții și precizări

  • 1 ≤ n ≤ 18
  • nu există piese identice
  • piesele nu se pot roti
  • sunt considerate vocale caracterele: AEIOU
  • lungimea maximă a unui cuvânt format nu poate depăși 10 piese

Exemplu

scrabble.in

6
AB
EC
BE
BA
CA
AC

scrabble.out

ECACAB

Explicație

Sunt mai multe cuvinte cu număr maxim de piese (3) care se pot forma:
ABECAC, ABACEC, ECABAC, ECACAB, BEBACA,…
Dintre acestea cel maxim lexicografic generat este: ECACAB.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema scrabble:

# include <fstream>
# include <cstring>
using namespace std;

ifstream f("scrabble.in");
ofstream g("scrabble.out");

char piesa[25][3], s[51];
int litere[121], n;
char sol[51];
int ap[25], st[25], kmax;

void back(int k)
{
    for(int x=1; x<=n; ++x){
        st[k] = x;
        if (!ap[st[k]]){
            ap[st[k]] = 1;
            if ((litere[piesa[st[k]][0]] != litere[piesa[st[k-1]][1]]) || k == 1){
                    s[2*k-2] = piesa[st[k]][0];
                    s[2*k-1] = piesa[st[k]][1];
                    if (k > kmax) {
                        s[2*k] = '\0';
                        strcpy(sol, s);
                        kmax = k;
                    }
                    else if (k == kmax) {
                            if (strcmp(s, sol) > 0) {
                                strcpy(sol, s);
                            }
                    }
                    if (k < n) back(k+1);
                }
            ap[st[k]] = 0;
        }
    }
}
int main()
{
    f >> n;
    for(int i=1; i<=n; ++i){
        f >> piesa[i];

        char c1 = piesa[i][0];
        char c2 = piesa[i][1];

        if (strchr("AEIOU", c1)){
            litere[c1] = 2; ///vocale
            litere[c2] = 1; ///consoane
        }
        else {
            litere[c2] = 2;
            litere[c1] = 1;
        }
    }

    back(1);

    g << sol << '\n';

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2262 scrabble

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2262 scrabble de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!