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
a a (eduardm) copaci1 07 August 2020, 10:56 Evaluare finalizată 100
LAZAR INGRID (Hell_Giver2079) copaci1 06 August 2020, 11:58 Evaluare finalizată 100
💻 Vlad-Laurentiu Nicu (nicuvlad76) copaci1 04 August 2020, 08:32 Evaluare finalizată 100
Ionel Ionelut (0p) copaci1 03 August 2020, 16:20 Evaluare finalizată 0
Ionel Ionelut (0p) copaci1 03 August 2020, 16:20 Evaluare finalizată 0
Ionel Ionelut (0p) copaci1 03 August 2020, 16:19 Evaluare finalizată 0
Ionel Ionelut (0p) copaci1 03 August 2020, 16:12 Evaluare finalizată 30
Ionel Ionelut (0p) copaci1 03 August 2020, 16:03 Evaluare finalizată 0
Ionel Ionelut (0p) copaci1 03 August 2020, 16:03 Evaluare finalizată 0
Ionel Ionelut (0p) copaci1 03 August 2020, 15:52 Evaluare finalizată 0
Ionel Ionelut (0p) copaci1 03 August 2020, 15:52 Evaluare finalizată 0
Bindea Mihai (mihaitab) copaci1 01 August 2020, 03:50 Evaluare finalizată 0
Bindea Mihai (mihaitab) copaci1 01 August 2020, 03:49 Evaluare finalizată 0
Bindea Mihai (mihaitab) copaci1 01 August 2020, 03:41 Evaluare finalizată 0
Horodniceanu Andrei (Horodniceanu_A) copaci1 31 Iulie 2020, 19:35 Evaluare finalizată 0
Horodniceanu Andrei (Horodniceanu_A) copaci1 31 Iulie 2020, 19:24 Evaluare finalizată 0
Horodniceanu Andrei (Horodniceanu_A) copaci1 31 Iulie 2020, 18:50 Evaluare finalizată 0
Horodniceanu Andrei (Horodniceanu_A) copaci1 31 Iulie 2020, 18:41 Evaluare finalizată 0
Raluca Sylvie (ralucasylvie) copaci1 29 Iulie 2020, 11:30 Evaluare finalizată 100
No One (John_The_Tester) copaci1 27 Iulie 2020, 22:42 Evaluare finalizată E.C
andra andra (andrraaa) copaci1 26 Iulie 2020, 11:44 Evaluare finalizată 100
Soare Cristian-Constantin (CristianConstantinSoare) copaci1 25 Iulie 2020, 15:13 Evaluare finalizată 100
Profu de Info (persoanapersonala) copaci1 17 Iulie 2020, 10:53 Evaluare finalizată 100
Horodniceanu Andrei (Horodniceanu_A) copaci1 16 Iulie 2020, 14:08 Evaluare finalizată 0
Horodniceanu Andrei (Horodniceanu_A) copaci1 15 Iulie 2020, 19:22 Evaluare finalizată 0
Horodniceanu Andrei (Horodniceanu_A) copaci1 14 Iulie 2020, 19:33 Evaluare finalizată E.C
Aspru Octavian (oaspru) copaci1 12 Iulie 2020, 10:20 Evaluare finalizată 100
‮ ‮ (oni) copaci1 11 Iulie 2020, 16:04 Evaluare finalizată 0
Marin Alexandru Remus (N4S4Vranci) copaci1 11 Iulie 2020, 11:33 Evaluare finalizată 100
Chiriac Casian (Sebastianul) copaci1 09 Iulie 2020, 09:20 Evaluare finalizată 0
Arama Alexandru (Alexandru_Arama) copaci1 06 Iulie 2020, 23:14 Evaluare finalizată 100
skylake59 . (skylake59) copaci1 06 Iulie 2020, 20:18 Evaluare finalizată 100
Quintus Maximus (mquintus) copaci1 06 Iulie 2020, 11:15 Evaluare finalizată 0
Camilla Camilla (camilla) copaci1 05 Iulie 2020, 22:34 Evaluare finalizată 100
Moldoveanu Traian Florian Alin (traianflorianalin) copaci1 05 Iulie 2020, 15:44 Evaluare finalizată 100
Gelu Ionescu (test111) copaci1 05 Iulie 2020, 10:11 Evaluare finalizată 100
✔️ Popa Adrian (a53) copaci1 04 Iulie 2020, 22:16 Evaluare finalizată 100
Bodnar Andrei (andreibodnar1) copaci1 04 Iulie 2020, 16:22 Evaluare finalizată 100
Ciornei Stefan (Joergen) copaci1 04 Iulie 2020, 11:14 Evaluare finalizată 100
Lucky l (CristianMacesan) copaci1 04 Iulie 2020, 11:14 Evaluare finalizată 100
Lucky l (CristianMacesan) copaci1 04 Iulie 2020, 11:02 Evaluare finalizată 10
Lucky l (CristianMacesan) copaci1 04 Iulie 2020, 10:41 Evaluare finalizată 0
‭ ‭ (May_9th) copaci1 04 Iulie 2020, 10:22 Evaluare finalizată 100
Lorintz Alexandru (Alex_tz307) copaci1 04 Iulie 2020, 09:24 Evaluare finalizată 100
Lorintz Alexandru (Alex_tz307) copaci1 27 Iunie 2020, 19:34 Evaluare finalizată 100