Lista de probleme 3

Pe un perete au fost montate n x m piese pe n rânduri (numerotate de sus în jos, de la 1 la n) și m coloane (numerotate de la stânga la dreapta, de la 1 la m). Piesele sunt tuburi sau coturi având unul dintre tipurile 1, 2, …, 6. Ionel poate introduce o bilă într-o piesă situată pe rândul 1, doar dacă piesa este de tip 2, 4 sau 6. Bila poate coborî un nivel sau se poate deplasa pe orizontală într-o piesă alăturată, dacă îmbinarea pieselor permite aceasta, dar nu poate urca, din cauza gravitației. Bila nu poate trece de două ori prin aceeași piesă și se blochează atunci când nu se mai poate deplasa într-o altă piesă.
Se citesc două numere naturale n, m și apoi n x m numere din mulțimea {1, 2, 3, 4, 5, 6} reprezentând dispunerea pieselor pe perete. Scrieți un program care să rezolve următoarele cerințe:
1. determină numărul maxim de piese prin care poate trece până la blocare o bilă introdusă în una dintre piesele de pe rândul 1, având tipul 2, 4 sau 6;
2. pentru un rând k dat, determină numerele c și t, unde c este coloana minimă pentru care, înlocuind piesa existentă pe rândul k și coloana c cu o piesă de tipul t, se obține un număr cât mai mare posibil de piese prin care poate trece, până la blocare, o bilă introdusă în una dintre piesele de pe rândul 1 având tipul 2, 4 sau 6; dacă există mai multe soluții de a înlocui piesa de pe rândul k și coloana c, se alege varianta cu t minim.

Într-un joc de domino, fiecare piesă este împărțită în două zone, în fiecare zonă fiind înscris un număr natural. Dacă jocul are dimensiunea d, în joc vor exista toate piesele distincte care se pot forma cu numere cuprinse între 0 și d. Două piese sunt considerate identice dacă au înscrise aceleași numere, indiferent de ordinea lor. Astfel, piesele (3,7) și (7,3) sunt identice. Suma tuturor numerelor de pe aceste piese este 12. Problema are două cerințe:
1. Dat fiind un șir format din N numere naturale nenule reprezentând dimensiunile unor jocuri de domino, să se determine pentru fiecare joc suma tuturor numerelor înscrise pe piesele din jocul respectiv.
2. Dat fiind un șir format din N numere naturale nenule reprezentând sumele tuturor numerelor de pe piesele unor jocuri de domino, se construiește mai întâi un șir de cifre, notat cu A, scriind în ordine toate numerele din șirul dat, fără spații între ele. Se cere să se construiască un șir strict crescător de numere naturale, notat cu B, parcurgând alternativ cifrele din șirul A de la stânga la dreapta și de la dreapta la stânga.

Casa de Modă Venus a decis să se modernizeze şi, începând cu 1 ianuarie 2020 ora 00:00, l-a angajat pe robotul Vasile. Vasile poate executa orice comandă în exact T ore, indiferent de complexitatea acesteia (mai exact, dacă Vasile începe să lucreze la comandă în momentul x, la momentul x+T ore comanda va fi gata de predare). Foarte încrezătoare în calitățile robotului Vasile, Casa de Modă Venus a lansat o campanie publicitară cu sloganul “Dacă am întârziat, primești produsul comandat gratis!”. Campania și-a atins scopul, ca urmare Casa de Modă a primit deja N comenzi pentru întreg anul 2020. Pentru fiecare comandă sunt specificate valoarea acesteia, precum și data și ora până la care produsul comandat trebuie să fie gata de predare. Dacă Vasile predă produsul exact la data și ora specificată în comandă (sau înainte) el încasează valoarea comenzii. Dacă nu, el tot trebuie să execute comanda respectivă, dar nu va primi suma reprezentând valoarea ei.
Deși lucrează fără nicio pauză, Vasile estimează că este posibil să nu poată preda la timp toate comenzile, dar își planifică lucrul, astfel încât pierderea să fie minimă (adică suma valorilor comenzilor care nu vor fi predate la timp să fie cât mai mică). Numim planificare optimală succesiunea în care Vasile trebuie să execute cele N comenzi, astfel încât pierderea să fie minimă.
Scrieți un program care, cunoscând informațiile referitoare la cele N comenzi, determină pierderea minimă, precum și o planificare optimală.