Lista de probleme 9

Etichete

#3583 jetoane

Ionel şi Georgel colecţionează jetoane care se găsesc în revistele Scooby-Doo. Jetoanele au înscrise pe ele diferite valori, numere naturale distincte, un copil neputând avea două sau mai multe jetoane cu aceeaşi valoare. Ei propun următorul joc: având în faţă jetoanele proprii, determină împreună care este jetonul de valoare comună cu cea mai mică valoare înscrisă şi jetonul de valoare comună cu cea mai mare valoare înscrisă. După ce au identificat aceste jetoane, câştigătorul este acela care va avea cele mai multe jetoane după eliminarea acelora cu valori cuprinse între minimul şi maximul comun, inclusiv minimul şi maximul.

#2405 politic

În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1, 2, 3, 5 şi 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1, 2 și 3 și altul din 5 și 6.)
Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați.
Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea: două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeași coaliţie doar dacă din coaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice 1, 2, 4, 5, 7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă din coaliţia respectivă face parte şi partidul format din 4 şi 5.
Fiind dat parlamentul din Ţara lui Papură Vodă printr-un şir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţie majoritară.

#2406 sort

Primăria orașului ONI a făcut un contract cu firma Gigel.SRL în vederea amenajării gardului Grădinii Botanice. Șeful firmei a constatat că gardul cu pricina este format doar din trei tipuri de scânduri care sunt aranjate fără nicio regulă. Fiind un tip cu “gust estetic” și-a propus să rearanjeze scândurile astfel încât gardul să conțină scândurile grupate astfel: primele să fie scândurile de primă dimensiune (cea mai mică) apoi cele mijlocii, iar ultimele să fie cele de dimensiunea cea mai mare. Echipa care a fost desemnată să execute lucrarea are un singur muncitor care dorește să știe care este numărul minim de schimbări pe care ar trebui să le facă astfel încât să rezolve problema și scândurile să fie ordonate așa precum a decis șeful firmei. Operația de schimbare constă în alegerea a două scânduri diferite și așezarea uneia în locul celeilalte.
Dându-se un număr n ce reprezintă numărul de scânduri care alcătuiesc gardul, precum şi modul în care sunt aranjate scândurile în gard, să se determine care este numărul minim de schimbări ce trebuie realizat astfel încât gardul să aibă scândurile aranjate crescător. Scândurile sunt codificate în funcție de dimensiune prin valorile 1, 2 și 3.

#2861 puncte4

Zăhărel a desenat pe o foaie de hârtie N puncte în plan. Curios din fire, şi-a ales încă M puncte pe axa OX şi s-a întrebat pentru fiecare dintre cele M puncte de pe axa Ox care dintre cele N puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte (x1, y1) şi (x2, y2) este (x1-x2)2 + (y1-y2)2. Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele M puncte de pe axa OX, care este distanța la cel mai apropiat punct dintre cele N desenate pe hârtie.

#3404 castel3

Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.
Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele M x N celule ale castelului sunt numerotate de la 1 la M x N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i conţine cheia cu numărul i. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte. Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele M x N camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.

ONI 2007, clasa a X-a

O firmă producătoare de software organizează un interviu pentru ocuparea unui post de programator, la care s-au prezentat N candidaţi. Aceştia sunt ordonaţi în funcţie de momentul la care şi-au trimis CV-ul şi numerotaţi cu numere consecutive de la 1 la N. Fiecărui candidat i-a fost realizat în prealabil un profil psihologic şi i s-a determinat nivelul de agitaţie provocat de interviul care urmează să aibă loc, precum şi un sens (crescător sau descrescător) de modificare a acestui nivel. Astfel, la ora la care s-a anunţat începerea interviului (pe care o vom considera momentul 0), fiecare candidat are un nivel de agitaţie iniţial. Pentru fiecare unitate de timp după momentul 0 şi până în momentul în care candidatul este invitat pentru interviu (până atunci el trebuind să aştepte), nivelul său de agitaţie se modifică cu 1: pentru o parte din candidaţi nivelul creşte cu 1 unitate, iar pentru ceilalţi nivelul scade cu 1 unitate. Dacă nivelul de agitaţie a unui candidat ajunge la 0, din acel moment, pentru fiecare unitate de timp următoare, nivelul de agitaţie va creşte cu 1 (se schimbă sensul de modificare a nivelului de agitaţie).

Să se scrie un program care să determine suma totală minimă a nivelelor de agitaţie a candidaţilor la sfârşitul interviului dacă aceștia sunt împărțiți optimal în grupuri.

#2408 divtrei

Se consideră numerele naturale N şi K şi cifrele nenule distincte c[1], c[2], …, c[N]. Să se determine câte numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4001.

#3582 sotron1

Pe asfalt este desenat cu cretă un şotron, caroiaj format din n*n căsuţe având aceleaşi dimensiuni (câte n căsuţe pe fiecare din cele n rânduri).

În fiecare căsuţă este scris câte un număr întreg din intervalul [-100, 100]. Fiecare jucător are câte o piatră pe care o aruncă într-o căsuţă a şotronului, şi sărind într-un picior, împinge piatra din căsuţă în căsuţă, pe un anumit traseu astfel încât punctajul obţinut din suma numerelor de pe traseul parcurs să fie cât mai mare.

Numerele din căsuţele şotronului sunt scrise cu două culori albastru şi alb, astfel încât să nu existe două căsuţe alăturate (pe cele patru direcţii Nord, Est, Sud, Vest) având numere scrise cu aceeaşi culoare. Întotdeauna, prima căsuţă din primul rând al şotronului are înscris un număr de culoare albastră.

Se stabilesc apoi, următoarele reguli ale jocului:

  • la începutul jocului, piatra poate fi aruncată în oricare căsuţă a şotronului. Din poziţia respectivă jucătorul îşi conduce piatra până la sfârşitul traseului stabilit de el;
  • dintr-o căsuţă în care numărul este scris cu albastru, piatra poate fi deplasată doar în căsuţa vecină pe direcţia Nord;
  • dintr-o căsuţă în care numărul este scris cu alb, piatra poate fi deplasată doar în căsuţa vecină pe direcţia Est;
  • jucătorul poate alege orice căsuţă (inclusiv cea în care a aruncat piatra) pentru a încheia jocul, atâta timp cât piatra nu iese din şotron.

Să se scrie un program care să determine cel mai mare punctaj care se poate obţine jucând şotron după regulile stabilite.

#2431 cover

Se consideră N intervale închise, având extremităţile numere naturale cuprinse între 1 şi L. Fiecare număr natural i din intervalul [1, L] are asociată o pondere c[i]. Numim acoperire o mulţime de numere naturale cuprinse între 1 şi L cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
Pentru un set de intervale dat să se determine costul minim al unei acoperiri.