Fişierul intrare/ieşire:copaci4.in, copaci4.outSursăONI 2012 - clasa a 9-a
AutorVlad IonescuAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Copaci4

Se consideră n copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la 1 la n. Pentru fiecare copac se cunoaşte înălţimea sa Hi. Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac i se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac i considerăm un şir d1, d2, ..., dx reprezentând prietenii copacului i situaţi în dreapta sa şi un şir s1, s2 ... sy reprezentând prietenii copacului i situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac i formează împreună lista prietenilor acestuia. Şirurile corespunzătoare copacului i se definesc astfel:

  1. d1 = i + 1 (dacă i = n, atunci copacul i nu are niciun prieten la dreapta sa, şirul rămânând vid);
    • pentru fiecare k ≥ 2, dk este cel mai mic indice (1 ≤ dk ≤ n) cu proprietatea că dk > dk-1 şi Hdk > Hdk-1 . Dacă dk nu există, atunci lista de prieteni la dreapta ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.
  2. s1 = i - 1 (daca i = 1, atunci copacul i nu are niciun prieten la stânga sa, sirul rămânând vid);
    • pentru fiecare k ≥ 2, sk este cel mai mare indice (1 ≤ sk ≤ n) cu proprietatea că sk < sk-1 şi Hsk > Hsk-1 . Dacă sk nu există, atunci lista de prieteni la stânga ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.

De exemplu, în figura de mai jos sunt reprezentaţi 7 copaci, fiecare având precizată sub el valoarea înălţimii sale. Primul copac din stânga are indicele 1, iar ultimul are indicele 7.

Copacul 1 este prieten cu copacul 2 fiind vecini, cu copacul 5 (deoarece copacul 5 este primul din dreapta lui 2 cu înălţimea mai mare strict decât înălţimea lui 2). La dreapta copacului 5 nu exista niciun copac cu înălţimea mai mare strict decât a sa, deci singurii prieteni ai copacului 1 sunt 2 şi 5.

Pentru copacul 3, prietenii la stânga sa sunt copacii 2 şi 1, iar cei de la dreapta sa sunt copacii 4 şi 5. Pentru copacul 6, singurul prieten la stânga este copacul 5, iar la dreapta copacul 7.

Copacul 7 poate avea prieteni doar la stânga, aceştia sunt 6 şi 5 (la stânga copacului 5 nu mai există niciun copac cu înălţimea mai mare strict decât 8).

Grădinarul Marian vrea să aleagă 3 copaci diferiţi dintre cei n pentru a-i planta în altă grădină. El doreşte ca dintre cei 3 copaci, oricum ar alege A si B, 2 dintre ei, atunci A este prieten cu B şi B este prieten cu A (relaţiile de prietenie se consideră cele stabilite iniţial). Marian are mai multe opţiuni şi se întreabă în câte moduri distincte poate alege cei 3 copaci cu proprietatea cerută.

Cerinţă

Determinaţi în câte moduri se pot alege 3 copaci diferiţi dintre cei n cu proprietatea că, oricum am alege 2 copaci dintre cei 3, fie aceştia copacul A şi copacul B, atunci A este prieten cu B şi B este prieten cu A.

Date de intrare

Fişierul de intrare copaci4.in conţine pe prima linie un număr natural n, reprezentând numărul de copaci, iar pe a doua linie n numere naturale nenule, separate prin câte un spaţiu, reprezentând înălţimile copacilor.

Date de ieşire

Fişierul de ieşire copaci4.out va conţine pe prima linie un număr natural reprezentând numărul de moduri în care Marian poate alege 3 copaci cu proprietatea din enunţ.

Restricţii

  • 1 ≤ n ≤ 200 000;
  • 1 ≤ Hi ≤ 200;
  • nu vor exista 2 copaci alăturaţi cu aceeaşi înălţime;
  • două triplete de copaci se consideră distincte dacă există cel puţin un copac din primul triplet care nu se află şi în al doilea triplet;
  • pentru 30% din teste, 1 ≤ n ≤ 200.

Exemplu

copaci4.incopaci4.outExplicaţie
7
6 4 2 3 8 5 8
4
Copacul 1 este prieten cu copacii: 2, 5
Copacul 2 este prieten cu copacii: 1, 3, 4, 5
Copacul 3 este prieten cu copacii: 1, 2, 4, 5
Copacul 4 este prieten cu copacii: 1, 2, 3, 5
Copacul 5 este prieten cu copacii: 1, 2, 4, 6, 7
Copacul 6 este prieten cu copacii: 5, 7
Copacul 7 este prieten cu copacii: 5, 6
Modurile in care Marian poate alege cei 3 copaci sunt:
(1, 2, 5), (2, 4, 5), (2, 3, 4), (5, 6, 7).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content