3. Opravte matfyz vzorové riešenie

2 2 3
3 2 1

3

1 2 3
1 2 3

2

3 3 3
50 50 50

9

Úlohou bolo nájsť najrýchlejší možný čas, za ktorý sa dalo splniť \(n\) úloh, pričom splnenie každej trvá \(t\) hodín. Plnenie úloh bolo možné urýchliť (ale aj spomaliť) vyškolením a najatím najviac \(r\) robotníkov, pričom každý má samostatne určenú zručnosť.

Bruteforce

Platí, že jediné spôsoby, akými môžeme ovplyvniť čas splnenia úloh sú:

• počet robotníkov, ktorých najmeme, označme si ho \(i\), pričom \(0\leq i\leq r\) - to je \(r\) možností
• ktorých konkrétnych \(i\) robotníkov z \(r\) si vyberieme - to je \(r \choose i\) možností
• po splnení ktorej úlohy každého z nich vyškolíme - to je \(r^n\) možností.

Čas splnenia \(n\) úloh, pričom každá trvá \(t\) hodín s \(i\) robotníkmi vieme vypočítať v konštantnom čase vzorcom \(\lceil\frac{n}{i}\rceil\cdot t+u\), kde \(u\) je doba školenia daných robotníkov. Pomocou bruteforce teda vyskúšame nájsť čas splnenia úloh pre každú kombináciu týchto faktorov. Pamäťová zložitosť takéhoto riešenia je \(O(r)\), keďže si pamätáme len zručnosť každého robotníka. Časová zložitosť takéhoto riešenia je \(O(r^n)\).

Vlastnosti optimálneho riešenia

Poďme za pozrieť na spôsoby, akými vieme eliminovať niektoré z vyššie opísaných faktorov.

Kedy vyškoliť robotníkov

Zamyslime sa nad tým, kedy sa najviac oplatí školiť robotníkov. Predpokladajme, že už sme našli optimálny počet aj výber konkrétnych robotníkov, ktorých zamestnáme a stačí nájsť už len optimálne úlohy, po ktorých splnení jednotlivých robotníkov vyškolíme. Zrejme platí, že to bude vždy ešte pred začatím stavby, keď nie je splnená ani jedna úloha. Keďže školenie robotníka trvá rovnako dlho bez ohľadu na to, kedy sa začne, nikdy sa neoplatí školenie nejakých robotníkov odkladať, lebo sa tým zbytočne stratí čas, počas ktorého mohli títo robotníci pracovať, ale nepracujú.

Ktorých robotníkov si vybrať

Teraz predpokladajme, že už máme optimálny počet robotníkov a aj sme určili správny moment, kedy ich vyškoliť (už vieme, že to je na začiatku). Môže nastať prípad, kedy je optimálny počet robotníkov menší ako \(r\), čiže si môžeme vyberať, ktorých konkrétnych najmeme. V tomto prípade bude zrejme najoptimálnejšie najať tých najzručnejších, lebo ich školenie zaberie najkratší čas.

Koľko robotníkov vyškoliť

Keďže sme už určili, kedy sa najviac oplatí vyškoliť robotníkov aj ktorých konkrétnych si vybrať, stačí nám už len nájsť optimálny počet robotníkov, ktorý vyškolíme. Nakoľko čas splnenia \(n\) úloh s \(i\) robotníkmi ak každá trvá \(t\) dlho vieme vypočítať v konštantnom čase vzorcom z predošlého riešenia, môžeme si dovoliť vyskúšať všetky možné počty robotníkov, ktoré zaškoliť. Uvedomme si, že ak by sme aj mali možnosť vyškolit viac robotníkov ako je úloh, zrejme sa to nikdy neoplatí, a teda počet robotníkov ktorý sa oplatí vyškolit je zhora ohraničený počtom úloh.

Počet možností bude preto vždy najviac \(\text{min}(r, n)\).

Riešenie

Zhrňme si, ako bude vyzerať nájdenie optimálneho riešenia. Nemusíme skúšať všetky možné úlohy, po ktorých vyškoliť robotníkov, ale ich všetkých vyškoliť hneď zo začiatku. Zároveň nemusíme skúšať všetky možné kombinácie jednotlivých robotníkov, ale vybrať vždy len tých najzručnejších. Zoradenie robotníkov od najzručnejších zaberie \(O(r\log r)\). Tým pádom stačí nájsť len optimálny počet robotníkov. Tento počet nájdeme vyskúšaním všetkých možností. Teda, pre každý počet robotníkov od \(0\) po \(r\) vypočítame, ako dlho bude trvať splnenie úloh a vypíšeme najmenšiu nájdenú hodnotu, čo bude trvať O(r). Pamäťová zložitosť takéhoto riešenia je \(O(r)\), keďže si pamätáme len zručnosť každého robotníka. Časová zložitosť takéhoto riešenia je \(O(r\log r)\).

from math import ceil


def time(n: int, t: int, i: int) -> int:
    """
    Výpočet času do splnenia výstavby.
    :param n: počet úloh
    :param t: počet hodín, ktorý trvá jedna úloha
    :param i: počet robotníkov (bez stavbyvedúceho), ktorí budú robiť úlohy
    :return: Počet hodín, ktorý trvá splnenie n úloh, pričom každá trvá t hodín, \
     plus počet hodín strávený školením i robotníkov
    """
    return suma[i] + ceil(n / (i + 1)) * t


n, t, r = map(int, input().split())
robotnici = list(map(int, input().split()))
robotnici.sort()  # robotníkov zoradíme od najzručnejších (takých, ktorých školenie bude trvať najkratšie) vzostupne

suma = [0] * (r + 1)
# pred for cyklom: suma[i] = 0, 0 <= i <= r
# po for cykle: suma[i] = počet hodín, ktorý trvá zaškolenie i najzručnejších robotníkov
for i in range(r):
    suma[i + 1] = suma[i] + robotnici[i]
print(min(time(n, t, i) for i in range(0, min(r + 1, n))))

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<numeric>

using namespace std;

/**
 * Výpočet času do splnenia výstavby.
 * @param n počet úloh
 * @param t počet hodín, ktorý trvá jedna úloha
 * @param i počet robotníkov (bez stavbyvedúceho), ktorí budú robiť úlohy
 * @param suma časy školení robotníkov
 * @return Počet hodín, ktorý trvá splnenie n úloh, pričom každá trvá t hodín,
     plus počet hodín strávený školením i robotníkov.
 */
long long cas(long long n, long long t, long long i, vector<long long> &suma) {
    return suma[i] + (long long) (ceil((double) n / (double) (i + 1))) * t;
}

int main() {
    long long i, n, t, r;
    cin >> n >> t >> r;

    vector<long long> robotnici(r + 1);
    vector<long long> suma(r + 1);

    for (i = 0; i < r; i++)
        cin >> robotnici[i + 1];

    // robotníkov zoradíme od najzručnejších (takých, ktorých školenie bude trvať najkratšie) vzostupne
    sort(robotnici.begin(), robotnici.end());
    // suma[i] = počet hodín, ktorý trvá zaškolenie i najzručnejších robotníkov
    partial_sum(robotnici.begin(), robotnici.end(), suma.begin());

    long long res = n * t;
    for (i = 0; i < min(r + 1, n + 1); i++) {
        res = min(res, cas(n, t, i, suma));
    }

    cout << res << endl;
}