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)