Lista de probleme 2

Prin convenţie numim expresie aritmetică ponderată o expresie construită astfel:

  • expresia conţine numere întregi de cel mult 2 cifre despărţite prin virgulă;
  • numim k-şir o enumerare de k numere despărţite prin virgulă (k≥1);
  • o expresie poate conţine unul sau mai multe k-şiruri;
  • expresia foloseşte paranteze rotunde şi paranteze drepte.

Evaluarea expresiei se face după următoarele reguli:

  • dacă expresia conţine un singur k-şir atunci rezultatul expresiei este reprezentat de suma celor k numere. Exemplu: 2,4,1 = 2+4+1 = 7.
  • dacă în expresie întâlnim un k-şir delimitat de paranteze rotunde rezultatul evaluării acestui k-şir va fi reprezentat de suma maximă a unui secvenţe ce aparţine k-şirului, unde prin secvenţă se înţelege o succesiune de numere aflate pe poziţii consecutive în şir. Exemplu: (-2,4,-1,3,-2,-3,2) => secvenţa de sumă maximă este 4,-1,3 a cărui sumă este egală cu 6.
  • dacă în expresie întâlnim un k-şir delimitat de paranteze pătrate, elementele k-şirului fiind numerotate 1,2,..,k, rezultatul evaluării acestui k-şir va fi reprezentat de valoarea elementului aflat pe poziţia [(k+1)/2] dacă şirul ar fi ordonat crescător (mediana unui şir). Exemplu: [-2,9,10,3,5] => şirul ordonat [-2,3,5,9,10] => iar valoarea expresiei este egală cu 5.
  • evaluarea parantezelor se face dinspre interior spre exterior.

Fiind dată o expresie aritmetică ponderată să se determine:

  • câte numere întregi conţine expresia aritmetică;
  • care este valoarea expresiei aritmetice.

OJI 2011, Clasa a X-a

#1066 AI

Institutul Naţional de Robotică Avansată realizează o serie de teste ultimei generaţii de roboţi inteligenţi proiectaţi de specialiştii acestuia. Sistemul de testare se bazează pe o reţea de senzori formată din n segmente egale dispuse orizontal şi n segmente egale dispuse vertical. Distanţa între două segmente alăturate orizontale, respectiv verticale este de 1 metru. Fiecare segment orizontal este în contact cu fiecare segment vertical. Denumim nod un punct în care un segment orizontal şi unul vertical vin în contact. Segmentele sunt numerotate: cele orizontale de sus în jos începând de la 1 iar cele verticale de la stânga la dreapta începând de la 1.

Un nod va fi identificat prin două numere: primul reprezintă numărul segmentului orizontal iar al doilea numărul segmentului vertical care vin în contact în respectivul nod.

Într-unul dintre nodurile reţelei se află o ţintă. În alte două noduri se află câte o sursă ce emite o rază laser. O astfel de sursă emite raza într-o singură direcţie. Raza laser are o grosime neglijabilă. Cele două surse sunt astfel orientate încât raza emisă de fiecare “loveşte” ţinta. Cele două noduri în care sunt plasate sursele sunt astfel alese încât cele două raze nu se intersectează decât în nodul unde se află ţinta.

În alte două noduri ale reţelei se află câte un robot. Fiecare robot se poate deplasa dintr-un nod în cele vecine (cele aflate sus, jos, în stânga şi în dreapta), dar fără să iasă din cadrul reţelei. Roboţii se deplasează cu 1 m/secundă.

Se efectuează experimente în care roboţii sunt programaţi să se deplaseze prin reţea cu scopul de a proteja ţinta faţă de cele două raze laser. Un robot poate proteja ţinta fie ocupând nodul unde se află sursa, fie ocupând un nod prin care trece raza laser în drumul de la sursă către ţintă (razele laser nu “ocolesc” roboţii). Dimensiunea roboţilor este atât de mică încât, în acest al doilea caz, ei protejează ţinta faţă de raza laser doar când nodurile unde sunt sursa, ţinta şi robotul sunt coliniare iar robotul este între sursă şi ţintă. În momentul în care un robot ajunge într-un nod unde protejează ţinta faţă de una dintre raze, el se poate opri sau poate să îşi continue deplasarea. Dacă îşi continuă deplasarea astfel încât noua poziţie ocupată de acel robot şi poziţiile ţintei şi sursei nu mai sunt coliniare, atunci acel robot nu mai protejează ţinta. Din modul în care sunt alese poziţiile nodurilor pentru ţintă şi sursele laser rezultă că nu există nicio poziţie în care un robot să protejeze simultan ţinta faţă de ambele raze.

Fiecare robot este dotat cu o reţea neuronală şi poate învăţa din experimentele anterioare pe unde să se deplaseze. Pentru a mări capacitatea de adaptare a roboţilor, în k noduri ale reţelei sunt aşezate obstacole care fac ca roboţii să nu poată trece prin nodurile respective. Deoarece obstacolele folosite sunt transparente, razele laser pot trece prin acestea fără a le fi afectată intensitatea sau direcţia. Două sau mai multe obstacole dispuse pe acelaşi segment, în noduri alăturate, formează un zid. Lungimea unui zid este egală cu numărul de obstacole din care este alcătuit.

Cerințe:

1) Determinaţi lungimea maximă a unui zid.
2) Determinaţi numărul minim de secunde în care cei doi roboţi pot proteja ţinta faţă de cele două raze laser.

OJI 2011, Clasa a X-a