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 D1 faţă de Oradea, a doua la distanţa D2 faţă de Oradea,..., a N-a turbină la distanţă DN 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 L1, turbina 2 are cele trei pale identice de lungime L2, ..., turbina N are cele trei pale identice de lungime LN iar lungimile L1, L2, ..., LN 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, D1, D2, ..., DN, L1, L2, ..., LN (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 D1, D2, ..., DN separate prin câte un spaţiu. A treia linie conţine cele N numere naturale L1, L2, ..., LN, 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
• 1 ≤ N ≤ 1000
• 1 ≤ D1, D2, ..., DN ≤ 5000
• 1 ≤ L1, L2, ..., LN ≤ 2500
• Numerele D1, D2, ..., DN sunt distincte două câte două. • Lungimea pilonilor este strict mai mare ca lungimea palelor.
Exemple
eoliene.in
eoliene.out
Explicaţii
7
27 9 28 37 3 54 50
1 5 5 4 5 2 2
3
Sunt N=7 turbine. În planul primarului ele figurează astfel:
Palele perechilor de turbine (2,5), (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).
