Lista de probleme 6

Grădina Academiei Shuchi’in are forma unui pătrat cu latura de N metri și este împărțit în N × N parcele pătrate cu dimensiunea de 1 metru. Harta grădinii arată că parcelele sunt aranjate pe linii și coloane și sunt notate cu perechi (r, c), unde r este linia și c coloana pe care o ocupă parcela. Unele parcele, marcate cu 0 pe harta grădinii, conțin copaci străvechi care nu au putut fi mutați sau tăiați când grădina a fost restaurată. Alte parcele, marcate cu 1, conțin flori. Notăm cu F numărul total de parcele care conțin flori. Kaguya definește gradul de înflorire a unei parcele ca fiind suma distanțelor de la parcela curentă la cele mai apropiate K parcele care conțin flori. Ea vrea să știe gradul de înflorire al fiecărei parcele.

Avem o cameră dreptunghiulară de dimensiuni N × M, pe care o vom interpreta ca o matrice cu N linii și M coloane, cu liniile numerotate de la 1 la N de sus în jos și coloanele numerotate de la 1 la M de la stânga la dreapta. Un aspirator robot se află inițial în poziția de coordonate (L1, C1) despre care se garantează că nu este pe marginea matricei, iar ușa de ieșire a camerei la coordonata (L2, C2) ce poate fi un colț de matrice, adică (1, 1), (1, M), (N, 1) sau (N, M). Scrieți un program care să afișeze o listă de instrucțiuni pentru aspirator astfel încât:

• să aspire o suprafață maximă în cameră
• să nu treacă de două ori prin aceeași celulă
• în final să ajungă în colțul camerei unde se află ușa.

Alice tocmai s-a decis să-și impresioneze fratele mai mic, Bob, cu abilitățile sale de deducție matematică. Astfel, ea așează într-o matrice cu N linii și M coloane toate numerele 1, 2, …, N × M, astfel încât fiecare linie și respectiv fiecare coloană, să fie sortată strict crescător. O matrice cu aceste proprietăți se numește o matrice AB. Alice îi cere apoi lui Bob să elimine K valori din matrice, care sa nu fie adiacente orizontal sau adiacente vertical. Apoi, ea va încerca să reintroducă aceste K valori în matrice astfel încât sa rămână o matrice AB. După câteva încercări, Alice realizează că, în anumite situații pot exista mai multe moduri de a aranja cele K numere pe pozițiile libere. Scrieți un program care, cunoscând matricea AB inițială și Q interogări, constând fiecare dintr-o listă de elemente eliminate din matrice, determină pentru fiecare interogare dacă există o soluție unică de a aranja elementele eliminate în matrice astfel încât aceasta să fie matrice AB.

Fie X un număr natural nenul și p cel mai mare factor prim din descompunerea în factori primi a lui X. Pentru X = 1, considerăm p = 1. Asupra lui X se pot efectua următoarele două operații:

• Operația 1: X se împarte la p și devine X / p;
• Operația 2: X devine X * k, unde k este un număr prim și mai mare sau egal decât p.

Se dau Q perechi de numere naturale nenule (X, Y). Să se determine, pentru fiecare pereche, numărul minim de operații necesare pentru a-l transforma pe X în Y.

Cetatea Sucevei, construită de Petru Mușat în timpul zilelor glorioase ale Moldovei medievale de la sfârșitul secolului 14, și consolidată în al 15-lea secol de către Ștefan cel Mare, este cunoscută pentru faptul că nu a fost niciodată capturată de Imperiul Otoman. Sistemul medieval de fortificații al cetății a fost compus din diferite construcții (curți regale, mănăstiri cu pereți înalți și puncte strategice semnificative) concepute în scopuri defensive, care au fost înconjurate de ziduri înalte de piatră. Dată fiind configurația zidului înainte de restaurare, compusă din N turnuri, indexate de la stânga la dreapta folosind numerele naturale cuprinse între 1 și N, și pentru fiecare turn având numărul de blocuri de piatră pe care îl conține, găsiți lungimea maximă a fragmentului de zid care poate fi restaurat, astfel încât restauratorii să folosească toate cele S blocuri de piatră recuperate în fragment. Lungimea fragmentului este definită ca numărul de turnuri conținute în acesta.

Nelu tocmai și-a cumpărat un nou tip de încuietoare digitală pe care vrea să o folosească pentru vestiarul de la școală. Codul secret al acestei încuietori este o secvență de N numere naturale, indexate de la 1 la N. Introducerea acestui cod și deblocarea dispozitivului se face într-un mod special. Încuietoarea începe cu o secvență afișată compusă din N valori de zero. Nelu poate folosi apoi o operație numită incS(i, j), care incrementează cu 1 toate valorile cu indici între i și j (inclusiv). Încuietoarea se deblochează atunci când secvența afișată se potrivește cu codul secret. Nelu îți cere ajutorul pentru a-și găsi codul secret.