Lista de probleme 888

Se dau două șiruri de numere naturale a[1], a[2], …, a[n] și b[1], b[2], …, b[m]. Să se determine câte numere distincte au în comun cele două șiruri. De exemplu, șirurile a=(2,5,1,4,5,1) și b=(1,1,1,3,7,5) au în comun două numere distincte: 1 și 5.

Fie ∆ o permutare de gradul n. Se cere să se calculeze perioada principală a funcției f(x) = ∆x.

Toată lumea cunoaște modelul de deblocare a telefoanelor sub formă de o matrice cu 3 linii și 3 coloane. Se pot trasa diferite modele de deblocare având un număr N de puncte prin care trecem, din fiecare punct putând merge la oricare vecin al lui. (Sunt maximum 8 vecini de exemplu pentru punctul din mijloc și 3 vecini pentru un punct din colț).

Determinați câte variante de modele sunt posibile trecând prin N puncte. Deoarece numărul poate fi foarte mare, se va afișa numărul de variante modulo 1000003.

Se consideră un set de două șiruri de caractere X și Y. Șirul X este format din caractere din mulțimea {'A'..'Z', 'a' ..'z', '*'}, iar șirul Y este format din caractere din mulțimea {'A'..'Z', 'a'..'z'}. Lungimea șirului Y este mai mare sau egală cu numărul de caractere * din X. Caracterele * din șirul X vor fi înlocuite cu caractere din Y, evident fără a depăși numărul de apariții ale acestora. Fiind date N seturi de câte două șiruri fiecare, (X1, Y1), (X2, Y2), …, (XN, YN), să se determine lungimea celui mai lung subșir strict crescător ce se poate forma în Xi prin înlocuirea caracterelor * cu caractere din Yi, 1 ≤ i ≤ N.

O companie feroviară a lansat recent un nou prototip de tren, format dintr-un singur vagon cu N scaune. Scaunele sunt numerotate la 1 la N (numerotarea începe de la partea din față a trenului) și sunt aranjate într-o linie, unul în spatele altuia. Următoarele reguli urmează să fie respectate de fiecare pasager:

1. Pasagerii vor urca în tren doar pe ușa din spate, care este situată după toate scaunele. Odată urcați, pasagerii au dreptul să se deplaseze doar spre partea din față și pot părăsi trenul doar prin ușa din față (care este situată în fața tuturor scaunelor).
2. Fiecare pasager va ocupa locul situat imediat după ultimul scaun ocupat. Dacă trenul este absolut liber, pasagerul va ocupa scaunul din față (marcat ca locul 1).
3. Nici un pasager nu are dreptul să-și părăsească locul până la debarcare.
4. La fiecare stație, pasagerii care au ajuns la destinație părăsesc trenul. Dacă există pasageri pe scaune în fața celui care a ajuns la destinație, ei de asemenea vor părăsi trenul, chiar dacă încă nu au ajuns la destinația lor.
5. Odată ce a ieșit din tren, pasagerul nu mai are dreptul să urce înapoi.

Ruta trenului are M stații, numerotate de la 1 la M. Trenul se oprește în fiecare stație, începând cu stația 1 și terminând cu stația M. La toate cele M stații de tren se află în total N pasageri, numerotați de la 1 la N. Pentru fiecare pasager se cunoaște din timp prețul tichetului, stația de îmbarcare și stația de debarcare. Compania feroviară dorește să aibă doar clienți fericiți, care ajung la destinația lor. Pentru a avea doar clienți fericiți, compania a permis conductorului să selecteze pasagerii care se pot îmbarca, precum și ordinea în care li se permite îmbarcarea. Astfel, conductorul poate să decidă să nu permită unor pasageri să urce în tren. Determinați profitul maximal care poate fi obținut de companie având doar clienți fericiți, precum și o ordine de îmbarcare validă, care permite obținerea acestui profit.

Legendarul vrăjitor Merlin se distrează în laboratorul său. El are N poțiuni magice (etichetate cu 1, 2, …, N) aranjate pe o singură linie într-o ordine dată. El dorește să le aranjeze în ordine crescătoare. Se va muta o singură poțiune la un moment dat. Prima poțiune mutată va fi cea etichetată cu 1, apoi cea etichetată cu 2 și așa mai departe. Bineînțeles, pentru a rezolva problema, Merlin va apela la magie. Fiecare poțiune poate fi mutată folosind una sau mai multe vrăji, trecând prin una sau mai multe poziții intermediare. Mutând o poțiune de la poziția I în poziția J, vraja va consuma (I-J)2 unități de energie. De exemplu, dacă există șapte poțiuni aranjate astfel 1, 7, 3, 4, 5, 2, 6 și Merlin mută poțiunea (etichetată cu 2) de la cea de-a șasea poziție la a doua poziție atunci noua aranjare va fi 1, 2, 7, 3, 4, 5, 6 cu (6-2)2 unități de energie consumate. Înainte de a începe distracția, Merlin a stabilit două criterii:
1. El nu dorește să fie prea obosit la sfârșitul zilei, de aceea nu dorește să consume mai mult de E unități de energie.
2. De asemenea el se plictisește repede, de aceea el dorește să rezolve problema cu un număr minim de vrăji. Calculați numărul minim de vrăji pe care le poate folosi Merlin pentru a rezolva problema.

Scrieţi un program care să determine în conformitate cu decizia directorului, diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipa LNA şi suma punctajelor la matematică ale elevilor din echipă, precum şi suma tuturor punctajelor elevilor din echipa LNA.

Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val.
2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată crescător.

Compania lui Jimmy are n plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin n - 1 drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația x la plantația y , pentru fiecare 1 ≤ x, y ≤ n. De asemenea, știm și distanța în km pentru fiecare dintre cele n - 1 drumuri. Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem a tone de flori şi vrem să le trimitem pe o distanță de b kilometri, costul transportului este a * b. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.

Michael își petrece vacanța de vară la bunici, în Delta Dunării. În prima zi, se duce la pescuit cu tatăl său în locul în care acesta se ducea în copilărie. Michael își dă seama că traseul ales nu este singura opțiune de a parcurge distanța de la casa bunicilor până la locul unde pescuiesc, așa că, odată ce vizitează întreaga regiune împreună cu bunicul său, se întreabă în câte moduri distincte poate parcurge distanța de la casa bunicilor la locul unde pescuiesc. Regiunea pe care Michael o cunoaște are formă dreptunghiulară, cu rânduri numerotate de la 1 la L și coloane numerotate de la 1 la C. Valorile de 1 reprezintă zone de uscat și valorile de 0 reprezintă zone acoperite de apă. Michael poate merge doar pe uscat, cu următoarea restricție: din zona de coordonate (i, j) se poate duce doar în una din zonele (i – 1, j + 1), (i, j + 1), (i + 1, j + 1) – bineînțeles, doar dacă acestea reprezintă zone de uscat și Michael nu părăsește regiunea. Fiind un băiat inteligent, când Michael vizitează împrejurimile cu bunicul său, își dă seama de următorul lucru: coloanele din matricea care codifică regiunea se repetă identic din K în K. Coloanele 2, K + 2, 2 * K + 2, … sunt identice, coloanele K – 1, K + (K - 1), 2 * K + (K - 1), … sunt identice. Două coloane c1 și c2 sunt identice dacă elementul de pe poziția (i, c1) este egal cu elementul de pe poziția (i, c2), oricare ar fi i de la 1 la L. Știind coordonatele locului unde se află casa bunicilor și coordonatele locului de pescuit pe care tatăl lui Michael i l-a arătat acestuia, să se determine numărul de moduri de a parcurge distanța dintre ele. Două drumuri sunt considerate distincte dacă, scriind secvența rândurilor vizitate (în ordine crescătoare a coloanelor), ele diferă prin cel puțin o poziție.