Lista de probleme 280

Filtrare

#3007 tort1

De ziua lui, Gigel a primit un tort de formă dreptunghiulară, ornat cu un caroiaj ce împarte tortul în m x n pătrate, în fiecare pătrat aflându-se câte o cireașă sau o căpșună. Caroiajul cu fructe este reprezentat printr-o matrice cu 0 şi 1, 0 însemnând cireaşă şi 1 căpşună. Sărbătoritul are dreptul să taie k felii de tort. O felie se poate obține prin tăierea după liniile caroiajului, dintr-un capăt în celălalt, având lățimea egală cu 1, de pe oricare latură a tortului, codificate cu N, E, S, V. Gigel fiind mare amator de căpşuni vrea să taie cele k felii astfel încât numărul căpşunilor din aceste felii să fie cât mai mare. Să se scrie un program care să determine numărul de posibilităţi de tăiere a k felii de tort, pentru a obţine un număr maxim de căpşuni. Două variante în care diferă doar ordinea de tăiere, dar rămâne aceeaşi bucată de tort, nu sunt considerate distincte. De exemplu, dacă numărul maxim de căpşuni se poate obţine prin una din variantele : VSNNV sau VVNSN, acestea nu sunt considerate distincte.

#3370 amedie

Pentru o matrice A cu n linii şi m coloane, ce conţine numere naturale, se defineşte amedia matricei A ca fiind valoarea situată la mijlocul şirului ordonat crescător format din toate elementele matricei A, dacă numărul de elemente din acest şir este impar, respectiv cea mai mică valoare dintre cele două valori situate la mijloc, dacă numărul de elemente din acest şir este par. Se definesc trei tipuri de operaţii ce pot fi aplicate matricei A. Scrieţi un program care determină valorile obţinute în urma efectuării operaţiilor de tip 3 din şirul de operaţii aplicate matricei A.

#1515 gradina

Păcală a reușit să ducă la bun sfârșit înțelegerea cu boierul căruia-i fusese slugă și, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, așa că livada sa este un pătrat cu latura de N metri unde, pe vremuri, fuseseră plantate N rânduri cu câte N pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află și poziția sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-și delimiteze în livadă o grădină pătrată cu latura de K metri.

#1129 Tinta

Alex are o pasiune pentru trasul la țintă. Jucându-se cu numere, visează la o nouă tablă pentru pasiunea sa. Tabla visată este de formă pătrată cu n linii și n coloane, iar numerele, de la 1 la n * n, le poziționează în țintă, ca în imaginea alăturată.

Alex, fiind un foarte bun țintaș, nu nimerește niciodată pe pătrățelele de pe contur. Când țintește o pătrățică din interior, el obține drept punctaj suma valorilor din cele opt pătrățele vecine.

Cunoscând n numărul de linii și de coloane ale țintei:

a. Ajutați-l pe Alex să construiască ținta visată.
b. Câte punctaje distincte poate să obțină Alex dacă are o singură săgeată?
c. Afișați punctajele distincte găsite.

#1103 Harta

Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele k clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu n•m celule așezate pe n linii numerotate de la 1 la n și m coloane numerotate de la 1 la m.

Numim drum, un dreptunghi al tabloului care străbate întreaga localitate pe direcția Est-Vest și are un număr maxim de linii sau un dreptunghi care străbate întreaga localitate pe direcția Nord-Sud și are un număr maxim de coloane. Drumurile, evident, nu trebuie să treacă prin clădiri.

Cartografii sunt interesați ca pe această hartă să fie reprezentate la scară doar clădirile, nu și drumurile. De aceea, pentru realizarea hărții, lățimile drumurilor au fost reduse la o singură celulă

Tabloul care reprezintă imaginea localității se codifică astfel: 1 pentru o celulă ocupată de o clădire și 0 pentru o celulă neocupată.

Cunoscând n, m și k, precum și tabloul care codifică imaginea, se cere să se determine:

1. Numărul S de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri C alese dintre celelalte k – 1 clădiri, cu proprietatea că fiecare dintre ele “încape” în interiorul clădirii pătratice cu latură maximă, fără să se suprapună peste celulele marginale ale acesteia.
2. Tabloul care reprezintă harta, în urma prelucrării imaginii inițiale.

#1185 Cub2

Sărbătorile de iarnă tocmai s-au încheiat. Florinel dorește să-și ajute părinții la despodobirea bradului. Tubul luminos pe care l-au folosit anul acesta este mai special. Are N3 becuri luminoase numerotate de la 1 la N3, iar fiecare bec care este inscripționat cu un număr prim, va rămâne mereu aprins. Cutia în care trebuie strâns tubul este un cub de latură N. Becul cu numărul 1, trebuie pus în colțul de coordonate (1,1,1), restul în spirală până la umplerea nivelului, apoi nivelul următor în sens invers, ș.a.m.d.

Cunoscând latura N a cubului, să se umple cubul cu tubul luminos (becurile fiind legate crescător), apoi să se determine:

1. Coordonatele (x,y,z) ale becului cu numărul V. (x-linia, y-coloana, z-înălțimea)
2. Numărul de becuri luminoase situate pe fiecare față a cubului.

#1189 Lenes

Leneşul este un animal foarte leneş. El se deplasează numai în linie dreaptă, dar face din când în când câte un popas. În această problemă leneşul trebuie să traverseze de la nord la sud şi înapoi un teren reprezentat de o matrice de dimensiuni M×N cu valori numere naturale. Valorile reprezintă efortul cerut pentru traversarea zonei respective. Leneşul va alege o coloană pentru traversarea matricei, iar pentru popasuri, în număr de k1, va alege zone alăturate drumului din coloana din stânga sau cea din dreapta. În cazul în care se va întoarce va proceda la fel, dar va face k2 popasuri. Regulile problemei cer ca cele două drumuri să nu aibă zone comune.

Cunoscând dimensiunile M, N ale terenului, numărul de popasuri k1, k2 și efortul pentru traversarea fiecărei zone a terenului, să se determine:

  1. Efortul minim de parcurgere a terenului de la Nord la Sud, folosind k1 popasuri.
  2. Efortul minim de parcurgere a terenului de la Nord la Sud și înapoi de la Sud la Nord, folosind k1 popasuri la deplasarea Nord – Sud, respectiv k2 popasuri la deplasarea Sud – Nord.

#1218 Teren

În satul vecin există un teren agricol de formă dreptunghiulară împărțit în N*M pătrate elementare identice, dispuse alăturat câte M pe fiecare rând şi câte N pe fiecare coloană. Rândurile sunt numerotate de la 1 la N, iar coloanele de la 1 la M. Un pătrat elementar situat în teren pe rândul R și coloana C este identificat prin coordonatele (R,C).

Suprafețe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T fermieri din sat, în calitate de moștenitori, pe baza actelor primite de la strămoșii lor. Pentru că au apărut și acte false, s-a constat că pot exista mai mulți fermieri care revendică aceleași pătrate elementare.

În cele T acte ale fermierilor, suprafețele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y) și (Z,U), reprezentând coordonatele primului pătrat elementar din colțul stânga-sus al suprafeței (rândul X și coloana Y), respectiv coordonatele ultimului pătrat elementar situat în colțul dreapta-jos al suprafeței (rândul Z și coloana U).

Scrieţi un program care să citească numerele naturale N, M, T, R, C apoi cele T perechi de coordonate (X,Y) și (Z,U) precizate în acte (corespunzătoare suprafețelor dreptunghiulare revendicate) și care să determine:

  1. numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C);
  2. numărul maxim de fermieri care revendică același pătrat elementar;
  3. numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier.

#1378 Flori2

Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv.

#2178 Furnica

Pe o tablă de şah cu n linii şi n coloane se află firimituri de pâine şi o furnică. Pentru fiecare pătrăţel, inclusiv cel în care se găseşte furnica, aflat pe linia i şi coloana j, cantitatea de firimituri de pâine este egală cu restul împărţirii lui i+j la 6.