Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | sume3.in, sume3.out | Sursă | utcn-2021 |
Autor | Tudor Muresan | Adăugată de | Ciprian Oprisa •cypry |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sume de subsecvențe
Se dă o secvenţă de întregi pozitivi , care se împarte în subsecvenţe disjuncte care concatenate dau secvenţa iniţială.
Se consideră sumele întregilor subsecvenţelor :
Scrieţi un program care să împartă secvenţa de numere în subsecvenţe astfel ca valoarea maximă a unei sume , () să fie minimă (adică dintre toate împărţirile posibile).
Date de intrare
Fişierul de intrare sume3.in conţine mai multe exemple de test. Un exemplu are pe prima linie doi întregi separaţi de un spaţiu determinând numărul al întregilor secvenţei şi numărul al subsecvenţelor. Pe linia următoare se dau cei întregi separaţi de un spaţiu. Fişierul se termină cu o linie conţinând un 0.
Date de ieşire
Fişierul de ieşire sume3.out conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de ':' şi de cea mai mică valoare maximă a sumei unei subsecvenţe posibil a fi obţinută la o împărţire a secvenţei date.
Restricţii
Exemplu
sume3.in | sume3.out |
---|---|
5 3 1 2 3 4 5 3 2 4 78 9 | 1:6 2:82 |
Explicaţie
...