4141 - Autostrada 1

Cerința

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ă într-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. 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 și precizări

• 2 ≤ N ≤ 2000
• 1 ≤ K ≤ 1.000.000
• 1 ≤ ls, cs ≤ N
• 1 ≤ Cz, Ct, Cp ≤ 100
• diri ∈ {0, 1, 2, 3} pentru orice 1 ≤ i ≤ K
• 1 ≤ pi ≤ N pentru orice 1 ≤ i ≤ K
• Poziția inițială și poziția finală a dronei trebuie asfaltate.
• Datorită testelor mari, doar unele au fost adăugate

Exemplu 1

Intrare

3 3 1 1
1 2 3
1 2
2 3
3 1

Iesire

TRASEU INVALID 2

Exemplu 2

Intrare

5 7 2 1
1 2 3
1 4
2 2
3 3
0 3
1 2
2 1
3 3

Iesire

TRASEU VALID
14

Rezolvare

<syntaxhighlight lang="python" line> def citire_date():

   with open("autostrada.in", "r") as f:
       data = f.read().split()
       
   N = int(data[0])
   k = int(data[1])
   ls = int(data[2]) - 1  # Transformăm în indexare 0-based
   cs = int(data[3]) - 1  # Transformăm în indexare 0-based
   Cz = int(data[4])
   Ct = int(data[5])
   Cp = int(data[6])
   
   instructiuni = []
   index = 7
   for _ in range(k):
       dir = int(data[index])
       p = int(data[index + 1])
       instructiuni.append((dir, p))
       index += 2
       
   return N, k, ls, cs, Cz, Ct, Cp, instructiuni

def deplaseaza_drona(N, ls, cs, instructiuni):

   directii = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # Nord, Est, Sud, Vest
   traseu = set()
   traseu.add((ls, cs))
   
   for idx, (dir, p) in enumerate(instructiuni):
       dx, dy = directii[dir]
       for _ in range(p):
           ls += dx
           cs += dy
           if not (0 <= ls < N and 0 <= cs < N):
               return False, idx + 1
           traseu.add((ls, cs))
   return True, traseu

def calculeaza_cost(traseu, Cz, Ct, Cp):

   cost = 0
   intersectii = {}
   
   for x, y in traseu:
       if (x, y) not in intersectii:
           intersectii[(x, y)] = 0
       intersectii[(x, y)] += 1
   
   for _, count in intersectii.items():
       if count == 1:
           cost += Cz
       elif count == 2:
           cost += Ct
       else:
           cost += Cp
           
   return cost

def scrie_rezultate(valid, result):

   with open("autostrada.out", "w") as f:
       if not valid:
           f.write("TRASEU INVALID\n")
           f.write(f"{result}\n")
       else:
           f.write("TRASEU VALID\n")
           f.write(f"{result}\n")

def main():

   N, k, ls, cs, Cz, Ct, Cp, instructiuni = citire_date()

   # Verificarea restrictiilor
   assert 2 <= N <= 2000, "N trebuie sa fie intre 2 si 2000"
   assert 1 <= k <= 1000000, "k trebuie sa fie intre 1 si 1.000.000"
   assert 0 <= ls < N, "ls trebuie sa fie intre 0 si N-1"
   assert 0 <= cs < N, "cs trebuie sa fie intre 0 si N-1"
   assert 1 <= Cz <= 100 and 1 <= Ct <= 100 and 1 <= Cp <= 100, "Cz, Ct si Cp trebuie sa fie intre 1 si 100"
   assert all(0 <= dir <= 3 for dir, _ in instructiuni), "dir trebuie sa fie intre 0 si 3"
   assert all(1 <= p <= N for _, p in instructiuni), "p trebuie sa fie intre 1 si N"

   valid, result = deplaseaza_drona(N, ls, cs, instructiuni)
   if not valid:
       scrie_rezultate(valid, result)
   else:
       cost = calculeaza_cost(result, Cz, Ct, Cp)
       scrie_rezultate(valid, cost)

if __name__ == "__main__":

   main()

if __name__ == "__main__":

   main()

if __name__ == "__main__":

   main()

</syntaxhighlight>