1. Zlacnené disky vzorové riešenie

5 1000 2
3 47 190 50 30

3

4 200 10
3 2 10 20

3

3 1000 1
100 10 1

1

Úlohou bolo zistiť, v ktorý deň je najvýhodnejšie zaplatiť zvyšok dlhu.

Potrebujeme teda pre každý deň zistiť, koľko eur by Matúš celkovo zaplatil, ak by vyplatil zvyšok dlhu v tento deň. Potom nám stačí vybrať najskorší deň kedy je táto suma najnižšia.

Otázkou ostáva, ako počítať sumu v eurách, ktorú by zaplatil, ak by ukončil splácanie v \(i\)-ty deň. Táto suma sa skladá z dvoch častí:

Prvá časť je to, čo musel zaplatiť každý deň splácania – \(i\)-krát výška splátky, teda \(i \cdot s\).

Druhá časť musí pokrývať nesplatený zvyšok ceny v taiwanských dolároch. Tento zvyšok vypočítame ako rozdiel ceny disku a súčtu hodnôt všetkých doterajších splátok. Ak si teda označíme kurz \(i\)-teho dňa ako \(k_i\), zvyšok je \(c - s \cdot (k_1 + k_2 + ... + k_i)\).

Môžeme si všimnúť, že ak poznáme zvyšok v \(i\)-ty deň, ľahko vieme vypočítať zvyšok v \(i+1\) deň, a to tak že od zvyšku v \(i\)-ty deň odrátame hodnotu splátky v \(i+1\) deň – \(s \cdot k_{i+1}\)¹.

Keď už poznáme zvyšok, ktorý treba pokryť, vydelíme ho kurzom na tento deň a získame sumu v eurách ktorú treba doplatiť. Nakoľko chceme platiť celočíselne, túto sumu ešte zaokrúhlime nahor.

Celkovú sumu, ktorú Matúš zaplatí, ak sa rozhodne doplatiť dlh v \(i\)-ty deň vieme teda vypočítať ako \[ i \cdot s + \left\lceil \frac{c - s \cdot (k_1 + k_2 + ... + k_i)}{k_i} \right\rceil\]

Keď poznáme celkovú sumu, stačí ju porovnať s doteraz najnižšou sumou ktorú sme vyrátali, a ak je lepšia, tak si uložíme číslo tohto dňa. Treba si dať pozor, aby sme výpočet zastavili potom, ako sa zvyšok stane záporným, lebo vtedy je už disk splatený.

Zložitosť

Ak postupujeme tak, ako sme popisovali vyššie, stačí nám v každom z \(n\) krokov prečítať hodnotu kurzu na tento deň a spraviť konštantne veľa jednoduchých výpočtov a porovnaní, ktoré majú konštantnú časovú zložitosť. Preto celková časová zložitosť bude \(O(n)\).

Lepšie sa to dokonca ani nedá, keďže na vstupe máme kurzy na \(n\) dní, ktoré musíme načítať².

Pamäťová zložitosť je \(O(1)\), pretože si stačí pamätať len zvyšok, ktorý treba zaplatiť z predošlého dňa a kurz v daný deň.

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int n, cena, splatka, best = 1234567890, den = 1, kurz;
    cin >> n >> cena >> splatka;
    for (int i=0; i<n; i++){
        cin >> kurz;
        cena -= kurz * splatka; // kolko taiwanskych dolarov zostava zaplatit

        // kolko eur by zaplatil ak skonci tento den
        int teraz = (i + 1) * splatka;
        if(cena>0) teraz += ceil(cena/kurz);

        if (teraz < best){
            best = teraz;
            den = i + 1;
        }

        if (cena < 0) break;
    }
    cout << den << endl;
}

uses crt, math;
var n, cena, splatka, best, teraz, den, kurz, i:longint;
begin
    best := 1234567890;
    den := 1;
    read(n, cena, splatka);
    for i := 1 to n do
    begin
        read(kurz);
        dec(cena, kurz * splatka);

        teraz := i * splatka;
        if cena > 0 then inc(teraz, ceil(cena / kurz));

        if teraz < best then
        begin
            best := teraz;
            den := i;
        end;

        if cena < 0 then break;
    end;
    writeln(den);
end.