1. Veľmi pokazená tlačiareň vzorové riešenie

6 6 6
1 2 2
2 1 1

4

3 4 5
1 1 1
2 2 2

3

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() {
    vector<int> mame(3);
    for(int i = 0; i < 3; i++) {
        cin >> mame[i];
    }
    vector<vector<int>> obrazky(2, vector<int>(3));
    int max_x = INT_MAX;
    for(int typ = 0; typ < 2; typ++) {
        for(int farba = 0; farba < 3; farba++) {
            cin >> obrazky[typ][farba];
            if(typ == 0) {
                max_x = min(max_x, mame[farba] / obrazky[typ][farba]);
            }
        }
    }
    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];
            y = min(y, ostalo_farby / obrazky[1][farba]);
        }
        odpoved = max(odpoved, x + y);
    }
    cout << odpoved << "\n";

    return 0;
}

def nacitaj():
    return [int(t) for t in input().split()]

mame, prvy, druhy = [nacitaj() for _ in range(3)]

odpoved = 0
for x in range(mame[0] + 1):
    ostalo = [mame[farba] - x * prvy[farba] for farba in range(3)]
    if any([farba < 0 for farba in ostalo]):
        break
    y = min([ostalo[j] // druhy[j] for j in range(3)])
    odpoved = max(odpoved, x + y)

print(odpoved)