Lista de probleme 905

Se consideră trei numere naturale n, k și d. Să se determine cel mai mic număr natural care se poate obține prin interschimbarea ultimelor k cifre ale lui n astfel încât numărul obținut să fie divizibil cu d.

Pentru un număr natural N, considerăm toate submulțimile nevide ale mulțimii {1, 2, 3, ..., N}. De exemplu, pentru N = 3, submulțimile nevide ale mulțimii {1, 2, 3} sunt: {1}, {2}, {3}, {1,2}, {1,3}, {2,3} și {1,2,3}. Pentru fiecare submulțime se ordonează mai întâi descrescător elementele sale, apoi valoarea maximă primește semnul +, valoarea următoare are semnul –, următoarea valoare + ș.a.m.d, apoi se determină suma lor. De exemplu, submulțimea {1, 2, 5, 8, 10} are asociată suma +10-8+5-2+1=6, submulțimea {4,7} are suma +7-4=3, iar submulțimea {3} are suma 3. Să se determine valoarea totală a sumelor asociate tuturor submulțimilor mulțimii {1, 2, 3, ..., N}.

Se consideră doi vectori a = a[1], a[2], ..., a[n] și b = b[1], b[2], ..., b[m] de numere naturale. Se construiește matricea c având n linii și m coloane, în care c[i][j] = 1 dacă a[i] ≤ b[j], sau c[i][j] = 2 dacă a[i] > b[j]. Să se determine numărul liniilor distincte din matricea c.

Se dă o listă de N numere naturale, indexată de la 1 la N, și Q query-uri de forma op poz, unde op = 1, 2 este tipul operației.

Cele 2 operații sunt:

• op = 1: se șterge din listă elementul aflat pe poziția poz
• op = 2: se afișează elementul din listă aflat pe poziția poz

Nicușor, primarul capitalei, a fost invitat în seara zilei de 5 septembrie 2024 la jurnalul de seară al Digi 24. Acesta a fost provocat să rezolve o problemă “de clasa a patra” propusă de către o profesoară: “Care este cel mai mic număr natural nenul care are proprietatea că dacă mutăm ultima sa cifră în fața primei cifre, valoarea noului număr este egală cu dublul numărului inițial”. Cu alte cuvinte, acestuia i s-a cerut să găsească cel mai mic număr nenul de forma \(\overline{c_1 c_2 … c_n}\) cu proprietatea \(\overline{c_n c_1 c_2 … c_{n-1}} = 2 \times \overline{c_1 c_2 … c_n}\).

După ce a rezolvat problema, Nicușor a decis să o generalizeze, astfel propunând o variantă pentru clasa a cincea: Care este cel mai mic număr natural nenul, care, scris in baza b ca \(\overline{c_1 c_2 … c_n}_{(b)}\), are proprietatea că \(\overline{c_n c_1 c_2 … c_{n-1}}_{(b)} = a \times \overline{c_1 c_2 … c_n}_{(b)}\) unde 2 ≤ a < b.

Se dă un șir de \(N\) numere întregi. Să se aleagă maxim \(K\) secvențe disjuncte astfel încât suma elementelor incluse în secvențe să fie maximă.

Se dă un șir a1, a2, …, an de numere întregi. În acest șir, o secvență de cel puțin două elemente ai, ai+1, …, aj este validă dacă ai este strict mai mic decât aj. Cu alte cuvinte, secvența de cel puțin două elemente trebuie să aibă capătul din stânga strict mai mic decât capătul din dreapta al secvenței. Să se determine câte secvențe valide sunt în șir.

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.

Echipa spațială s-a deghizat în locuitorii unei planete înapoi, cunoscută sub numele de „Pământ”. În timpul șederii lor s-au interesat de muzica acestor așa-numiți oameni, în special a genului obscur cunoscut sub numele de “space jazz”. În loc să fie jucat la o scară obișnuită, se joacă pe space jazz, o scară de 26 de note, etichetate de la “a” la “z”. Un compozitor de space jazz scrie o piesă de space jazz așa cum urmează să fie descris. Începe cu o foaie goală de hârtie. Apoi alege o anumită notă de la “a” la “z” și scrie nota de două ori. Apoi alege în mod repetat o nouă notă (ar putea fi aceeași sau diferită de cea anterioară) și o scrie de două ori între două note adiacente sau lângă altă notă. De exemplu, un compozitor ar putea începe prin a scrie “gg”, apoi adaugă “oo” pentru a face “goog”, apoi adaugă “aa” pentru a face “aagoog” și așa mai departe. Problema este că toate spectacolele pe care le ascultă echipa spațială lasă afară note. Având în vedere notele jucate într-o reprezentație de space jazz, ajutați-i să-și dea seama numărul minim de note care au fost lăsate deoparte, având în vedere că original piesa a fost o compoziție valabilă de jazz spațial.