Lista de probleme 2

RAU-Gigel și Vlad sunt prieteni buni și le place tot timpul să se provoace unul pe altul. De data aceasta, RAU-Gigel a inventat o problemă interesantă de matematică.

Acesta are un arbore secret cu N noduri (numerotate de la 1 la N), în care fiecare nod are asociată o valoare (pe lângă numărul său de ordine din arbore), care este un număr natural și ii spune lui Vlad informații despre unele drumuri din acest arbore. O informație are forma x, y, val și reprezintă faptul că lanțul din arbore de la nodul x la nodul y are cel mai mare divizor comun al valorilor asociate nodurilor acestuia egal cu val, unde val este un număr natural nenul.

Vlad știe că RAU-Gigel minte câteodată și s-ar putea ca unele dintre restricțiile date să fie eronate, astfel că vrea să afle întâi folosind informațiile ce le are la îndemână dacă ar putea exista un arbore care să respecte toate restricțiile date de prietenul său.

Pentru că știe ce programator iscusit ești, Vlad ți-ar fi foarte recunoscător daca l-ai putea ajuta cu această problemă prin a scrie un program care să o rezolve cât mai eficient.

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.