Clasa a IX-a
Ziua 2
Problema 4

Scuturi

Pe o linie orizontala, la distante egale, se afla n obiecte punctiforme numerotate de la 1 la n , inzestrate fiecare cu un scut.
Pe o linie paralela cu aceasta se deplaseaza intr-o miscare de "du-te vino" doua dispozitive de tragere care incearca sa distruga obiectivele considerate. Primul dispozitiv porneste din dreptul pozitiei obiectivului 1, se deplaseaza succesiv in dreptul pozitiilor obiectivelor 2, 3, ... , n-1, n, n-1, n-2 ...etc. Al doilea dispozitiv porneste din dreptul pozitiei obiectivului n, se deplaseaza in dreptul obiectivelor n-1, ... 2, 1, 2, 3, ... etc.
Ambele dispozitive parcurg distanta din dreptul pozitiei unui obiectiv pana in dreptul pozitiei obiectivului urmator intr-o secunda. Pentru fiecare dispozitiv se cunoaste un numar p1 respectiv p2 reprezentand numarul de secunde de la ultima tragere dupa care dispozitivul va trage din nou. Orice dispozitiv poate sa traga doar asupra obiectivului in dreptul caruia se afla.
Pentru fiecare obiectiv i se afla un numar r_i (i<=n) reprezentand rezistenta scutului, aceasta insemnand ca obiectivul i este distrus dupa r_i+1 trageri asupra sa.

Observatii:
- Se considera ca dispozitivele se deplaseaza si trag independent unul de celalalt (astfel incat se pot trage asupra aceluiasi obiectiv, in acelasi moment, in acest caz scutul poate fi atacat de doua ori);
- Durata unei trageri este neglijabila ;
- Un dispozitiv continua sa traga si in obiectivele deja distruse(este rusesc !)

Se cere sa se afiseze pe ecran:
a) numarul maxim de obiective care pot fi distruse, considerand miscarea dispozitivelor si resursele de munitie infinite;
b) timpul minim dupa care se reuseste distrugerea obiectivelor numarate la punctul a).
Datele de intrare se gasesc in fisierul SCUT.IN cu urmatorul format:
- pe prima linie se afla numarul n de obiective (2<=n<=30);
- pe linia a doua se afla n numere naturale de cel mult 6 cifre fiecare reprezentand rezistenta scuturilor;
- pe a treia linie se gasesc doua numere naturale reprezentand perioada de tragere a primului, respectiv al celui de-al doilea dispozitiv (p₁, p₂<=n).

Exemplu: daca fisierul SCUT.IN are urmatorul continut:
5
2 1 8 13 2
2 4
pe ecran se vor afisa numerele:
3
34

Observatii: - pentru exemplul de mai sus, obiectivele distruse sunt:    1, 3 si 5;
- timpul minim determinat la b nu va depasi tipul numeric.

Timp maxim de rulare pentru un test: 3 secunde.
Punctaj: 50p.