Runda 1

CR1P1 Volumul piramidei

Dâ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 fluturilor

Directorul 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 Hambar

Farmer 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]