Soluții trimise

Rezumat problemă

#3564 copaci1

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 \( {H}_{i} \). 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 \( {d}_{1}, {d}_{2}, …, {d}_{x} \) reprezentând prietenii copacului i situaţi în dreapta sa şi un şir \( {s}_{1}, {s}_{2}, …, {s}_{y} \) 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. \( {d}_{1} = 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, \( {d}_{k} \) este cel mai mic indice (\( 1 ≤ {d}_{k} ≤ n \)) cu proprietatea că \( {d}_{k} > {d}_{k-1} \) şi \( {H}_{{d}_{k}} > {H}_{{d}_{k-1}} \). Dacă \( {d}_{k} \) nu există, atunci lista de prieteni la dreapta ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.
  2. \( {s}_{1} = i – 1 \) (dacă i = 1, atunci copacul i nu are niciun prieten la stânga sa, şirul rămânând vid). Pentru fiecare k ≥ 2, \( {s}_{k} \) este cel mai mare indice (\( 1 ≤ {s}_{k} ≤ n \)) cu proprietatea că \( {s}_{k} < {s}_{k-1} \) şi \( {H}_{{s}_{k}} > {H}_{{s}_{k-1}} \). Dacă \( {s}_{k} \) nu există, atunci lista de prieteni la stânga ai copacului i s-a încheiat şi construirea şirului se opreşte la acest pas.

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.

ID   Utilizator Problema Data încărcării Stare
Ciobanu Dragoș (Dragos_Ciobanu) copaci1 02 Iulie 2021, 18:15 Evaluare finalizată 100
Slanina Simon (Simon271207) copaci1 27 Iunie 2021, 13:25 Evaluare finalizată 100
Slanina Simon (Simon271207) copaci1 27 Iunie 2021, 13:03 Evaluare finalizată 0
Slanina Simon (Simon271207) copaci1 27 Iunie 2021, 11:59 Evaluare finalizată E.C
Militaru Mihai-Alexandru (Defalt_30) copaci1 31 Mai 2021, 09:17 Evaluare finalizată 100
Cozma Tiberiu-Stefan (TibiNyte) copaci1 04 Mai 2021, 16:35 Evaluare finalizată 100
Cozma Tiberiu-Stefan (TibiNyte) copaci1 04 Mai 2021, 16:34 Evaluare finalizată 0
Cozma Tiberiu-Stefan (TibiNyte) copaci1 04 Mai 2021, 16:32 Evaluare finalizată 0
Cozma Tiberiu-Stefan (TibiNyte) copaci1 04 Mai 2021, 16:27 Evaluare finalizată 0
Cozma Tiberiu-Stefan (TibiNyte) copaci1 04 Mai 2021, 16:27 Evaluare finalizată 0
Serban Teodora (Teodora_Maria) copaci1 09 Aprilie 2021, 16:02 Evaluare finalizată 100
Serban Teodora (Teodora_Maria) copaci1 09 Aprilie 2021, 15:57 Evaluare finalizată 0
Todoran Alexandru (alextodoran) copaci1 06 Aprilie 2021, 11:32 Evaluare finalizată 100
Todoran Alexandru (alextodoran) copaci1 06 Aprilie 2021, 11:24 Evaluare finalizată 0
Todoran Alexandru (alextodoran) copaci1 06 Aprilie 2021, 11:09 Evaluare finalizată 0
Todoran Alexandru (alextodoran) copaci1 06 Aprilie 2021, 11:04 Evaluare finalizată 0
Predescu Sebastian Ion (SebastianPredescuIon) copaci1 02 Aprilie 2021, 14:58 Evaluare finalizată 100
Predescu Sebastian Ion (SebastianPredescuIon) copaci1 02 Aprilie 2021, 14:58 Evaluare finalizată 60
Predescu Sebastian Ion (SebastianPredescuIon) copaci1 02 Aprilie 2021, 14:58 Evaluare finalizată 40
Mic Narcis (Narcis44) copaci1 26 Martie 2021, 10:27 Evaluare finalizată 100
Toma Ionut Cristian (TomaIonutCristian) copaci1 20 Martie 2021, 19:01 Evaluare finalizată 100
Peticaru Alexandru (AlexandruPeticaru) copaci1 11 Martie 2021, 12:28 Evaluare finalizată 100
Peticaru Alexandru (AlexandruPeticaru) copaci1 11 Martie 2021, 12:24 Evaluare finalizată 0
Peticaru Alexandru (AlexandruPeticaru) copaci1 11 Martie 2021, 12:21 Evaluare finalizată 0
Peticaru Alexandru (AlexandruPeticaru) copaci1 11 Martie 2021, 11:59 Evaluare finalizată 0
Paul Laurentiu (Shader) copaci1 24 Februarie 2021, 11:28 Evaluare finalizată 100
Paul Laurentiu (Shader) copaci1 24 Februarie 2021, 11:28 Evaluare finalizată 0
Paul Laurentiu (Shader) copaci1 24 Februarie 2021, 11:27 Evaluare finalizată 0
Marcu Cristian (cristiiiy) copaci1 06 Februarie 2021, 20:25 Evaluare finalizată E.C
Croitoru Andrei (andreicroitoru) copaci1 20 Ianuarie 2021, 10:49 Evaluare finalizată 100
Gaşpar Robert - Andrei (gasparrobert95) copaci1 18 Ianuarie 2021, 17:44 Evaluare finalizată 100
Aruxandei Matei - Stefan (MateiStefan) copaci1 15 Ianuarie 2021, 16:41 Evaluare finalizată 100
B &amp; B (BandB) copaci1 11 Ianuarie 2021, 16:10 Evaluare finalizată 100
Eu Cu Mine (NEA__cAiSa) copaci1 08 Ianuarie 2021, 12:53 Evaluare finalizată 100
Eu Cu Mine (NEA__cAiSa) copaci1 08 Ianuarie 2021, 12:34 Evaluare finalizată 0
Andrei Stefan (500_IQ) copaci1 06 Ianuarie 2021, 02:02 Evaluare finalizată 100
POPESCU ANDREI (andreip99) copaci1 13 Decembrie 2020, 11:23 Evaluare finalizată 100
PUICA ANDREI (hacker2017) copaci1 10 Decembrie 2020, 22:38 Evaluare finalizată 100
Pangaleanu Catalin (CatalinPangaleanu) copaci1 07 Decembrie 2020, 14:20 Evaluare finalizată 100
Pangaleanu Catalin (CatalinPangaleanu) copaci1 07 Decembrie 2020, 13:37 Evaluare finalizată 0
HORATIU OPREA (Horatiu) copaci1 10 Noiembrie 2020, 14:01 Evaluare finalizată 100
Bucă Mihnea-Vicențiu (Dap2) copaci1 07 Noiembrie 2020, 20:31 Evaluare finalizată 100
Bucă Mihnea-Vicențiu (Dap) copaci1 07 Noiembrie 2020, 20:11 Evaluare finalizată 100
Bucă Mihnea-Vicențiu (Dap2) copaci1 07 Noiembrie 2020, 20:10 Evaluare finalizată 100
Bucă Mihnea-Vicențiu (Dap2) copaci1 07 Noiembrie 2020, 19:23 Evaluare finalizată 100
Bucă Mihnea-Vicențiu (Dap2) copaci1 07 Noiembrie 2020, 17:57 Evaluare finalizată 0
Bucă Mihnea-Vicențiu (Dap2) copaci1 07 Noiembrie 2020, 17:44 Evaluare finalizată 0
Sacuiu Silviu (silviu_s) copaci1 30 Octombrie 2020, 10:03 Evaluare finalizată 100
Sacuiu Silviu (silviu_s) copaci1 30 Octombrie 2020, 10:02 Evaluare finalizată E.C
Puiu Alexandra (a_puiu) copaci1 16 Octombrie 2020, 00:55 Evaluare finalizată 100