Lista de probleme 38

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ţ.

Se dau N puncte în spațiul 3D prin coordonatele lor. Dorim să amplasăm două cuburi cu laturile paralele cu axele de coordonate, astfel încât fiecare punct să se afle pe una dintre feţele sau în interiorul a cel puțin unuia dintre cuburi. În plus, latura cubului de latură maximă dintre cele două trebuie să fie minimă.

Scrieţi un program care să determine latura cubului de latură maximă pentru două cuburi care realizează acoperirea mulțimii de puncte în condiţiile de mai sus.

La ora de geometrie, Aurel a primit de la profesorul X o temă foarte dificilă: fiind date N segmente orizontale (paralele cu axa Ox), cu extremităţile de coordonate numere naturale, să se numere câte dreptunghiuri speciale pot fi formate în plan, luând în considerare aceste segmente.

Un dreptunghi este special dacă respectă simultan următoarele trei condiţii:
1. Cele patru vârfuri ale dreptunghiului au coordonate numere naturale
2. Laturile dreptunghiului sunt paralele cu axa Ox, respectiv Oy
3. Fiecare dintre cele patru vârfuri ale dreptunghiului aparţine cel puţin unui segment

Scrieţi un program care să-l ajute pe Aurel să determine numărul de posibilităţi de a plasa un dreptunghi în plan astfel încât să fie dreptunghi special. Deoarece rezultatul poate fi foarte mare, se va determina numărul modulo 946021 (restul împărţirii numărului calculat la 946021).

Marele inginer NN, expert în construirea de baraje, a primit de data aceasta o sarcină mai îmbârligată. Acesta are de construit M baraje peste mai multe râuri dintr-o deltă și îşi planifică pe hârtie milimetrică construcţia fiecărui baraj în parte.

Toate râurile peste care are de construit baraje sunt braţe ale aceluiaşi fluviu şi toate pornesc din exact acelaşi punct pe lungimea fluviului. Pentru a-şi explica schiţa, NN marchează locul de despărţire a tuturor braţelor fluviului printr-un punct O, numit origine. Apoi, din origine pornesc N semidrepte, fiecare reprezentând o porţiune de uscat, astfel încât spaţiul gol dintre 2 semidrepte consecutive va fi considerat un braţ al fluviului.

După ce a desenat schiţa proiectului, NN se întreabă care e numărul de râuri pe care le acoperă complet fiecare baraj. Un baraj acoperă complet un râu dacă intersectează fiecare dintre malurile acestuia. Sarcina voastră este să îl ajutaţi oferindu-i informaţii precise pentru a-şi putea realiza planul cât mai eficient, păstrându-şi renumele.

Ferma lui Algo arată ca o gospodărie mare, în care îşi găsesc locul multe animale şi sunt cultivate pe suprafeţe întinse legume, cereale şi pomi fructiferi. În acest an, pomii a fost atacaţi de o musculiţă care le distruge fructele. Algo a căutat o soluţie pentru îndepărtarea musculiţelor, dar nu a găsit una eficientă. A observat însă că musculiţele sunt sensibile la fum. Aşa că a construit un dispozitiv alcătuit din două ţevi, cu care poate să tragă în acelaşi timp, pe aceeaşi direcţie, dar în sens invers, două baloane speciale umplute cu fum. La fiecare acţionare a dispozitivului sunt lansate cu aceeaşi viteză cele două baloane, care se sparg şi împrăştie fumul la contactul cu copacul.

Deoarece baloanele speciale şi tehnologia lui de a le umple cu fum sunt costisitoare, Algo îşi propune să alunge dăunătorii folosind cât mai eficient resursele. Astfel el vrea să folosească cât mai puţine baloane şi caută posibilitatea de a amplasa dispozitivul într-un punct din fermă care să îi permită trageri eficiente, adică să poată trage în toți pomii din fermă și la fiecare tragere să atingă doi pomi în acelaşi timp.

Determinaţi dacă este posibil să găsească acest punct.

Arpsod vă roagă să faceți un program care, pentru un număr N cunoscut de trageri și poziția fiecărei săgeți pe țintă, determină distanța maximă dintre două săgeți.

Determinaţi costul total minim al segmentelor care pot fi alese pentru a obtura orice fascicul de lumină care
ar pleca din origine către un punct cu ordonata pozitivă.

Pescar împătimit pe râul Olt și pe bălțile din lunca Dunării, Eric a ajuns în Deltă și acum și-a propus să pescuiască pe canalele de aici. Sejurul lui Eric în Deltă începe în ziua 0, atunci când el ajunge la cherhanaua din Tulcea. În fiecare din următoarele n zile pornește din cherhanaua în care se află, merge să pescuiască pe un canal și apoi depozitează peștele prins în altă cherhana (de unde va porni în ziua următoare). El și-a făcut de la început planul stabilind exact la care canal pescuiește în fiecare zi și la care cherhana depozitează peștele prins la finalul zilei respective. Dorește însă să meargă o distanță cât mai mică.
Canalele sunt reprezentate prin drepte în plan iar cherhanalele prin puncte. În prima zi de pescuit, el pleacă de la cherhanaua din Tulcea (să o notăm cherhanaua 0), merge să pescuiască într-un loc din canalul 1, apoi depozitează peștele în cherhanaua 1. Rămâne aici peste noapte, apoi, în ziua 2, pornește din cherhanaua 1, pescuiește într-un loc (punct) de pe canalul 2 și depozitează peștele în cherhanaua 2 etc.
Considerând că pescarul Eric se poate deplasa oricum dorește, determinați distanța minimă pe care o parcurge (suma lungimilor tuturor segmentelor pe care el le parcurge).

Se dau N numere reale considerate ca fiind razele a N discuri. Considerăm că așezăm un disc în sistemul xOy dacă îl plasăm la o coordonată x pozitivă suficient de mare, tangent cu axa Ox și deasupra ei, apoi îl împingem spre Oy până când devine tangent cu Oy sau cu primul disc așezat anterior întâlnit. În figura rezultată după așezarea tuturor discurilor în ordinea dată unele dintre ele pot fi considerate dispensabile, pentru că prin eliminarea lor nu se modifică lățimea totală a figurii, adică nici un disc nu se mai poate deplasa spre stânga. Identificați toate discurile dispensabile din figură.

Numim poligon drept un poligon cu laturile consecutive perpendiculare și lungimile laturilor numere naturale nenule. Un poligon drept cu n laturi este descris de un șir de n numere întregi nenule în care lungimile laturilor sunt date de valoarea absolută a numerelor din șir, iar semnul precizează poziția laturilor, un număr pozitiv însemnând latură spre dreapta sau în sus față de extremitatea laturii precedente, iar un număr negativ însemnând latură în jos sau spre stânga față de extremitatea laturii precedente; de exemplu șirul 1, 1, -1, -1 reprezintă un pătrat de latură 1 (prima latură spre dreapta, a doua în sus, a treia spre stânga, a patra în jos). Vom considera laturile ca fiind orizontale sau verticale, prima latură enumerată fiind orizontală spre dreapta, dacă numărul este pozitiv, sau spre stânga, dacă numărul este negativ.
Se dau unul sau mai multe șiruri de numere întregi nenule.
1. Să se stabilească, pentru fiecare dintre ele, dacă reprezintă un poligon drept.
2. Știind că șirurile date reprezintă poligoane drepte, să se determine aria fiecăruia.