3041 - venus

Enunt

Casa de Modă Venus a decis să se modernizeze şi, începând cu 1 ianuarie 2020 ora 00:00, l-a angajat pe robotul Vasile. Vasile poate executa orice comandă în exact T ore, indiferent de complexitatea acesteia (mai exact, dacă Vasile începe să lucreze la comandă în momentul x, la momentul x+T ore comanda va fi gata de predare). Foarte încrezătoare în calitățile robotului Vasile, Casa de Modă Venus a lansat o campanie publicitară cu sloganul “Dacă am întârziat, primești produsul comandat gratis!”. Campania și-a atins scopul, ca urmare Casa de Modă a primit deja N comenzi pentru întreg anul 2020. Pentru fiecare comandă sunt specificate valoarea acesteia, precum și data și ora până la care produsul comandat trebuie să fie gata de predare. Dacă Vasile predă produsul exact la data și ora specificată în comandă (sau înainte) el încasează valoarea comenzii. Dacă nu, el tot trebuie să execute comanda respectivă, dar nu va primi suma reprezentând valoarea ei. Deși lucrează fără nicio pauză, Vasile estimează că este posibil să nu poată preda la timp toate comenzile, dar își planifică lucrul, astfel încât pierderea să fie minimă (adică suma valorilor comenzilor care nu vor fi predate la timp să fie cât mai mică). Numim planificare optimală succesiunea în care Vasile trebuie să execute cele N comenzi, astfel încât pierderea să fie minimă.

Cerinta

Scrieți un program care, cunoscând informațiile referitoare la cele N comenzi, determină pierderea minimă, precum și o planificare optimală.

Date de intrare

Fișierul de intrare venus.in conține pe prima linie numărul natural N, reprezentând numărul de comenzi și numărul natural T, reprezentând numărul de ore necesare lui Vasile pentru a executa o comandă. Pe următoarele N linii se află informațiile despre comenzi, câte o comandă pe o linie, sub forma: V zi luna ora unde V este valoarea comenzii, zi este ziua în care trebuie predată comanda (un număr natural cuprins între 1 și numărul de zile ale lunii), luna este denumirea lunii, iar ora este un număr natural cuprins între 0 și 23. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu. Comenzile se consideră numerotate de la 1 la N în ordinea din fișierul de intrare.

Date de iesire

Fișierul de ieșire venus.out va conține pe prima linie numărul natural pmin, reprezentând pierderea minimă. Pe a doua linie vor fi scrise N numere naturale distincte cuprinse între 1 și N, separate prin câte un spațiu, reprezentând o planificare optimală.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ T ≤ 500
• 1 ≤ V ≤ 10.000
• Numele lunilor vor fi scrise cu litere mici. Anul 2020 este an bisect, adică luna februarie are 29 de zile.
• Dacă există mai multe planificări optimale, se va accepta orice soluție corectă.
• Se acordă 50% din punctajul pentru fiecare test pentru determinarea valorii pmin. Punctajul integral pentru fiecare test se acordă pentru rezolvarea ambelor cerințe (pmin şi o planificare optimală).

Rezolvare

venusin.txt

4 25

90 10 ianuarie 20

50 2 ianuarie 8

20 4 ianuarie 3

70 2 ianuarie 9

venusout.txt

Datele introduse corespund restrictiilor impuse.

50

4 1 3 2

Exemplul 2

venusin.txt

0 2

3 4 februarie

9 8 iunie

venusout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

def planificare_optimala(comenzi):

   comenzi.sort(key=lambda x: x[2])  # Sortăm comenzile după data și ora limită

   n = len(comenzi)
   dp = [0] * (n + 1)

   for i in range(1, n + 1):
       dp[i] = max(dp[i - 1], comenzi[i - 1][1] - comenzi[i - 1][2])

   pierdere_minima = dp[n]
   planificare = []

   for i in range(n, 0, -1):
       if dp[i] != dp[i - 1]:
           planificare.append(comenzi[i - 1][0])

   planificare.reverse()

   return pierdere_minima, planificare

def main():

   N = int(input("Introduceți numărul de comenzi: "))
   comenzi = []

   for i in range(N):
       valoare = int(input(f"Introduceți valoarea comenzii {i + 1}: "))
       termen_limita = input(f"Introduceți data și ora limită pentru comanda {i + 1} (format YYYY-MM-DD HH:MM): ")
       data_ora_limita = datetime.datetime.strptime(termen_limita, '%Y-%m-%d %H:%M')
       comenzi.append((i + 1, valoare, data_ora_limita))

   pierdere, planificare = planificare_optimala(comenzi)

   print(f"Pierdere minimă: {pierdere}")
   print("Planificare optimală:")
   for comanda in planificare:
       print(f"Comanda {comanda}")

if __name__ == "__main__":

   main()

</syntaxhighlight>