Lista de probleme 193

Luis este la târgul auto și dorește să-și cumpere un nou bolid, fiind Black Friday. Există n tipuri de bancnote (a[1], a[2], ..., a[n]). Acestea satisfac condițiile: a[1] < a[2] < ... < a[n]; a[i] este divizor al lui a[i+1].

Știind că bolidul costă x euro, determinați numărul minim de bancnote ce vor fi folosite pentru a efectua plata (numărul de bancnote este egal cu suma dintre numărul bancnotelor cu care plătește și numărul bancnotelor pe care le va primi rest).

Avem un poligon convex cu n laturi, pe fiecare dintre cele n vârfuri fiind scris un număr natural. Acesta se împarte în n-2 triunghiuri. Definim valoarea unui triunghi produsul valorilor celor 3 vârfuri, iar valoarea poligonului este suma valorilor celor n-2 triunghiuri. Determinați valoarea maximă pe care o poate avea poligonul, împărțindu-l în mod optim.

Dăm de n ori cu zarul și însumăm valorile care le obținem, care este probabilitatea ca răspunsul să fie în intervalul [a,b]?

Vrei să-ți aranjezi vitrina florăriei în cel mai minunat mod cu putință. Ai F buchete de flori de diferite soiuri și cel puțin la fel de multe vaze aliniate pe un rând. Vazele sunt lipite de raft și sunt numerotate de la stânga la dreapta cu numere de la 1 la V, unde V este numărul de vaze. Pentru a obține cel mai plăcut efect trebuie să maximizezi suma valorilor estetice pentru aranjament, păstrând în același timp ordinea necesară a florilor. Dacă există mai multe aranjamente de valoare maximă totală, oricare dintre ele va fi acceptată. Trebuie să afișați exact un aranjament.

Se dă o secvență de N procese, numerotate de la 1 la N, care urmează să fie pe rând executate de o mașină. Șirul de procese trebuie împărțit în unul sau mai multe grupe, fiecare grupă conținând o secvență de procese consecutive. Procesarea începe la momentul 0. Dat timpul S și un șir de procese împreună cu timpii de executare și factorii de cost, calculați costul total minim.

Fie N și M două numere naturale nenule. Fie X un șir de M numere naturale nenule x1, x2,…, xM, cu proprietatea că
N=x1+x2+ ... +xM.

Scrieţi un program care să citească numerele N și M şi care să determine:
a) cel mai mare număr care poate să apară în șirul X cu proprietatea din enunț;
b) numărul de șirurilor distincte X cu proprietatea din enunț, modulo 104729.

Rufus pleacă din punctul de linie 1 și coloană 1 al matricei, iar Rufia îl asteaptă în punctul de linie N și coloană M. Fiind un teren accidentat, acesta consumă o anumită energie și un anumit timp pentru a ajunge dintr-un punct în unul din cele maxim 8 puncte vecine ale sale, cu condiția să rămână în interiorul spațiului bine delimitat.
Energia consumată pentru a ajunge în punctul de linie i și coloană j din unul din punctele sale vecine este dată de valoarea lui | A[i][j] | (valoarea lui A[i][j] în modul ), iar timpul consumat pentru a ajunge în acest punct dintr-un punct vecin este dat de valoarea T[i][j].

Ajutați-l pe Rufus să ajungă la prietena sa Rufia în cel mai scurt timp posibil și găsiți, de asemenea, capacitatea fizică inițială minimă, știind că aceasta poate fi cel mult K.

Plictisiți de Facebook și jocuri online, Diana și Jonny s-au gândit să joace un joc nou, care să necesite și mișcare în aer liber. Astfel, cei doi au desenat pe terenul de sport din liceu un dreptunghi pe care l-au împărțit cu N-1 linii orizontale și M-1 linii verticale în NxM pătrate identice, așezate pe N rânduri și M coloane, câte N pe fiecare rând și câte M pe fiecare coloană, ca în exemplu. Apoi, în interiorul fiecărui pătrat au scris câte un număr reprezentând valoarea pătratului respectiv în joc. După ce au terminat de scris cele NxM numere, Diana și Jonny au stabilit ca jocul să se desfășoare după următoarele reguli:

• Diana se poziționează în pătratul din colțul stânga-sus al dreptunghiului, iar Jonny se poziționează în pătratul din colțul dreapta-sus al dreptunghiului.
• Din pătratul în care se află, Diana se va deplasa făcând un pas în pătratul din dreapta de pe aceeași linie (dacă există) sau în pătratul situat pe linia următoare în aceeași coloană (dacă există), ca în desenul de mai jos.
  
• Din pătratul în care se află, Jonny se va deplasa făcând un pas în pătratul din stânga de pe aceeași linie (dacă există) sau în pătratul situat pe linia următoare în aceeași coloană (dacă există), ca în desenul alăturat.
  
• Ambii concurenți vor face până la finalul jocului un număr egal de pași. Simultan, fiecare se va deplasa din pătratul curent în cel ales cu respectarea regulilor de mai sus. Concurenții se pot afla la un moment dat în același pătrat.
• Jocul se încheie în momentul în care Diana ajunge în pătratul din colțul dreapta-jos al dreptunghiului, iar Jonny ajunge în pătratul din colțul stânga-jos al dreptunghiului.
• Fiecare concurent alege pătratele prin care să se deplaseze conform regulilor de mai sus astfel încât să obțină suma maximă posibilă a valorilor din pătratele alese. Această sumă va reprezenta punctajul concurentului.
• Câștigă jocul concurentul care obține punctajul cel mai mare la finalul jocului. Dacă cei doi concurenți obțin același punctaj, atunci amândoi vor câștiga jocul.

Scrieți un program care să citească numerele N, M, cele NxM valori ale pătratelor din dreptunghi și care să determine câștigătorul jocului, precum și punctajul obținut de acesta la finalul jocului.

Considerăm codificarea binară a caracterelor, în care fiecărui simbol îi revine reprezentarea pe 8 biți a codului său ASCII. De exemplu, caracterului ’A’, având codul ASCII 65, îi va corespunde reprezentarea binară 01000001.

Scrieți un program care citește din fișierul convert_submatrix.in un șir s format din n ≤ 100 caractere și construiește o matrice M cu n linii și 8 coloane, linia i a matricii reprezentând codificarea binară a caracterului de pe poziția i din șir. Se cere determinarea dimensiunii celei mai mari submatrice pătratice a lui M, care conține elemente cu aceeași valoare (fie 0, fie 1). Valoarea determinată se scrie în fișierul convert_submatrix.out.

Să se calculeze câte numere naturale în intervalul [A, B] au suma cifrelor un număr prim.