#4671
Scrabble2
C++
Fiind în vacanță, RAU-Gigel petrece mult timp jucându-se pe telefon. El are un joc cu cuvinte, de tip Scrabble, în care piesele sunt inscripționate cu litere (mici sau mari, ale alfabetului englez), fiecare literă din alfabet având o valoare cunoscută, număr natural. Valoarea unui cuvânt este egală cu suma valorilor literelor din cuvânt, fără a se ține cont de frecvența lor.
Prin unirea a două cuvinte se obține cel mai mic (alfanumeric) cuvânt format din toate literele prezente în cele două cuvinte, fără să ținem cont de tipul literei (mică/mare) sau de numărul de apariții. Notăm acest cuvânt cu a*b
.
Costul unirii dintre două cuvinte este obținut prin însumarea valorilor literelor prezente în a*b
, dar care nu sunt în a
, respectiv, care nu sunt în b
, ignorând tipul lor.
Aplicația lui RAU-Gigel generează un șir liniar cu N
cuvinte, iar RAU-Gigel trebuie să unească două câte două cuvinte alăturate din șir, oricare, plătește costul necesar unirii lor, apoi înlocuiește în șir cele două cuvinte cu cuvântul obținut prin unire. La final, din șirul dat va rămâne un singur cuvânt, iar, pentru obținerea lui, RAU-Gigel va plăti suma tuturor costurilor generate pe parcurs.
Cerința este, ca, pentru un șir de N
cuvinte, să se afle cuvântul final și costul total minim necesar obținerii acestuia.
RAU-Coder 2024
Problema | Scrabble2 | Operații I/O |
scrabble.in /scrabble.out
|
---|---|---|---|
Limita timp | 0.2 secunde | Limita memorie |
Total: 1 MB
/
Stivă 1 MB
|
Id soluție | #55072918 | Utilizator | |
Fișier | scrabble2.cpp | Dimensiune | 2.58 KB |
Data încărcării | 20 Decembrie 2024, 15:46 | Scor / rezultat | Eroare de compilare |
scrabble2.cpp: In function 'std::pair<std::basic_string<char>, int> minimumCostToMerge(const std::vector<std::basic_string<char> >&)': scrabble2.cpp:73:23: error: could not convert '(& dp.std::vector<_Tp, _Alloc>::operator[]<std::vector<std::pair<int, std::basic_string<char> > >, std::allocator<std::vector<std::pair<int, std::basic_string<char> > > > >(0u))->std::vector<_Tp, _Alloc>::operator[]<std::pair<int, std::basic_string<char> >, std::allocator<std::pair<int, std::basic_string<char> > > >(((std::vector<std::pair<int, std::basic_string<char> > >::size_type)(n + -1)))' from '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, std::basic_string<char> > > >::value_type {aka std::pair<int, std::basic_string<char> >}' to 'std::pair<std::basic_string<char>, int>' return dp[0][n - 1]; ^ scrabble2.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type] } ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Scrabble2 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.