Lista de probleme 6

#1244 Trapeze

Se consideră două semidrepte orizontale paralele notate a şi b. Fiecare dintre ele are capătul din stânga situat pe axa Oy. Distanţa dintre ele este de două unităţi.

Pe semidreapta a se află n1 puncte iar pe semidreapta b se află n2 puncte. Pentru fiecare dintre aceste puncte se cunoaşte distanţa faţă de axa Oy.

Să se determine :

  1. Câte trapeze dreptunghice, cu una dintre baze pe semidreapta a, cu cealaltă bază pe semidreapta b şi cu vârfurile în cele două mulțimi de puncte date se pot forma?
  2. Care este cea mai mare arie a unuia dintre aceste trapeze?

Specificul insulelor din arhipelagul Maldive (Oceanul Indian) este faptul că toate cele N insule ale sale au forma unui triunghi. Localizarea acestor insule folosește coordonatele carteziene ale celor trei vârfuri.

Administrația acestor insule dorește să instaleze un dispozitiv de emisie-recepţie pe apă sau pe o insulă, într-un punct având coordonate numere naturale (xD, yD), ce transmite semnale numai pe direcții orizontale și verticale concomitent, cu următoarele proprietăţi:

  • notând cu NRO numărul de insule la care ajunge semnalul pe orizontală și cu NRV numărul de insule la care ajunge semnalul pe verticală, suma NRO + NRV trebuie să fie maximă;
  • dacă există mai multe puncte cu proprietatea anterioară, atunci se va alege punctul cel mai mic în ordine lexicografică.

Să se scrie un program care cunoscând numărul de insule N şi coordonatele carteziene ale vârfurilor acestora, determină coordonatele xD și yD cu proprietățile din enunţ.

Lot Juniori Severin, 2015

#1247 Torturi

Adela lucrează la un laborator de cofetărie. Ea trebuie să pregătească două torturi de nuntă şi în acest scop va folosi n blaturi de tort. Blaturile de tort au formă cilindrică, având toate aceeaşi înălţime, eventual diametre diferite. Blaturile ies pe rând din cuptor. Când un blat iese din cuptor, Adela îl va aşeza deasupra uneia dintre cele două stive de blaturi aflate pe cele două tăvi pe care se pregătesc torturile.

Blaturile diferă între ele prin rezistenţa la presiune. Rezistenţa unui blat creşte odată cu creşterea diametrului. Astfel, un blat va suporta deasupra sa oricâte alte blaturi cu diametre mai mici sau egale cu diametrul său. Pe de altă parte, dacă se aşează un blat de diametru d, deasupra altuia de diametru mai mic, atunci atât blatul aflat imediat dedesubt, cât şi toate blaturile din tort cu diametrul mai mic decât d vor colapsa. Blatul de diametru d se va stabiliza pe un blat cu diametru mai mare sau egal cu al său sau după caz, pe fundul tăvii.

Adela trebuie să folosească toate cele n blaturi pentru pregătirea celor două torturi, şi să le aşeze pe cele două tăvi, în ordinea în care blaturile ies din cuptor. Dorinţa Adelei este ca numărul total de blaturi care nu vor colapsa în cele două torturi să fie maximă.

Cunoscând diametrele blaturilor şi ordinea în care acestea ies din cuptor, să se determine numărul maxim de blaturi care nu vor colapsa.

#1242 Ecluze

Ecluza este o construcție hidrotehnică amenajată pe traseul unei căi navigabile, care asigură trecerea navelor între două suprafețe de apă cu niveluri diferite. O ecluză se compune dintr-un bazin numit “sas” sau “camera ecluzei”, prevăzut la ambele capete cu porţi etanşe şi dintr-o instalaţie puternică de pompare pentru umplerea sau golirea sasului până la nivelul dorit.

Specialiștii români au construit pe cursul navigabil al Dunării o succesiune de N ecluze numerotate de la 1 la N, care asigură condiții optime de navigare în sezoanele secetoase. Astfel, dacă o navă se află la un moment dat în ecluza i și nivelul apei din ecluză diferă de nivelul apei din ecluza i+1, pentru a-și continua navigarea în condiții optime se face modificarea nivelului apei fie din ecluza i la nivelul ecluzei i+1, fie se face modificarea nivelului apei din ecluza i+1 la nivelul ecluzei i.

Cunoscând nivelul apei din cele N ecluze, să se determine numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

#1243 Insula

Pe țărmul insulei Mauritius sunt N localități, numerotate de la 1 la N, considerate puncte de maximă atracție pentru turiști. Acestea sunt conectate printr-o rețea feroviară cu linie ferată dublă ce leagă localitățile 1 de 2, 2 de 3, … , N-1 de N și N de 1, putându-se realiza astfel două circuite. Primul circuit presupune vizitarea localităţilor 1 2 .., N 1, în această ordine, iar cel de-al doilea, vizitarea localităţilor 1 N N – 1 … 2 1. În fiecare localitate există agenții ale tuturor celor M operatori de turism, numerotați de la 1 la M.

Un tichet de călătorie se poate achiziționa doar din localitatea în care se găsește călătorul și permite deplasarea din acea localitate până la următoarea localitate a circuitului. Pentru fidelizarea clienților, operatorii de turism utilizează următoarea regulă pentru prețurile tichetelor: dacă un călător a ajuns într-o gară, cu un tichet cumpărat de la un anumit operator de turism și își continuă călătoria către următoarea destinație cu un tichet pe care-l va cumpăra de la un alt operator de turism, atunci noul tichet își va dubla prețul.

Ștefan se află în concediu pe insulă în localitatea 1 și tocmai a câștigat un premiu oferit de operatorul de turism numerotat cu 1, pentru o excursie cu N tichete de călătorie pe insula Mauritius.

El pornește din localitatea în care se află și apoi parcurge cu trenul întregul circuit, astfel încât cu ultimul tichet cumpărat să se întoarcă în localitatea 1, de unde a plecat. Același operator de turism îi oferă contra cost, primul tichet de călătorie. Ștefan va studia toate ofertele și dacă e cazul poate refuza inclusiv acest prim tichet pentru a-l achiziționa de un alt operator de turism, chiar dacă i se va dubla prețul (fiindcă a schimbat operatorul).

Cunoscând prețul tichetelor de călătorie, stabilite de fiecare operator de turism, determinați suma minimă cu care Ștefan poate achiziționa cele N tichete necesare călătoriei sale.

#1245 Birot

Emil are un mouse special, cu două rotițe de scroll. Pe fiecare rotiță de scroll el poate fixa câte o bandă circulară de cauciuc pe care sunt printate în format 3D caracterele utilizate frecvent pentru editare.

Apăsând vertical rotița de scroll în punctul ei cel mai înalt, caracterul aflat în punctul de apăsare va fi generat de către mouse. Astfel se pot edita diferite texte doar cu ajutorul mouse-ului. Ordinea în care sunt printate caracterele influențează viteza de tastare și energia consumată în procesul de editare a textelor. Efortul de trecere de la un caracter la următorul sau la anteriorul consumă o cantitate de energie egală cu o unitate. Apăsarea pe rotiță nu consumă energie. Emil vrea să afle care este cantitatea minimă de energie pe care trebuie să o consume pentru construirea unui text dat.