Fișierul intrare/ieșire gogosi.in, gogosi.out Sursă Concurs Infogim 2017 clasa a 5-a
Autor Vlad Turcuman Adăugată de avatar Isabela_coman Coman Isabela Patricia Isabela_coman
Timp de execuție pe test 0.6 sec Limită de memorie 5120 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Gogoși (clasa a 5-a)

La magazinul X sunt N persoane așezate la coadă pentru gogoși. Din cauza aglomerației, managerul vrea să împartă persoanele la mai multe case. Deoarece toată lumea trebuie să vadă gogoșile, înălțimea fiecărei persoane trebuie să fie mai mică sau egală decât înălțimile tuturor celor de după el în coada lui. Mai mult, dacă persoana i în șirul inițial și persoana j în șirul inițial (i < j) ajung în aceeași coadă, persoana i trebuie să fie înaintea persoanei j. Dându-se N, numărul de persoane și A, înălțimile persoanelor în ordinea inițială, să se afișeze numărul minim de case pe care managerul trebuie să le deschidă.

Date de intrare

În fișierul gogosi.in se află pe prima linie numărul N iar pe a doua linie N numere naturale, Ai reprezentând înălțimea persoanei i din coada inițială.

Date de ieșire

Afișați pe prima linie din fișierul gogosi.out numărul minim de case care trebuie deschise.

Restricții

  • 1 ≤ N ≤ 106
  • 1 ≤ Ai ≤ 105
  • 1 ≤ Ai ≤ 2 pentru teste în valoare de 20 puncte.
  • 1 ≤ N ≤ 103 pentru teste în valoare de alte 30 puncte.

Exemplu

gogosi.in gogosi.out Explicații
7
1 4 2 3 9 7 6
3
Numărul minim de case care trebuie deschise este
3. Există mai multe variante de a împărți
persoanele, una dintre acestea este:
Coada 1:
i 1 2 5 (persoanele din sirul initial)
A[i] 1 4 9 (inaltimile lor)
Coada 2:
i 3 6 (persoanele din sirul initial)
A[i] 2 7 (inaltimile lor)
Coada 3:
i 4 7 (persoanele din sirul initial)
A[i] 3 6 (inaltimile lor)
5
1 2 1 1 2
2
Numărul minim de case care trebuie deschise este
2. Una dintre variante este:
Coada 1:
i 1 2 (persoanele din sirul initial)
A[i] 1 2 (inaltimile lor)
Coada 2:
i 3 4 5 (persoanele din sirul initial)
A[i] 1 1 2 (inaltimile lor)

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii