Fișierul intrare/ieșire superhedgy.in, superhedgy.out Sursă OJI 2022, clasele 11-12 (OSEPI)
Autor Mihaela Cismaru Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.5 sec Limită de memorie 32768 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

SuperHedgy (clasele 11-12)

Ariciul Gălușcă este un arici obișnuit pe timp de zi. Noaptea, însă, el este de fapt eroul misterios al orașului Hedgytown – un oraș mai special, deoarece are clădiri atât deasupra solului, cât și sub pamânt, unde gravitația este inversată.

Orașul poate fi văzut ca o dreaptă (ce reprezintă solul), cu un șir de clădiri dreptunghiulare lipite deasupra solului, și un șir de clădiri dreptunghiulare lipite dedesubtul solului. Sunt N clădiri peste pământ și M sub pământ. Cele două șiruri încep și se termină la aceleași poziții. Fiecare clădire este caracterizată de trei valori: L, H și E. L reprezintă lățimea clădirii, H reprezintă înălțimea clădirii și E reprezintă efortul necesar pentru a folosi liftul din acea clădire.

Inițial, Gălușcă se afla pe partea din stânga a orașului, la nivelul solului (în dreptul primei clădiri) și trebuie să ajungă pe partea din dreapta a orașului, tot la nivelul solului (în dreptul ultimei clădiri). În acest scop, el se poate deplasa pe contururile clădirilor, consumând o unitate de efort pentru a se deplasa o unitate pe conturul unei clădiri – sau folosind lifturile.

O deplasare cu liftul este mereu de pe conturul unei clădiri până pe conturul clădirii aflate pe cealaltă parte a solului – cu alte cuvinte, când folosește liftul, ariciul nu are voie să se deplaseze doar până la sol sau să se oprească în interiorul clădirii. În cazul în care clădirea pe care se află ariciul necesită efortul E pentru a folosi liftul și clădirea de pe partea opusă a solului necesită efortul E’, atunci efortul total necesar pentru a folosi liftul este E + E’.

Deplasarea cu liftul se efectuează vertical. Astfel, liftul îl va lăsa pe Gălușcă la aceeași distanță orizontală față de începutul orașului, doar că pe acoperișul clădirii opuse. Liftul nu poate fi folosit unde se întâlnesc două clădiri adiacente orizontal – nici dacă se întâlnesc pe partea solului de unde începe deplasarea, nici dacă se întâlnesc pe partea solului unde se termină deplasarea. Atenție, cum Gălușcă este un erou, acesta nu va merge niciodată înapoi – doar va înainta sau va folosi lifturile.

Cerință

Se cere să se afle numărul minim de unități de efort pe care trebuie să le depună ariciul Gălușcă pentru a ajunge la destinația sa.

Date de intrare

Pe prima linie a fișierului de intrare superhedgy.in se dă N, reprezentând numărul de clădiri de deasupra solului.

Pe următoarele N linii ale fișierului de intrare se dau L, H, și E, reprezentând datele clădirilor de deasupra solului, în ordinea în care sunt plasate în oraș începând cu cea mai apropiată clădire de Gălușcă.

Pe linia N+2 a fișierului de intrare se află M, reprezentând numărul de clădiri dedesubtul solului.

Pe următoarele M linii ale fișierului de intrare se dau L, H, și E, reprezentând datele clădirilor de dedesubtul solului, în ordinea în care sunt plasate în oraș începând cu cea mai apropiată clădire de Gălușcă.

Date de ieșire

Fișierul de ieșire superhedgy.out va conține un singur număr natural, reprezentând numarul minim de unități de efort pe care trebuie să le depună Gălușcă pentru a ajunge la destinație.

Restricții și precizări

  • 1 ≤ N, M ≤ 100.000
  • 1 ≤ L, H ≤ 1.000.000.000
  • 0 ≤ E ≤ 1.000.000.000
  • Suma lungimilor clădirilor de deasupra și de dedesubtul pământului coincid. Fie LTotal această lungime totală.
  • Pentru 20 de puncte, 1 ≤ LTotal ≤ 10
  • Pentru 20 de puncte, E = 0 pentru toate clădirile din oraș, 1 ≤ LTotal ≤ 100.000
  • Pentru 40 de puncte, 1 ≤ LTotal ≤ 100.000
  • Pentru 20 de puncte, fără restricții suplimentare

Mențiune

  • Rezultatele evaluării pot fi diferite față de cele din concurs.

Exemplu

superhedgy.in superhedgy.out
3
1 2 5
3 1 1
2 3 1
4
1 4 10
2 3 1
1 2 1
2 1 1
13

Explicație

Orașul va arăta ca în figura de mai jos:

Un traseu posibil al ariciului va fi următorul:

Atenție! Deplasarea cu liftul nu s-ar fi putut efectua mai la stânga sau mai la dreapta cu 0.5 unități.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii