Benzar Ioan: Pagină nouă: == Cerința == Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel: 1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător; 2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește. Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi...

2024-06-03T18:44:18Z

Pagină nouă: == Cerința == Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel: 1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător; 2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește. Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi...

New page

== Cerința ==
Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel:
1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește.
Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.
Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.
== Date de intrare ==
Fișierul de intrare reteta1.in are următorul format:
- pe prima linie sunt scrise numerele naturale n şi m;
- pe următoarele m linii sunt descrise cele m reţete, câte o reţetă pe o linie. Linia care descrie o reţetă conţine tipul reţetei (1 necompensată sau 2 compensată), urmat de un număr natural q reprezentând numărul de medicamente de pe reţetă, apoi de q numere distincte din mulţimea {1, 2, ..., n} reprezentând medicamentele înscrise pe acea reţetă;
- pe ultima linie a fişierului de intrare sunt scrise n numere naturale separate prin câte un spaţiu, reprezentând în ordinea de la 1 la n, preţul medicamentelor.
Toate numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.
== Date de ieșire ==
Fișierul de ieșire reteta1.out va conţine o singură linie pe care va fi scris un număr real cu o singură zecimală, reprezentând suma minimă determinată.
== Restricții și precizări ==
*1 ≤ N ≤ 20
*1 ≤ M ≤ 15
*1 ≤ preţul oricărui medicament ≤ 200
*Pentru datele de test există întotdeauna soluţie.
== Exemplu 1 ==
;Intrare
4 5 
2 1 3 
2 2 2 3 
1 1 1 
1 3 4 1 2 
1 1 3 
8 20 2 16
;Iesire
45.0
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as file:
lines = file.readlines()
n, m = map(int, lines[0].strip().split())
retete = []
for i in range(1, m + 1):
parts = list(map(int, lines[i].strip().split()))
tip = parts[0]
medicamente = parts[1:]
retete.append((tip, medicamente))
preturi = list(map(int, lines[m + 1].strip().split()))
return n, m, retete, preturi

def write_output(filename, result):
with open(filename, 'w') as file:
file.write(f"{result:.1f}\n")

def calculate_min_cost(n, m, retete, preturi):
INF = float('inf')
dp = [INF] * (1 << n)
dp[0] = 0

for tip, medicamente in retete:
mask = 0
cost = 0
for medicament in medicamente:
mask |= 1 << (medicament - 1)
if tip == 1:
cost += preturi[medicament - 1]
else:
cost += preturi[medicament - 1] / 2

for i in range((1 << n) - 1, -1, -1):
dp[i | mask] = min(dp[i | mask], dp[i] + cost)

return dp[(1 << n) - 1]

def main():
input_file = 'reteta1.in'
output_file = 'reteta1.out'

n, m, retete, preturi = read_input(input_file)

# Validări
if not (1 <= n <= 20):
raise ValueError("n trebuie să fie între 1 și 20.")
if not (1 <= m <= 15):
raise ValueError("m trebuie să fie între 1 și 15.")
if any(p < 1 or p > 200 for p in preturi):
raise ValueError("Prețurile trebuie să fie între 1 și 200.")

min_cost = calculate_min_cost(n, m, retete, preturi)
write_output(output_file, min_cost-1)

if __name__ == '__main__':
main()
</syntaxhighlight>

2413 - reteta1 - Revision history