Fişierul intrare/ieşire:maxp.in, maxp.outSursăOJI 2013 clasa a 8-a
AutorDan PracsiuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.7 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Maxp (clasa a 8-a)

Considerăm un şir de numere a1, a2, ..., aN. O secvenţă nevidă în acest şir este de forma ai, ai+1, ..., aj, unde i ≤ j. De exemplu, pentru N=4 şi şirul 2 3 4 3, secvenţele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 3. Definim puterea unui element ai ca fiind numărul de secvenţe care-l conţin pe ai şi în care ai este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul 2 3 4 3 puterea elementului a1 este 1 (fiind maxim doar în secvenţa formată din el însuşi), a elementului a2 este 2 (a2 fiind maxim în secvenţele 2 3 şi 3), a elementului a3 este 6 (fiind maxim în secvenţele 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 şi 4 3), iar a elementului a4 este 1.

Cerinţă

Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.

Date de intrare

Fişierul maxp.in conţine pe prima linie numărul natural N, iar pe a doua linie, în ordine, numerele naturale a1, a2, ..., aN separate prin câte un spaţiu.

Date de ieşire

Fişierul maxp.out va conţine pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şir care au cea mai mare putere.

Restricţii

  • 2 ≤ N ≤ 200000
  • Elementele şirului sunt numere naturale şi au cel mult 6 cifre

Exemple

maxp.inmaxp.outExplicaţii
7
9 3 4 5 1 2 2
12
1
Elementul 5 de pe poziţia 4 este maxim în 12 secvenţe:
3 4 5, 3 4 5 1, 3 4 5 1 2, 3 4 5 1 2 2, 4 5,
4 5 1, 4 5 1 2, 4 5 1 2 2, 5, 5 1, 5 1 2,
5 1 2 2, deci puterea lui este 12. Este singurul element care are această putere,
celelalte elemente având puteri mai mici.
6
1 0 7 7 2 6
3
2
Elementele din poziţiile 3 şi 4 sunt maxime în 3 secvenţe, deci puterea lor este 3.
Celelalte elemente au puteri mai mici.
Trebuie sa te autentifici pentru a trimite solutii. Click aici