Lista de probleme 106

Se cunosc înălțimile a N vârfuri, plasate de la stânga la dreapta, în cadrul unui lanț muntos. Dacă plasăm o santinelă pe un vârf de o anumită înălțime, aceasta veghează vârful respectiv și maximum K vârfuri la stânga și maximum K vârfuri la dreapta acestuia, dar cu condiția ca înălțimile acestor vârfuri vegheate să fie mai mici sau egale cu înălțimea vârfului pe care se află santinela. Date fiind N, K și înălțimile celor N vârfuri, să se determine:

• Numărul maxim de vârfuri consecutive, începând de la primul vârf al lanțului muntos (inclusiv acest vârf), ce pot fi vegheate cu o singură santinelă.
• Numărul minim de santinele necesare ca toate vârfurile să fie vegheate.

În sistemul solar Stelarion sunt 99 de planete. Planeta Hazard găzduiește campionatul de Robotron pe echipe. Jucătorii sunt înregistrați în ordinea sosirii lor, indiferent de planeta de pe care provin. Anul acesta s-au înscris în campionat N jucători de pe M planete. Jucătorul înregistrat al i-lea (cu i de la 1 la N) primește două numere: E[i] — numărul trecut pe ecuson și P[i] — puterea jucătorului. Numărul trecut pe ecuson este format din codul planetei jucătorului CP (numărul format din ultimele două cifre de pe ecuson) și codul jucătorului CJ (numărul format din restul cifrelor).
1) Să se determine numărul M al echipelor participante și codul H al planetei gazdă Hazard, știind că numărul jucătorilor din echipa planetei gazdă este strict mai mare decât numărul jucătorilor oricărei alte echipe.
2) Să se determine codul planetei de pe care provine echipa câștigătoare la runda K și codul jucătorului care aduce victoria acestei echipei la aceasta rundă.

Robin Hood și Little John au hotărât să stabilească care dintre ei este cel mai bun arcaș. Pentru aceasta au construit n ținte așezate în linie dreaptă și numerotate de la 1 la n. Au stabilit apoi distanța de tragere. Cei doi se deplasează prin fața țintelor în linie dreaptă la distanța stabilită de comun acord. Cei doi pot trage simultan în aceeaşi țintă sau într-una deja atinsă. Concursul se încheie în momentul în care fiecare țintă a fost atinsă cel puțin o dată.
1. Se cere să se determine timpul în care se termină concursul.
2. Care sunt țintele atinse exact o dată în timpul concursului.
3. Care sunt țintele atinse de cele mai multe ori în timpul concursului.

Se dă un șir a1, a2, …, an de numere naturale. Trebuie să răspundeți la două cerințe:
1) Să se verifice dacă șirul este ordonat crescător sau nu.
2) Să se verifice dacă prin eliminarea unui singur element, șirul rămas este ordonat crescător sau nu.

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.