#703
Salturi
Se dă un șir de numere întregi a[0],a[1],..a[N-1]
. Fiecare valoare a[i]
reprezintă mărimea maximă a unui salt ce poate fi efectuat din pozitia i
. Din poziţia i
, se poate ajunge printr-un salt la oricare din poziţiile i+1, i+2,…, i+a[i]
, dacă a[i]
este pozitiv, iar dacă a[i]
este negativ se poate ajunge la oricare din poziţiile i-1,i-2,…, i+a[i]
.
Trebuie să se ajungă, prin salturi, de la poziția 0
la o poziție mai mare decât N-1
(în afara vectorului, la dreapta).
Scrieți un program care să determine numărul minim de salturi necesare pentru a ajunge de la poziția 0
la o poziție mai mare decât N-1
.
Lot Juniori, Baia Mare, 2013
Problema | Salturi | Operații I/O |
![]() salturi.in /salturi.out
|
---|---|---|---|
Limita timp | 0.3 secunde | Limita memorie |
Total: 16 MB
/
Stivă 16 MB
|
Id soluție | #43077373 | Utilizator | |
Fișier | salturi.cpp | Dimensiune | 613 B |
Data încărcării | 30 Martie 2023, 08:37 | Scor / rezultat | 90 puncte |
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0.016 secunde | OK. | 10 | 10 | ||
2 | 0 secunde | OK. | 10 | 10 | ||
3 | 0 secunde | OK. | 10 | 10 | ||
4 | 0.008 secunde | OK. | 10 | 10 | ||
5 | 0.016 secunde | OK. | 10 | 10 | ||
6 | 0.084 secunde | OK. | 10 | 10 | ||
7 | 0.08 secunde | OK. | 10 | 10 | ||
8 | 0.088 secunde | OK. | 10 | 10 | ||
9 | 0.092 secunde | OK. | 10 | 10 | ||
10 | Depășit | Limita de timp depășită | 10 | 0 | ||
Punctaj total | 90 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Salturi face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.