Fișierul intrare/ieșire autostrada.in, autostrada.out Sursă ONI 2022 baraj gimnaziu
Autor Theodor-Gabriel Tulbă-Lecu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 2 sec Limită de memorie 131072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Autostrada (baraj gimnaziu)


Gimi tocmai a câștigat o licitație pentru asfaltarea unei noi autostrăzi. Firma lui este responsabilă de prelucrarea zonelor dintr-o suprafață bidimensională de dimensiuni N × N. Știm că dacă un drum va trece prin a i-a linie, respectiv a j-a coloană, atunci acea zonă de la poziția (i, j) va trebui asfaltată. Liniile și coloanele suprafeței bidimensionale sunt numerotate de la 1 la N. Din nefericire pentru el, a aflat abia după semnarea contractului că proiectul nu este așa de simplu precum a crezut. Drumul va fi determinat de traseul urmat de o dronă. Mai mult, Gimi nici nu știe acest traseu, dar a primit de la proiectantul autostrăzii poziția inițială a dronei (ls, cs), reprezentând linia și coloana zonei în care se află inițial drona, și o listă de K instrucțiuni pe care acesta le-a aplicat dronei. Fiecare instrucțiune este o pereche de tipul (dir , p), cu semnificația că drona s-a deplasat pe direcția dir cu p unități, unde dir poate avea următoarele valori:

  • 0 – direcția Nord
  • 1 – direcția Est
  • 2 – direcția Sud
  • 3 – direcția Vest

Spre exemplu, dacă drona se află în poziția (1, 3) și a primit instrucțiunea (2, 3), atunci drona se va deplasa spre sud (direcția 2) cu 3 unități și va parcurge zonele (2, 3), (3, 3) și (4, 3) unde se va opri. Toate aceste zone vor trebui asfaltate de firma lui Gimi.

Costul de asfaltare al unei zone prin care trece un drum simplu este Cz . Din fericire pentru Gimi, o zonă parcursă de mai multe ori de dronă trebuie asfaltată o singură dată. Însă, el a observat că pot apărea niște cazuri particulare:

  • Dacă într-o zonă se produce o intersecție de tip , înseamnă că este nevoie de benzi de accelerare/decelerare în intersecție. Atunci costul de asfaltare al zonei devine Ct.
  • Dacă intr-o zonă se produce o intersecție de tip +, înseamnă că este nevoie de construirea unui pod, caz în care costul de asfaltare al zonei devine Cp.





Cele patru tipuri de intersecții de tip
Intersecție de tip +

Cerință

Având aceste informații, Gimi vrea să verifice dacă traseul dronei este valid, adică drona nu va părăsi niciodată suprafața de care este responsabilă firma lui Gimi. În cazul în care traseul este invalid Gimi vrea să știe a câta instrucțiune dintre cele K a determinat mutarea dronei în afara suprafeței. Dacă traseul este valid, el vrea să determine costul total de asfaltare al autostrăzii.

Date de intrare

Prima linie din fișierul de intrare autostrada.in va conține patru numere naturale N, K, ls și cs, unde N este dimensiunea suprafeței, K este numărul de instrucțiuni aplicate dronei, iar (ls, cs) reprezintă linia și coloana zonei în care se află inițial drona. A doua linie va conține trei numere naturale Cz Ct și Cp, reprezentând costurile de asfaltare ale unei zone simple, unei intersecții de tip , respectiv unei intersecții de tip +.

Următoarele K linii vor conține câte două numere naturale diri și pi , reprezentând valorile specifice celei de-a i-a instrucțiuni primite de dronă. Numerele scrise pe aceeași linie sunt separate printr-un singur spațiu.

Date de ieșire

Dacă traseul dronei este invalid, pe prima linie din fișierul de ieșire autostrada.out se va afișa textul TRASEU INVALID, iar apoi, pe a doua linie, un singur număr natural, reprezentând a câta instrucțiune dintre cele K a determinat mutarea dronei în afara suprafeței. Altfel, pe prima linie din fișierul de ieșire se va afișa textul TRASEU VALID, iar apoi, pe a doua linie, un singur număr natural reprezentând costul total necesar pentru asfaltarea autostrăzii.

Restricții

  • 2 ≤ N ≤ 2 000
  • 1 ≤ K ≤ 1 000 000
  • 1 ≤ ls, cs ≤ N
  • 1 ≤ Cz, Ct, Cp ≤ 100
  • diri ∈ {0, 1, 2, 3} pentru orice 1 ≤ iK
  • 1 ≤ piN pentru orice 1 ≤ iK
  • Poziția inițială și poziția finală a dronei trebuie asfaltate.

Task-uri


Punctaj Restricții
1
14
Traseul este invalid
2
6
1 ≤ K ≤ 2 000 traseul este valid și nu conține niciun tip de intersecție
3
8
1 ≤ K ≤ 2 000 traseul este valid și nu conține intersecții de tip +
4
9
1 ≤ K ≤ 2 000 traseul este valid și nu conține intersecții de tip
5
24
1 ≤ K ≤ 2 000 traseul este valid
6
39
Traseul este valid

Exemple

În exemplele de mai jos, cu verde s-au marcat zonele ce trebuiesc asfaltate, iar cu linii albe s-a indicat traseul dronei. Zonele gri sunt zone nevizitate de traseul dronei.

autostrada.in autostrada.out Explicații
3 3 1 1
1 2 3
1 2
2 3
3 1
TRASEU INVALID
2
A doua instrucțiune este invalidă, drona ieșind din suprafață întrucât ar ajunge la
coordonatele (4, 3).
5 7 2 1
1 2 3
1 4
2 2
3 3
0 3
1 2
2 1
3 3
TRASEU VALID
17
Traseul determinat de dronă este:
 
Se observă că toate zonele, mai puțin (2, 2) și (2, 4) sunt simple, adică nu sunt intersecții,
și fiecare au costul de asfaltare Cz = 1.
În (2, 2) avem o intersecție de tip +, deci costul de asfaltare va fi Cp = 3.
În (2, 4) avem o intersecție de tip ⊤, deci costul de asfaltare va fi Ct = 2.
În total, costul este 12 × 1 + 1 × 2 + 1 × 3 = 17.

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

Indicii de rezolvare

Arată 5 categorii