Runda 1CR1P1 Volumul piramideiDându-se coordonatele a patru puncte din spațiu să se determine volumul tetraedrului determinat de cele 4 puncte. Datele de intrare se vor citi din fișierul VOLUM.IN care conține pe patru linii câte trei numere reale reprezentând coordonatele celor patru puncte. Volumul tetraedrului (cu o aproximație de 0.001) va fi scris în fișierul VOLUM.OUT. În cazul în care cele patru puncte nu pot determina un tetraedru fișierul de ieșire va conține numai numărul 0. Programul va trebui să furnizeze rezultatul în cel mult o secundă. Exemplu VOLUM.IN VOLUM.OUT 0 0 0 0.167 1 0 0 0 1 0 0 0 1
CR1P2 Dansul fluturilorDirectorul circului Hilbert s-a hotărât să adauge un nou act la spectacol și a ales dansul fluturilor care este dansat, simultan, de n fluturi numerotați de la 1 la n. Inițial fluturii se află în câmpuri numerotate de la 1 la n. Există n săgeți desenate în câmpuri astfel încât din fiecare câmp pornește exact o săgeată și în fiecare câmp ajunge exact o săgeată. La început fiecare fluture se află în câmpul cu numărul corespunzător (al k-lea fluture se află în câmpul k). La fiecare secundă, fiecare fluture sare din câmpul în care se află în câmpul indicat de săgeata ce pornește din acel câmp (toți fluturii sar deodată). Dansul fluturilor se termină când toți fluturii se află din nou în pozițiile din care au plecat. Directorul vrea ca spectacolul să dureze cât mai mult posibil, deci trebuie să realizeze o aranjare inteligentă a săgeților. Scrieți un program care citește numărul n al fluturilor și determină o aranjare a săgeților astfel încât spectacolul să dureze cât mai mult timp posibil. Programul trebuie să determine și durata spectacolului (T). Din fișierul FLUTURI.IN se va citi numărul n al fluturilor (1<n<1000), iar în fișierul FLUTURI.OUT se va scrie timpul T (în secunde). Programul va trebui să furnizeze rezultatul în cel mult o secundă. Exemplu FLUTURI.IN FLUTURI.OUT 8 15
CR1P3 HambarFarmer John dorește să amplaseze un hambar mare de formă pătrată pe terenul de formă pătrată al fermei sale. Deoarece nu-i place să taie copaci la ferma sa, vrea să găsească o locație pentru hambarul său care să-i permită să-l construiască pe un teren fără copaci. Pentru scopurile noastre, terenul lui a fost împărțit în N*N parcele. Intrarea conține o listă cu parcelele care conțin copaci. Sarcina voastră este de a determina cel mai mare hambar de formă pătrată care poate fi amplasat pe teren fără să fie nevoie ca unii copaci să fie tăiați. Laturile hambarului trebuie să fie paralele cu axa orizontală, respectiv cea verticală. Exemplu Să considerăm următoarea reprezentare a terenului lui Farmer John unde .' reprezintă o parcelă care nu conține copaci, iar #' o matrice care conține copaci. 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . # . . . . . 7 . . . . . . . . 8 . . . . . . . . Cel mai mare hambar are dimensiunea 5*5 și poate fi amplasat în partea din dreapta-jos a matricei, în oricare dintre cele două moduri posibile. Date de intrare Datele se citesc din fișierul HAMBAR.IN care conține: · pe prima linie două numere întregi N (1ŁNŁ200) și T (1ŁTŁ500) reprezentând numărul de parcele de pe o latură, respectiv numărul parcelelor pe care cresc copac; · pe liniile 2..T+1 două numere întregi din intervalul [1,n] indicând linia și coloana unei parcele pe care cresc copaci. Date de ieșire Fișierul HAMBAR.OUT va conține o singură linie pe care se va scrie lungimea maximă a unei laturi a hambarului. Exemplu INPUT.TXT OUTPUT.TXT 8 3 5 2 2 2 6 6 3
Timp maxim de execuție/test: 1 secundă [cuprins] |