Lista de probleme 617

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#3478 palixor

Se dă un şir format din n numere naturale nenule. Aflaţi câte subşiruri ale şirului dat au proprietatea că, folosind toate cifrele numerelor din subşir, cu ajutorul acestora se poate forma un palindrom.

În anul 2020, profitând de lipsa oamenilor de pe şosele, guvernul a construit atâtea şosele încât poţi ajunge din orice oraş al patriei în oricare altul. Drumul dintre două oraşe are şi un cost, cel al benzinei consumate. Dorel s-a hotărât să plece într-o excursie, pornind din oraşul 1 până într-un oraş oarecare. El profită şi de oferta guvernului de relansare a turismului, având k vouchere de călătorie. Un voucher îl scuteşte de plata benzinei între două oraşe consecutiv vizitate, traseu pe care îl alege el pentru scutirea plăţii, de asemenea nefiind obligatorie folosirea tuturor voucherelor primite. Aflaţi costul minim al călătoriei din oraşul 1 pâna la fiecare oraş.

#3563 spider

Omul păianjen (Spiderman) sare de pe o clădire pe alta, aflată în imediata vecinătate, în nord, est, sud sau vest. Clădirile din cartierul omului păianjen au o înălţime exprimată în numere naturale şi sunt aşezate pe m rânduri, câte n pe fiecare rând. Spiderman va alege să sară pe una dintre clădirile vecine, care are înălţimea mai mică sau egală, iar diferenţa de înălţime este minimă. Dacă există mai multe clădiri vecine de aceeaşi înălţime, omul păianjen aplică ordinea preferenţială nord, est, sud, vest, dar nu sare încă o dată pe o clădire pe care a mai sărit. Scopul omului păianjen este acela de a reuşi să facă un număr maxim de sărituri succesive.

Scrieţi un program care determină numărul maxim de sărituri succesive, pe care îl poate efectua, pornind de la oricare dintre clădiri, precum şi poziţiile clădirilor care formează drumul maxim.

O expediție spațială își propune să determine un traseu optim între două sisteme solare din galaxie, în urma căruia să se utilizeze o cantitate minimă de energie pentru propulsie. Determinați costul minim energetic suportat de aceasta, în cazul în care există.

#3556 xorsum

Se dau numerele naturale n, x, y, z, t. Se generează vectorul a astfel: a[i] = (a[i-1] * x + y) % z, pentru 1 ≤ i ≤ n si a[i] = 0 pentru i = 0. Determinați ∑(a[i] XOR a[j]), unde 1 ≤ i < j ≤ n, modulo t.

#3510 AIB2D

Se dă o matrice pătratică de dimensiune N. Asupra ei se fac 2 tipuri de operații:

  • 1 x y val – elementul de coordonate x y crește cu val
  • 2 x1 y1 x2 y2 – se cere suma elementelor submatricei cu colțul stânga-sus de coordonate x1 y1 și cel drepta jos de coordonate x2 y2.

Dându-se Q operații să se raspundă în ordine la cele de tip 2.

#3508 Bal

La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri.

#3541 Pixeli

RAU-Gigel este pasionat de grafică, așa că se gândește la un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni N X N pixeli. O imagine bitmap binară este o matrice de pixeli, fiecare pixel fiind un bit. Să considerăm că valoarea 0 (nesetat) înseamnă alb și valoarea 1 (setat) înseamnă negru (în realitate este exact invers!). Apoi RAU-Gigel împarte imaginea în patru imagini pătrate egale de latură N / 2 pe care le notează de la 1 la 4 (1 este imaginea din colțul dreapta-sus, 2 este cea din colțul dreapta-jos, 3 stânga-jos și 4 stânga-sus). El repetă procedeul pentru fiecare dintre cele 4 imagini obținute, și tot așa, reducând mereu latura la jumătate și notând direcțiile de la 1 la 4, până când ajunge la imagini de mărimea unui pixel.

Pentru simplitate, să presupunem că N este o putere a lui 2, să spunem K. Deci, după K împărțiri succesive de imagini, orice pixel poate fi identificat printr-un șir unic format din cifrele 1, 2, 3 și 4, de lungime K. Inițial, imaginea este complet albă.

Acum începe jocul. RAU-Gigel se gândește la 2 tipuri de operaţii:
Operaţia 1 x schimbă starea pixelul identificat cu șirul x, descris ca mai sus. Dacă pixelul x nu este setat, îl setează. Dacă pixelul x este deja setat, atunci îl resetează.
Operaţia 2 x , unde x are aceeași semnificație ca mai sus, este o interogare: dacă x este setat, se răspunde cu 0. Dacă x nu este setat, se cere determinarea dimensiunii celei mai mari imagini complet albe, dintre cele create de RAU-Gigel, care conține pixelul x. Dimensiunea este dată de numărul de pixeli conținut.

Dându-se N cu semnificația de mai sus și M, reprezentând numărul de operaţii şi cele M operaţii de tipul 1 și 2, să se răspundă la operaţiile de tip 2.

#3546 sidon

Dorel şi consătenii lui, fiind în perioada de alertă, s-au aşezat la rând la magazin. Fiecare avea la el o sumă diferită de bani şi, mai mult, sumele de bani ale secvenţelor de oameni din rând erau diferite oricare două.
Aflaţi ce sumă de bani avea fiecare sătean la el.

Astăzi la ora de mate, Gigel și Ionel nu au fost atenți deloc la explicațiile domnului profesor, iar acesta a hotărât să le dea la finalul orei o tema consistentă pentru ca acest lucru să nu se mai repete. Astfel, fiecare elev a primit pe lângă tema de casă obișnuită încă un exercițiu.