Fișierul intrare/ieșire	eoliene.in, eoliene.out	Sursă	ONI 2013 clasa a 8-a
Autor	Carmen Mincă	Adăugată de	Tudor Mocioi • tgm000
Timp de execuție pe test	0.1 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Eoliene (clasa a 8-a)

Primarul orașului Oradea intenționează să instaleze N turbine eoliene cu câte trei pale (imaginea alăturată) pentru a produce ecologic, cu costuri minime, energia electrică necesară locuitorilor orașului. Conform planului primarului, cele N turbine eoliene (numerotate cu 1, 2, 3, ..., N) vor fi montate în linie dreaptă, paralel cu șoseaua care leagă Oradea de Băile Felix, la distanțe nu neapărat egale unele de altele. Prima turbină se va instala la distanța D₁ față de Oradea, a doua la distanța D₂ față de Oradea, ..., a N-a turbină la distanță D_N față de Oradea. Palele turbinelor sunt poziționate, în același plan, paralel cu șoseaua. Sub acțiunea vântului, palele turbinelor se rotesc în jurul nacelei (imaginile următoare), vitezele de rotație putând fi diferite de la o turbină la alta.

Primarul a achiziționat turbinele și a angajat echipa inginerului Eol pentru a le construi fundațiile și pentru a le instala. După construirea fundațiilor, înainte de instalare, inginerul Eol a studiat turbinele și a constatat că:

• turbina 1 are cele trei pale identice de lungime L₁, turbina 2 are cele trei pale identice de lungime L₂, ..., turbina N are cele trei pale identice de lungime L_N iar lungimile L₁, L₂, ..., L_N nu sunt toate egale, o parte dintre turbine având palele cu lungimi diferite față de celelalte turbine;
• pilonii celor N turbine sunt identici;
• dacă vor instala turbinele conform planului, atunci pot fi turbine care își pot lovi palele în timpul rotirii și astfel se vor strica.

În concluzie, inginerul Eol va trebui să determine numărul minim M de turbine care pot fi eliminate din planul primarului, astfel încât oricare două turbine dintre cele rămase să nu-și lovească palele în timpul funcționării (palele a două turbine se lovesc dacă se ating chiar și într-un punct), orice valori ar avea vitezele lor de rotație.

Cerință

Scrieți un program care să citească numerele naturale N, D₁, D₂, ..., D_N, L₁, L₂, ..., L_N (cu semnificația din enunț) și să determine numărul minim M de turbine ce pot fi eliminate din planul primarului astfel încât oricare două turbine alăturate din cele rămase să nu-și lovească palele în timpul funcționării.

Date de intrare

Fișierul de intrare eoliene.in conține pe prima linie numărul natural N. A doua linie conține cele N numere naturale D₁, D₂, ..., D_N separate prin câte un spațiu. A treia linie conține cele N numere naturale L₁, L₂, ..., L_N, separate prin câte un spațiu, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire eoliene.out va conține pe prima linie numărul natural M determinat.

Restricții

• Numerele N, D₁, D₂, ..., D_N, L₁, L₂, ..., L_N sunt numere naturale nenule.
• 1 ≤ N ≤ 1000; 1 ≤ D₁, D₂, ..., D_N ≤ 5000; 1 ≤ L₁, L₂, ..., L_N ≤ 2500
• Numerele D₁, D₂, ..., D_N sunt distincte două câte două.
• Lungimea pilonilor este strict mai mare ca lungimea palelor.

Exemplu

Explicație

Sunt N=7 turbine. În planul primarului ele figurează astfel:

Palele perechilor de turbine , (1,3), (3,4) și (6,7) se vor lovi. Astfel, se vor elimina minimum M=3 turbine (turbinele 2, 3 și 6 sau 2,3 și 7 sau 5,3 și 6 sau 5,3 și 7).