Fişierul intrare/ieşire: | compact3.in, compact3.out | Sursă | ONI 2019, clasele 11-12, ziua 2 |
Autor | Alex Tatomir | Adăugată de | Tinca Matei •TincaMatei |
Timp execuţie pe test | 0.7 sec | Limită de memorie | 131072 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Compact3
Se dă un şir de numere naturale nenule mai mici sau egale cu . Se doreşte partiţionarea şirului în cât mai multe grupe stabile. O grupă stabilă se defineşte ca fiind o secvenţă continuă şi nevidă de numere , respectând următoarea condiţie:
- orice alt element din afara intervalului este ori strict mai mare, ori strict mai mic decât toate valorile din .
Mai exact, pentru orice , doar una din următoarele condiţii este satisfăcută:
- , oricare ar fi ;
- , oricare ar fi .
Partiţionarea şirului presupune ca fiecare număr să facă parte din exact o grupă.
Cerinţă
Dându-se şi şirul de numere, să se găsească o partiţie a şirului în cât mai multe grupe stabile.
Date de intrare
În fişierul compact3.in, pe prima linie se află două numere şi separate prin spaţiu. Pe a doua linie se află cele elemente ale şirului separate prin câte un spaţiu.
Date de ieşire
În fişierul compact3.out se vor afişa două linii. Pe prima linie se va afla numărul maxim de grupe stabile , iar pe a doua linie se vor afla valori, reprezentând poziţia ultimului element al fiecărei grupe stabile în ordine crescătoare.
Restricţii
- .
- .
- , pentru .
- Pentru teste în valoare de 21 puncte .
- Pentru alte teste în valoare de 28 de puncte .
- Se garantează că fiecare număr natural de la 1 la apare cel puţin o dată.
- Ultimul indice din fiecare soluţie va fi întotdeauna .
- În cazul în care există mai multe soluţii cu număr maxim de grupe stabile, se va afişa soluţia minimă lexicografic.
- Un şir este mai mic lexicografic decât un alt şir dacă există un număr întreg mai mic sau egal cu astfel încât: , iar .
Exemplu
compact3.in | compact3.out |
---|---|
6 5 1 4 2 3 5 5 | 5 1 2 3 4 6 |
7 5 1 3 2 1 5 2 4 | 1 7 |
14 10 5 8 6 7 5 2 1 2 3 3 4 10 9 10 | 5 5 8 10 11 14 |
4 3 3 1 2 1 | 2 1 4 |