#3032
sufle
Sufle este un personaj cu urechi ascuțite, îndrăgostit de algoritmică. El are o antipatie profundă față de Aisimok, cel care îl tot provoacă să rezolve probleme folosind tot felul de formule. Sufle a botezat aceste probleme Emsiteanap. Astăzi Aisimok i-a aruncat tânărului Sufle o nouă provocare:
Pentru oricare două numere naturale se definește următoarea operație:
Pentru un șir oarecare de numere naturale, se poate aplica de oricâte ori și asupra oricăror două numere operația descrisă mai sus. Scopul final este ca suma pătratelor numerelor din șir să ajungă la valoarea minim posibilă. Denumim costul șirului acestă valoare minimă.
Pentru a deveni și mai antipatic, Aisimok îi cere lui Sufle să calculeze aceast cost pentru mai multe subsecvențe ale unui șir dat. Costul unei subsecvențe este egal cu costul șirului definitit de subsecvența dată.
Cerința: Pentru un șir cunoscut și pentru mai multe subsecvențe date să se calculeze suma minimă a pătratelor numerelor din subsecvență după aplicare a operației descrise, de oricâte ori se consideră necesar și asupra oricăror numere din subsecvență.
Baraj ONI 2017
Problema | sufle | Operații I/O |
![]() sufle.in /sufle.out
|
---|---|---|---|
Limita timp | 2 secunde | Limita memorie |
Total: 256 MB
/
Stivă 256 MB
|
Id soluție | #42521657 | Utilizator | |
Fișier | sufle.cpp | Dimensiune | 1.71 KB |
Data încărcării | 08 Martie 2023, 22:05 | Scor / rezultat | 100 puncte |
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0 secunde | OK. | 8 | 8 | ||
2 | 0 secunde | OK. | 8 | 8 | ||
3 | 0 secunde | OK. | 7 | 7 | ||
4 | 0.02 secunde | OK. | 7 | 7 | ||
5 | 0.004 secunde | OK. | 5 | 5 | ||
6 | 0.012 secunde | OK. | 5 | 5 | ||
7 | 0.008 secunde | OK. | 5 | 5 | ||
8 | 0.04 secunde | OK. | 5 | 5 | ||
9 | 0.02 secunde | OK. | 5 | 5 | ||
10 | 0.02 secunde | OK. | 5 | 5 | ||
11 | 0.132 secunde | OK. | 10 | 10 | ||
12 | 0.132 secunde | OK. | 10 | 10 | ||
13 | 0.076 secunde | OK. | 5 | 5 | ||
14 | 0.04 secunde | OK. | 5 | 5 | ||
15 | 0.02 secunde | OK. | 5 | 5 | ||
16 | 0.02 secunde | OK. | 5 | 5 | ||
Punctaj total | 100 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema sufle 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ă.