Lista de probleme 3

Maria inventează mereu câte ceva și îl provoacă la joacă pe fratele ei mai mic Petru. De data aceasta alege N cartonașe, pe care sunt înscrise valorile naturale distincte de la 1 la N (fiecare astfel de număr apare pe câte un singur cartonaș), le amestecă și le așează unul lângă altul într-un șir. Maria formulează lui Petru cerințe de următoarele tipuri:
1) Îți spun un număr poz și trebuie să determini cartonașul numerotat cu cea mai mare valoare r astfel încât primele r cartonașe din șir au înscrisă o valoare strict mai mică decât cea scrisă pe cartonașul numerotat cu poz. Dacă nu există niciun astfel de cartonaș, pentru r se stabilește valoarea 0.
2) Determină toate valorile p cu proprietatea că pe primele p cartonașe se află înscrise toate numerele naturale de la 1 la p.
3) Determină toate valorile p cu proprietatea că pe primele p cartonașe se află înscrise exact p-1 dintre numerele naturale de la 1 la p.

Există N căsuțe (pătrățele), așezate în ordine, de la stânga la dreapta, numerotate de la 1 la N. În interiorul fiecărei căsuțe putem scrie câte un număr natural. Inițial, în fiecare căsuță scriem același număr 0. Executăm, în ordine, Q operații, care pot fi de trei tipuri:

• Primul tip de operație se codifică prin 1 st dr nr și înseamnă că în fiecare căsuță cu indicii între st inclusiv și dr exclusiv ștergem numerele care existau înainte și scriem în locul lor același număr nr.
• Al doilea tip de operație se codifică prin 2 poz și rezultatul operației este numărul aflat în căsuța cu indicele poz.
• Al treilea tip de operație se codifică prin 3 st dr și rezultatul operației este numărul de apariții al valorii celei mai mari din căsuțele cu indicii între st inclusiv și dr exclusiv.

Determinați rezultatele tuturor operațiilor de tip 2 sau 3, în ordinea executării acestora.

Gigel a primit o sarcină interesantă: se dă un șir de N numere numere naturale și un număr natural K. Ajutați-l pe Gigel să rezolve următoarele două cerințe.
1) Fie X primul număr din șir. Determinați poziția celui mai mic număr Y care aparține șirului, astfel încât suma celor două numere X și Y să fie divizibilă cu K. Dacă valoarea Y, cu proprietatea precizată, apare de mai multe ori în șir, se ia în considerare poziția cea mai din dreapta. Există cel puțin un astfel de număr Y, care aparține șirului.
2) Determinați numărul minim de elemente care trebuie eliminate din șir astfel încât elementele rămase să poată fi grupate în perechi disjuncte (fiecare element rămas aparține unei singure perechi), cu proprietatea că suma celor două valori din fiecare pereche este divizibilă cu K.