Lista de probleme 3

Nivelul concursului: Online - open

Grupe

Clasele XI-XII Seniori

Etichete

#4648 Donjon

Căpcăunul cel rău o ține captivă pe frumoasa prințesă într-un castel izolat, într-un turn înalt. RAU-Gigel prinde de veste și se duce într-un suflet să o salveze. Ajunge în preajma castelului, însă între cărarea pe care se află el și donjonul prințesei este săpat un mare șanț de apărare pe care RAU-Gigel trebuie să îl treacă. Dar personajul nostru principal are o putere magică, el activează unealta „Piatră” care îi oferă accesul la un morman de pietre pe care, folosindu-se de puterea minții, le poate așeza unele peste altele în speranța că va ajunge pe partea cealaltă a șanțului. Fiind foarte obosit după drumul îndelungat și plin de peripeții, RAU-Gigel nu poate activa magia la capacitate maximă. Reușește oare RAU-Gigel să așeze pietrele? Chiar și așa, căpcăunul îi rezervă și alte surprize, pentru care RAU-Gigel are nevoie de ajutorul vostru.

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.

#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.