Rețete

De când am descoperit Chat GPT îl folosesc la orice, inclusiv în bucătărie. De exemplu, astăzi am făcut un inventar al ingredientelor pe care le am în casă sub forma unei liste, în care fiecare linie corespunde unui ingredient sub forma:

denumire_ingredient cantitate unitate_de_măsură

Unitatea de măsură poate fi litrul (indicat prin l), decilitrul (indicat prin dl; 1l = 10dl), centilitrul (indicat prin cl; 1l = 100cl) mililitrul (indicat prin ml; 1l = 1000ml), gramul (indicat prin g), kilogramul (indicat prin kg; 1kg = 1000g) sau bucata (indicată prin b). Cantitatea și denumirea ingredientului, respectiv cantitatea și unitatea de măsură sunt separate prin câte un spațiu.

Apoi i-am dat lui Chat GPT rețetele mele de prăjituri preferate, fiecare rețetă în următorul format:

#nr
descriere listă ingrediente

Rețetele sunt numerotate începând cu 1, în ordinea în care sunt scrise (numărul rețetei fiind specificat după caracterul #). Descrierea listei de ingrediente este în același format cu inventarul ingredientelor pe care le am în casă. Nefiind interesant pentru Chat GPT, am omis descrierea modului de preparare. I-am cerut lui Chat GPT să-mi răspundă la două întrebări:

1. Dacă aș dori să prepar prăjitura dintr-o singură rețetă, care sunt rețetele de prăjituri pe care le-aș putea prepara cu ingredientele pe care le am în casă?
2. Dacă aș dori să prepar mai multe prăjituri, care este numărul maxim de rețete de prăjituri pe care le-aș putea prepara cu ingredientele din inventar, precum și toate combinațiile cu număr maxim de rețete de prăjituri ce aș putea să le prepar.

Chat GPT nu s-a prea descurcat, prin urmare scrieți voi un program care să răspundă la întrebări.

Cerință

Date fiind lista cu inventarul ingredientelor pe care le am în casă, precum și rețetele de prăjituri:

1. determinați numerele de ordine ale rețetelor ce pot fi preparate cu ingredientele din inventar;
2. determinați numărul maxim de rețete distincte de prăjituri care pot fi preparate cu ingredientele din inventar, precum și toate combinațiile cu număr maxim de rețete.

Date de intrare

Fișierul de intrare retete.in conține pe prima linie numărul natural $C$ reprezentând cerința care trebuie să fie rezolvată ($1$ sau $2$). Pe următoarele linii este scris inventarul ingredientelor, câte un ingredient pe o linie, în formatul descris în enunț. În continuare, până la sfârșitul fișierului sunt
scrise rețetele, în formatul din enunț. Pe ultima linie a fișierului de intrare se află caracterul *.

Date de ieșire

Dacă cerința $C = 1$, fișierul de ieșire retete.out conține o singură linie, pe care sunt scrise în ordine crescătoare, separate prin câte un spațiu, numerele rețetelor care pot fi preparate cu ingredientele din inventar. Dacă cerința $C = 2$, fișierul de ieșire retete.out conține pe prima linie numărul maxim de rețete care pot fi preparate cu ingredientele din inventar. Pe următoarele linii sunt scrise în ordine lexicografică combinațiile cu număr maxim de rețete care pot fi preparate cu ingredientele din inventar, fiecare combinație pe o linie. O combinație este o succesiune de numere de rețete, în ordine strict crescătoare, separate prin câte un spațiu.

Restricții și precizări

• În inventar există cel mult $10 \ 000$ de ingrediente distincte.
• În fișierul de intrare există cel mult $100$ de rețete, fiecare rețetă având cel mult 100 de ingrediente, nu neapărat distincte.
• Denumirea unui ingredient are cel mult $30$ de caractere (litere mici, cifre, spațiu sau procent).
• Cantitățile sunt numere naturale nenule $\leq 10 \ 000$.
• Dacă $C = 2$, cu ingredientele din inventar pot fi preparate, individual, cel mult $18$ rețete.
• Un ingredient poate avea unitatea de măsură doar din una dintre următoarele $3$ categorii: unitate de masă (kg, g), unitate de volum (l, dl, cl, ml) sau bucata (b).
• Combinația de rețete $a_1, a_2, \cdots a_N$ precedă în ordine lexicografică combinația de rețete $b_1, b_2, \cdots b_N$ dacă există $k (1 \leq k \leq N)$, astfel încât $a_i = b_i$, pentru orice $1 \leq i < k$ și $a_k < b_k$.

Exemplul 1

retete.in

1
unt 82% 500 g
ulei de floarea soarelui 5 l
faina 000 4 kg
smantana 500 g
zahar 1500 g
zahar pudra 200 g
rahat 500 g
cacao 450 g
rom 2 dl
nuca 2 kg
unt 60% 800 g
vanilie 10 g
zahar vanilat 5 b
ou 30 b
#1
nuca 100 g
ou 2 b
zahar pudra 100 g
unt 82% 220 g
faina 000 300 g
ou 1 b
zahar vanilat 1 b
vanilie 1 g
#2
biscuit 500 g
unt 60% 200 g
rahat 150 g
nuca 150 g
zahar 100 g
cacao 60 g
lapte 200 ml
#3
unt 82% 250 g
smantana 250 g
faina 000 750 g
rahat 400 g
#4
unt 82% 100 g
faina 000 300 g
zahar 100 g
*

retete.out

1 3 4

Explicație

Doar rețetele $1, 3$ și $4$ pot fi preparate cu ingredientele din inventar (deoarece pentru rețeta $2$ este necesar să avem lapte și biscuiți, care nu există în inventar).

Exemplul 2

retete.in

2
unt 82% 500 g
ulei de floarea soarelui 5 l
faina 000 4 kg
smantana 500 g
zahar 1500 g
zahar pudra 200 g
rahat 500 g
cacao 450 g
rom 2 dl
nuca 2 kg
unt 60% 800 g
zahar vanilat 5 b
ou 30 b
#1
nuca 100 g
ou 2 b
zahar pudra 100 g
unt 82% 220 g
faina 000 300 g
ou 1 b
zahar vanilat 1 b
#2
biscuit 500 g
unt 60% 200 g
rahat 150 g
nuca 150 g
zahar 100 g
cacao 60 g
lapte 200 ml
#3
unt 82% 250 g
smantana 250 g
faina 000 750 g
rahat 400 g
#4
unt 82% 100 g
faina 000 300 g
zahar 100 g
*

retete.out

2
1 3
1 4
3 4

Explicație

Maximum $2$ rețete am putea prepara cu ingredientele din inventar, acestea fiind $1$ și $3$, sau $1$ și $4$ sau $3$ și $4$.