Fişierul intrare/ieşire:gogosi.in, gogosi.outSursăConcurs Infogim 2017 clasa a 5-a
AutorVlad TurcumanAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test0.6 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Gogosi ( 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 coadă lui. Mai mult, dacă persoana i în şirul iniţial şi persoana j în şirul iniţial (i < j) ajung în aceeaşi coadă, persoană 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 numarul N iar pe a doua line N numere naturale, Ai reprezentând înălţimea persoanei i din coadă 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.ingogosi.outExplicaţ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)

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici