Zadanie
Od neskorého večera do neskorého rána, tlačiaren v T2 tlačila. Mišof a Hodobox vstúpili dnu. Po chvíli skúmania zistili, že vytlačené sú iba dva druhy obrázkov. Mišofovi hneď napadlo, že by časť, alebo aj všetky obrázky mohli použiť na oblepenie stien. A tak sa s Hodoboxom zhodli, že na vyfarbenie každého obrázku použijú béžovú, ružovú a modrú. Z týchto farieb však mali obmedzený počet voskoviek, ktoré mohli použiť na vyfarbovanie obrázkov. A preto chcú zistiť, koľko najviac obrázkov dokážu vyfarbiť.
Úloha
Mišof s Hodoboxom Vám povedali, koľko majú voskoviek jednotlivých farieb. Pre oba typy obrázka viete, koľko voskoviek ktorej farby potrebujú na jeho vyfarbenie.
Vašou úlohou je povedať, koľko najviac obrázkov Mišof a Hodobox dokážu vyfarbiť.
Formát vstupu
Na prvom riadku vstupu sú 3 medzerou oddelené prirodzené čísla \(b,\,r,\,m\) – počet béžových, ružových a modrých voskoviek, ktoré majú Mišof s Hodoboxom k dispozícii.
Nasledujú dva riadky. V \(i\)-tom z nich sú čísla \(b_i,\,r_i,\,m_i\) – počty voskoviek jednotlivých farieb, ktoré sa spotrebujú na jeden obrázok typu \(i\).
Formát výstupu
Na jediný riadok výstupu vypíšte najväčší počet obrázkov, ktoré vedia Mišof a Hodobox vyfarbiť.
Hodnotenie
Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq b,\,r,\,m\, \leq\) | \(100\) | \(10\,000\) | \(100\,000\) | \(1\,000\,000\) |
\(1 \leq b_i,\,r_i,\,m_i\, \leq\) | \(300\) | \(30\,000\) | \(300\,000\) | \(3\,000\,000\) |
Príklad
Input:
6 6 6
1 2 2
2 1 1
Output:
4
Mišof a Hodobox vyfarbia po dva obrázky z každého druhu.
Input:
3 4 5
1 1 1
2 2 2
Output:
3
V tomto prípade vedia vyfarbiť 3 obrázky prvého druhu.
V tejto úlohe sme mali zistiť, koľko obrázkov vedia Mišof a Hodobox vyfarbiť, keď majú dané koľko ktorých voskoviek majú k dispozícii a koľko ktorých voskoviek je potrebných na vyfarbenie každého typu obrázku.
Vzorové riešenie
Nech v optimálnom riešení máme \(x\) obrázkov typu 1 a \(y\) obrázkov typu 2. Našou úlohou je zistiť čísla \(x, y\) tak, aby \(x + y\) bolo maximálne možné.
Môžeme postupne skúšať všetky dosiahnuteľné hodnoty \(x\). Ku každej z nich si ľahko vieme dorátať, koľko ktorých voskoviek nám ostane po vyfarbení \(x\) obrázkov typu 1. Všetky tieto zvyšné voskovky môžeme použiť na vyfarbenie čo najviac obrázkov druhého typu. Jednoducho si teda dorátame číslo \(y\).
Skúsme sa bližšie pozrieť na to, ako dopočítať číslo \(y\). Ak sme na \(x\) obrázkov prvého typu použili \(x_b = x \cdot b_1\) voskoviek béžovej, \(x_r = x \cdot r_1\) ružovej a \(x_m = x \cdot m_1\) voskoviek modrej farby, tak na obrázky typu 2 nám ostalo \(y_b = b - x_b\) voskoviek béžovej, \(y_r = r - x_r\) ružovej a \(y_m = m - x_m\) modrej farby. Ako zistíme, koľko obrázkov druhého typu vieme týmito voskovkami zafarbiť? Na vyfarbenie jedného obrázku typu 2 potrebujeme \(b_2, r_2, m_2\) voskoviek príslušných farieb. Jedna z týchto farieb voskoviek sa nám minie ako prvá. Obrázkov typu 2 teda vieme vyfarbiť \(y = \min\{ \frac{y_b}{b_2}, \frac{y_r}{r_2}, \frac{y_m}{m_2} \}\).
Pre nejaké nami zvolené \(x\) sme teda dopočítali maximálne možné \(y\). Na doriešenie úlohy nám teda stačí postupne skúsiť všetky možné \(x\), ku každému dopočítať \(y\) a vypísať tú možnosť, kde bolo \(x + y\) najväčšie.
Prečo to funguje? Pretože skúšame všetky možnosti. Žiadna nám teda neunikne.
Zložitosť
Koľko rôznych \(x\) potrebujeme skúšať? Na každý obrázok spotrebujeme aspoň jednu voskovku každého druhu. Stačí nám teda vyskúšať \(\min\{ b, r, m \}\) možností pre \(x\). Ku každému vieme potom dopočítať \(y\) v konštantnom čase. Časová zložitosť teda bude \(O(\min\{ b, r, m \})\).
Pamätať si nám stačí jednotlivé počty voskoviek, ktoré máme k dispozícii a doteraz najlepšie nájdené \(x, y\). Stačí nám teda konštantná pamäť a pamäťová zložitosť bude \(O(1)\).
#include <bits/stdc++.h>
using namespace std;
int main() {
<int> mame(3);
vectorfor(int i = 0; i < 3; i++) {
>> mame[i];
cin }
<vector<int>> obrazky(2, vector<int>(3));
vectorint max_x = INT_MAX;
for(int typ = 0; typ < 2; typ++) {
for(int farba = 0; farba < 3; farba++) {
>> obrazky[typ][farba];
cin if(typ == 0) {
= min(max_x, mame[farba] / obrazky[typ][farba]);
max_x }
}
}
int odpoved = 0;
// Skusime postupne vsetky mozne x
for(int x = 0; x <= max_x; x++) {
int y = INT_MAX; // Kolko obrazkov typu 2 vieme este vyfarbit zvysnymi voskovkami
for(int farba = 0; farba < 3; farba++) {
int ostalo_farby = mame[farba] - x * obrazky[0][farba];
= min(y, ostalo_farby / obrazky[1][farba]);
y }
= max(odpoved, x + y);
odpoved }
<< odpoved << "\n";
cout
return 0;
}
def nacitaj():
return [int(t) for t in input().split()]
= [nacitaj() for _ in range(3)]
mame, prvy, druhy
= 0
odpoved for x in range(mame[0] + 1):
= [mame[farba] - x * prvy[farba] for farba in range(3)]
ostalo if any([farba < 0 for farba in ostalo]):
break
= min([ostalo[j] // druhy[j] for j in range(3)])
y = max(odpoved, x + y)
odpoved
print(odpoved)
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.