Lista de probleme 1769

Seiful SEPI, în care sunt depozitate premiile olimpiadelor de informatică, este securizat cu un cifru sub forma unei matrice A de formă pătratică cu N linii și N coloane, unde N este un număr natural par. Liniile și coloanele sunt numerotate începând cu 1. Matricea-cifru A este formată din N / 2 chenare. Al i-lea chenar (1 ≤ i ≤ N / 2) va conține elementele aflate pe marginea matricei A, după excluderea primelor i - 1 chenare. Ordinea elementelor acestui chenar este obținută pornind din poziția (i, i), parcurgând latura de sus de la stânga la dreapta, latura din dreapta de sus în jos, latura de jos de la dreapta la stânga și apoi latura din stânga de jos în sus. Cunoscând numărul natural N, cele N x N elemente ale matricei-cifru precum și succesiunea de T operații de permutare circulară a unor chenare, să se determine configurația finală a matricei, cea care va permite deschiderea seifului!

RAU-Gigel și-a descoperit o nouă pasiune: graffiti-ul. El simte o nevoie din ce în ce mai puternică de a-și manifesta spiritul artistic, de a exersa, de a explora, și de a încerca noi și noi tehnici … și pentru asta are nevoie de spațiu.

Făcând o incursiune prin cartier, RAU-Gigel descoperă un depou părăsit împrejmuit de un gard format din plăci de beton de lățimi și înălțimi diferite, dispuse în linie continuă. „O pânză imaculată” se gândește el. Și începe să măsoare plăcile de beton, una câte una, cu gândul ca odată ajuns acasă, să schițeze următoarea sa creație artistică.

El vrea să aleagă câteva plăci de beton alăturate și pe dreptunghiul maximal delimitat de acestea, să își făurească creația. Care este suprafața maximă de desenare ? Ajutați-l pe RAU-Gigel să facă mai multe simulări.

Fie un număr natural nenul n, cunoscut. RAU-Gigel alege un număr oarecare între 1 și n, fie acesta x. Apoi calculează “suma XOR” S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n pe care v-o comunică. Puteți să-l ghiciți pe x ? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi.

Dorești să faci un parfum pentru care vei avea nevoie de X petale de flori. În grădina ta sunt N tipuri de flori, fiecare cu un anumit număr de petale, notat cu count[i]. Odată la T zile, toate florile își vor scutura petalele, urmând ca tu să le colectezi. De asemenea, florile tale au fiecare câte o durată de viață exprimată în zile, notată cu days[i]. Odată ce o floare moare, ea nu mai produce petale.
Acum, te ești interesat să găsești valoarea maximă a lui T pentru care s-ar strânge minim X petale de flori după primele Z zile.

Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: \( \frac{(-1)^{a_i}b_i}{c_i} \). Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil.

Se dau n intervale, să se afișeze care dintre ele includ alte intervale și care sunt incluse într-un interval. Intervalul [a,b] este inclus în intervalul [c,d] dacă c <= a și b <= d (a < b, c < d).

Gimi tocmai a câștigat o licitație pentru asfaltarea unei noi autostrăzi. Firma lui este responsabilă de prelucrarea zonelor dintr-o suprafață bidimensională de dimensiuni N × N. Știm că dacă un drum va trece prin a i-a linie, respectiv a j-a coloană, atunci acea zonă de la poziția (i, j) va trebui asfaltată. Liniile și coloanele suprafeței bidimensionale sunt numerotate de la 1 la N. Având aceste informații, Gimi vrea să verifice dacă traseul dronei este valid, adică drona nu va părăsi niciodată suprafața de care este responsabilă firma lui Gimi. În cazul în care traseul este invalid Gimi vrea să știe a câta instrucțiune dintre cele K a determinat mutarea dronei în afara suprafeței. Dacă traseul este valid, el vrea să determine costul total de asfaltare al autostrăzii.

Dacă vrei să-ți schimbi buletinul trebuie să mergi la Serviciul de Evidență a Populației. Acolo trebuie să iei un număr de ordine și să aștepți să-ți vină rândul. Numerele de ordine sunt emise de un robot, în ordinea 1,2,3,... Programatorul Vasile, care a elaborat soft-ul pentru robot și care asigură (contra cost) întreținerea sistemului, a creat intenționat un bug în sistem. Vasile are un număr natural preferat N. Un număr de ordine x va fi emis dacă și numai dacă x este un subșir al lui N (adică toate cifrele lui x apar în N în ordinea din x, nu neapărat pe poziții consecutive). Dacă numărul de ordine curent x nu îndeplinește această condiție, robotul se blochează și nu mai emite numere de ordine. Scrieți un program care, cunoscând valoarea lui N, numărul natural preferat de Vasile, rezolvă următoarele două cerințe:
1. determină câte cifre are numărul de ordine x care conduce la blocarea robotului;
2. determină numărul de ordine x care conduce la blocarea robotului.

Un număr se numește triprim dacă este produsul a trei numere prime distincte. Exemple de numere triprime: 30 = 2 × 3 × 5, 42 = 2 × 3 × 7, 231 = 3 × 7 × 11. Date fiind numerele A și B, să se afișeze numărul de numere triprime din intervalul [A, B] (inclusiv A și B).

Ionuţ, tânăr programator, se lansează pe piaţa producătorilor de jocuri pe calculator. Jocul pe care l-a proiectat se numeşte RGB. În joc există N personaje extraterestre. Scrieţi un program care, cunoscând culorile şi puterile extratereştrilor, rezolvă următoarele două cerinţe:
1) determină puterea extraterestrului care câştigă cele mai multe lupte; dacă există mai mulţi astfel de extratereştri, se va afişa puterea minimă;
2) determină pentru fiecare extraterestru numărul de lupte câştigate de acesta.