Lista de probleme 208

Un showroom din Strasbourg comercializează o gamă foarte mare de modele de autoturisme, aşezate pe n linii. Pe câte o linie se găsesc numai modele de autoturisme comercializate de acelaşi dealer. Un dealer poate avea modele pe mai multe linii. Parlamentul European doreşte să-şi înnoiască parcul auto şi trimite responsabilul cu activitatea de transport la showroom pentru a se informa cu privire la variantele pe care le are pentru rezolvarea acestei probleme de achiziţie. Responsabilul trebuie să aleagă de la primul dealer \(f_1\) modele, de la al doilea dealer \(f_2\) modele, etc. Şirul de numere \(f_1, f_2, f_3, …\) reprezintă termenii modulo k ai unei progresii aritmetice cu primul termen a şi raţia r. Să se scrie un program care determină: a) Numărul de dealeri prezenţi în showroom; b) Numărul de modalităţi de achiziţie al modelelor de către Parlamentul European, modulo 9001.

Spionul 008 vrea să găsească o locație secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi cu fiecare pas, el avansează de la nivelul i la nivelul i+1, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia u faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V), trecând de pe nivelul i pe nivelul i+1 cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caracterele E sau V, corespunzătoare deplasării spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4 a nivelului 6.

Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:
a) poziţia locației secrete de pe ultimul nivel;
b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia inițială pentru a ajunge în locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o poziţie.

Nu e un secret pentru nimeni faptul că Mireluş se antrenează în timpul liber cu probleme de algoritmică. De curând a aflat că un număr natural N, pentru care există două numere naturale nenule A şi B (B>1) astfel încât N = A^B, se numeşte putere. Mireluş şi-a propus să determine numărul de puteri din intervalul [X, Y], unde X şi Y sunt numere naturale nenule.

Cum probabil v-aţi imaginat deja, Mireluş nu a reuşit să rezolve această problemă şi a decis să ceară ajutorul Olimpiei D’Info. Pentru a fi sigur că nici ea nu greşeşte, i-a dat un set de intervale şi i-a cerut să determine pentru fiecare interval numărul de puteri corespunzător.

Dându-se numărul de intervale T şi pentru fiecare din cele T intervale cele două extremităţi, determinaţi numărul de puteri corespunzător fiecărui interval dat de Mireluş Olimpiei.

Suleiman I s-a confruntat în anul 1548 cu mari probleme interne. În acel an, el a primit vestea că într-una din regiunile Imperiului se pregăteşte o răscoală. Harta Imperiului este realizată sub forma unui tablou bidimensional cu n linii şi m coloane, iar fiecare element al tabloului corespunde unei regiuni a Imperiului. În fiecare regiune erau deja cantonaţi soldaţi, dar pentru a preîntâmpina răscoala sultanul decide ca toţi cei k soldaţi din Garda Imperială să fie trimişi în regiuni, întărindu-le pe cele păzite de mai puţini soldaţi. Distribuirea lor respectă următoarele reguli:

• Dacă există o singură regiune cu număr de soldaţi mai mic decât al tuturor celorlalte regiuni, trimite un soldat în această regiune.
• Dacă există mai multe regiuni cu acelaşi număr minim de soldaţi, trimite un soldat în regiunea care iniţial avea un număr mai mic de soldaţi. Dacă mai multe regiuni aveau acelaşi număr iniţial de soldaţi, se trimite un soldat în regiunea cu indicele liniei mai mic, iar dacă regiunile sunt pe aceeaşi linie, în regiunea cu indicele coloanei mai mic.

Suleiman continuă distribuirea soldaţilor din garda imperială în regiuni conform celor precizate anterior, până la epuizarea soldaţilor din Garda Imperială.

Cunoscându-se n, m şi k reprezentând numărul de linii, numărul de coloane, respectiv numărul de soldaţi din Garda Imperială, precum şi numărul de soldaţi existent deja în regiunile Imperiului, să se determine:
a) numărul de regiuni din Imperiu în care vor fi trimişi soldaţii din Garda Imperială, respectiv numărul minim de soldaţi care se vor găsi într-o regiune, după trimiterea soldaţilor din Garda Imperială;
b) distanța maximă între două regiuni în care au fost trimiși soldaţi ai Gărzii Imperiale. Distanța între o regiune A și o regiune B se calculează folosind formula |LA- LB| + |CA- CB|, unde (LA ,CA) reprezintă coordonatele regiunii A, precizate prin numărul liniei și coloanei, respectiv (LB ,CB) reprezintă coordonatele regiunii B, precizate prin numărul liniei și coloanei.

Ben are un teren pe care se află o pădure cu arbori seculari. Acolo vrea să-şi construiască o cabană, însă el fiind ecologist nu vrea să taie niciun arbore, ci vrea să găsească cea mai mare suprafaţă dreptunghiulară fără arbori. El caută o suprafaţă dreptunghiulară străjuită doar în colţuri de arbori şi cu laturile paralele cu axele de coordonate. Ben cunoaşte coordonatele tuturor arborilor din pădure şi vă roagă să-l ajutaţi să găsească aria dreptunghiului cu suprafaţă maximă care are arbori doar în cele patru colțuri.

Cunoscând numărul arborilor din pădure şi coordonatele acestora, se cere să se determine aria dreptunghiului de suprafaţă maximă cu copaci doar în cele 4 colţuri, unde Ben intenţionează să-şi construiască cabana.

Un proprietar vinde un teren de formă dreptunghiulară împărțit în MxN parcele de formă pătrată cu lungimea laturii de o unitate. Fiecare parcelă costă V lei. Vlad s-a interesat și a aflat pentru fiecare din parcelele terenului care este valoarea de revânzare. El constată că unele parcele i-ar putea aduce profit, iar altele i-ar aduce pierdere. Fiind isteț, negociază cu proprietarul să cumpere atâtea parcele de teren câte pot fi împrejmuite cu un singur gard de lungime egală cu 2M+2N unități. Terenul are pe fiecare din cele patru laturi acces la drumul exterior, pe o porțiune de lungime egală cu o unitate. Vlad negociază astfel încât terenul achiziționat să conțină și cele patru parcele de acces la exterior.

Cunoscând M și N – dimensiunile terenului, V – prețul de cumpărare al fiecărei parcele, x_nord, x_sud, y_vest și y_est – pozițiile parcelelor cu acces la drumul exterior și A[i][j], 1≤i≤M și 1≤j≤N – valorile de revânzare pentru fiecare parcelă, să se determine:

a) Profitul P_arie_minimă pe care-l poate obține Vlad după cumpărarea și apoi revânzarea suprafeței de teren de arie minimă, împrejmuită conform condițiilor negociate.
b) Profitul maxim P_max pe care-l poate obține Vlad după cumpărarea și apoi revânzarea unei suprafețe de teren împrejmuită conform condițiilor negociate.

Definim o modificare procentuală de preț ca fiind o pereche (c p) formată dintr-un caracter din {‘+‘,‘-‘} și un număr natural p. Dacă c = ‘+‘ atunci are loc o scumpire iar dacă c = ‘-‘ atunci are loc o ieftinire a unui preț, iar numărul p reprezintă procentul de modificare a prețului.

Exemple de modificări procentuale de preț: (+ 35) – reprezintă scumpirea unui preț cu 35%; (– 50) – reprezintă ieftinirea unui preț cu 50%.

Unui preț inițial i se poate aplica o succesiune de n modificări procentuale de preț obținându-se un preț final. Numim ciclu de preț de lungime n o succesiune de n modificări procentuale de preț, cu proprietatea că prețul final este egal cu prețul inițial.

Să se scrie un program care citește un număr natural n și determină numărul de cicluri de preț de lungime n distincte ce conțin cel puțin o dată o modificare procentuală cunoscută (C P).

Ne aflăm în secția de vopsitorie a uzinei Toyota Motor unde inginerii japonezi prezintă ultimul tip de robot industrial de vopsire. În dorința de a evidenția calitatea și viteza de execuție a roboților, inginerii folosesc pentru demonstrație o tablă de dimensiunea n×n, împărțită în pătrate cu latura egală cu 1, reprezentată sub forma unui tablou bidimensional cu n linii şi n coloane.

Un robot utilizat pentru vopsire are două brațe telescopice care se deplasează de-a lungul unei axe. Fiecare braț poate vopsi într-o unitate de timp un singur pătrat. La momentul de timp t=0 robotul primește comanda de a se poziționa într-un pătrat specificat prin coordonatele (x,y).

În funcție de traiectoria de deplasare roboții folosiți sunt de două tipuri. La momentul de timp t robotul de tip 1 vopsește pătratele aflate la coordonatele: (x-t,y+t) și (x+t,y-t), iar robotul de tip 2 vopsește pătratele aflate la coordonatele: (x+t,y+t) și (x-t,y-t). Pentru vopsirea unui pătrat se consumă 1 litru de vopsea.

Pe tablă sunt așezați m roboți.

Cunoscând pentru cei m roboți coordonatele inițiale (x[i],y[i]), i=1,…,m, se cere să se determine:

a) Cantitatea totală de vopsea care a fost folosită de roboți după t unități de timp
b) Numărul minim de unități de timp necesare formării primului dreptunghi cu arie nenulă. Un dreptunghi corect format este rezultatul intersecției a două traiectorii paralele a doi roboți de tip 1 cu două traiectorii paralele a doi roboți de tip 2, iar colțurile dreptunghiului sunt 4 pătrate care au fost vopsite de doi roboți de tipuri diferite.

Fermierul Ion deţine un teren de formă pătrată, împărţit în NxN pătrate de latură unitate, pe care cultivă cartofi. Pentru recoltarea cartofilor fermierul foloseşte un robot special proiectat în acest scop. Robotul porneşte din pătratul din stânga sus, de coordonate (1,1) şi trebuie să ajungă în pătratul din dreapta jos, de coordonate (N, N). Traseul robotului este programat prin memorarea unor comenzi pe o cartelă magnetică. Fiecare comandă specifică direcţia de deplasare (sud sau est) şi numărul de pătrate pe care le parcurge în direcţia respectivă. Robotul strânge recolta doar din pătratele în care se opreşte între două comenzi.

Din păcate, cartela pe care se află programul s-a deteriorat şi unitatea de citire a robotului nu mai poate distinge direcţia de deplasare, ci numai numărul de paşi pe care trebuie să-i facă robotul la fiecare comandă. Fermierul Ion trebuie să introducă manual, pentru fiecare comandă, direcţia de deplasare.

Scrieţi un program care să determine cantitatea maximă de cartofi pe care o poate culege robotul, în ipoteza în care Ion specifică manual, pentru fiecare comandă, direcţia urmată de robot. Se va determina şi traseul pe care se obţine la recolta maximă.

Ilinca este o fetiţă căreia îi place foarte mult să deseneze; ea a făcut multe desene pe care le-a numerotat de la 1 la d şi apoi le-a multiplicat (toate copiile poartă acelaşi număr ca şi originalul după care au fost făcute). În vacanţă s-a hotărât să-şi deschidă propria expoziţie pe gardul bunicilor care are mai multe scânduri; pe fiecare scândură ea aşează o planşă (un desen original sau o copie). Ilinca ţine foarte mult la desenele ei şi doreşte ca fiecare desen să apară de cel puţin k ori (folosind originalul şi copiile acestuia). Ilinca se întreabă în câte moduri ar putea aranja expoziţia. Două moduri de aranjare sunt considerate distincte dacă diferă cel puţin prin numărul unei planşe (de exemplu: 2 1 3 3 este aceeaşi expoziţie ca şi 2 3 1 3, dar este diferită de 2 1 3 1 şi de 1 3 3 1).

Cunoscând n numărul de scânduri din gard, d numărul desenelor originale şi k numărul minim de apariţii al fiecărui desen, să se determine în câte moduri poate fi aranjată expoziţia, ştiind că Ilinca are la dispoziţie oricâte copii doreşte.