Zadatak: Kripto trgovina – Analiza i objašnjenje

U ovom zadatku, junak po imenu Alex započinje sa tačno 1 BTC (jednim bitkoinom) i želi da poveća svoj kapital kroz N dana trgovanja kriptovalutama. Svakog dana se na platformi prikazuje matrica kurseva konverzije između različitih valuta.

Na prvi pogled zadatak deluje apstraktno, ali u osnovi simulira stvarno ponašanje kripto-berzi i načine na koje algoritmi pokušavaju da pronađu najprofitabilniju sekvencu konverzija.

1️⃣ Uvod u kriptovalute i Bitcoin

Bitcoin (BTC) je prva i najpoznatija kriptovaluta. Nastao je 2009. godine kao ideja digitalnog novca bez posrednika i centralne banke. Sve transakcije se beleže u javnoj knjizi pod nazivom blockchain.

  • Svaki korisnik ima svoj digitalni novčanik (wallet) i privatni ključ.
  • Trgovanje se odvija na kripto berzama (npr. Binance, Coinbase...).
  • Kurs između valuta (npr. BTC ⇄ ETH) se menja iz sekunde u sekundu.

Kada na primer 1 BTC vredi 20 ETH, to znači da možeš zameniti jedan Bitcoin za 20 Ethera (drugu kriptovalutu). Ako kurs sutra poraste, možeš povratnom konverzijom dobiti više BTC nego što si imao na početku — to je osnova trgovine (tradinga).

2️⃣ Opis zadatka

Alex ima K različitih kriptovaluta, označenih brojevima 1 do K. Broj 1 je rezervisan za BTC. Svakog dana dobija matricu dimenzije K × K, gde A[i][j] označava kurs po kojem može da pretvori količinu x valute i u A[i][j] × x valute j.

Važno pravilo: svaka konverzija traje jedan ceo dan, pa sredstva konvertovana danas ne mogu biti korišćena ponovo istog dana. Alex takođe može odlučiti da tog dana ne obavi nijednu transakciju.

Nakon N dana, Alex želi da završi sa maksimalnom količinom BTC. Tvoj zadatak je da pronađeš taj maksimalni iznos.

□ Ulaz

N K
matrice A dimenzije K × K za svaki dan

□ Izlaz

Jedan realan broj — maksimalna količina BTC koju Alex može imati nakon N dana. Rezultat mora imati relativnu grešku do 10⁻⁶.

3️⃣ Primer

Ulaz:
1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0

Izlaz:
2.0000000000

Objašnjenje: Alex počinje sa 1 BTC. Za ovaj dan, može ga zameniti za 2 ETH ili 2.5 DOGE, ali pošto može izvršiti samo jednu konverziju dnevno, a rezultat meri u BTC, najisplativije je ostati u BTC (po kursu 2.0).

4️⃣ Ideja rešenja

Ovo je tipičan primer zadatka za dinamičko programiranje (DP) po danima i valutama. Ideja je da pamtimo koliku maksimalnu količinu svake valute možemo imati nakon svakog dana, i da je ažuriramo pomoću kurseva. 


dp[day][curr] = maksimalna količina valute curr posle day dana

dp[0][1] = 1      // imamo 1 BTC na početku
dp[0][i] = 0      // ostale valute = 0

dp[d][j] = max_i( dp[d-1][i] * A_d[i][j] )

odgovor = dp[N][1]   // količina BTC posle N dana

Ovde A_d[i][j] predstavlja kurs između valute i i j za dan d. Svaki dan biramo najbolju konverziju i prosleđujemo rezultat sledećem danu.

5️⃣ Rešenje u C++


#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    // 3D vektor: A[d][i][j] predstavlja kurs konverzije iz valute i u valutu j na dan d
    vector>> A(N, vector>(K, vector(K)));

    // Učitavanje svih matrica
    for (int d = 0; d < N; d++)
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                cin >> A[d][i][j];

    // dp[i] = maksimalna količina valute i na kraju trenutnog dana
    vector dp(K, 0.0);
    dp[0] = 1.0; // Početno stanje: imamo 1 BTC (valuta sa indeksom 0)

    // Simulacija trgovanja po danima
    for (int d = 0; d < N; d++) {
        vector next(K, 0.0); // dp za sledeći dan
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                // Ako imam dp[i] jedinica valute i na kraju jučerašnjeg dana,
                // danas ih mogu pretvoriti u valutu j po kursu A[d][i][j]
                next[j] = max(next[j], dp[i] * A[d][i][j]);
            }
        }
        dp = next; // prelazak na stanje sledećeg dana
    }

    // Na kraju nas zanima maksimalna količina BTC (valuta indeks 0)
    cout << fixed << setprecision(10) << dp[0] << "\n";
    return 0;
}

6️⃣ Kako ovo liči na stvarnu kripto trgovinu

U realnom svetu, kripto trgovci (traderi) koriste slične algoritme da automatski biraju najpovoljnije trenutke i parove za zamenu valuta. Cilj je uvek isti: maksimizovati profit u osnovnoj valuti (ovde BTC).

Postoje i specijalni algoritmi za arbitražu – situacije u kojima se, zahvaljujući razlikama u kursu između više valuta, može ostvariti dobit čak i bez rasta tržišta.

Na sličan način, naš DP model kroz više dana pronalazi najpametniji niz konverzija da bi Alex završio sa što više BTC-a.

Vrati se na listu zadataka: interaktivni algoritmi

Ilustracija: prelazi između valuta kroz dane (DP vizualizacija)

Slika prikazuje tri valute (1 = BTC, 2 = ETH, 3 = DOGE) kroz četiri tačke vremena: Day 0 (početno stanje) do Day 3 (nakon 3 dana). Svaka strelica od valute i u danu d do valute j u danu d+1 označava moguću konverziju sa koeficijentom A[d][i][j]. DP bira maksimalan put.

Day 0Day 1Day 2Day 3 BTC (1) ETH (2) DOGE (3) BTC (1) ETH (2) DOGE (3) BTC (1) ETH (2) DOGE (3) BTC (1) ETH (2) DOGE (3) A[0][1][1] A[0][1][2] A[0][1][3] A[0][2][1] A[0][2][2] A[0][2][3] A[0][3][1] A[0][3][2] A[0][3][3] A[1][1][1] A[1][1][2] A[1][2][2] A[1][3][1] A[2][1][1] A[2][3][2] Strelice: moguća konverzija i → j tokom jednog dana; oznaka = A[d][i][j].

Kako čitati dijagram:

  • Kolone predstavljaju dane: Day 0 je početno stanje (pre početka trgovanja), Day 3 je nakon 3 dana.
  • Krugovi predstavljaju valute: 1 = BTC, 2 = ETH, 3 = DOGE.
  • Svaka strelica od i u danu d do j u danu d+1 nosi faktor A[d][i][j]. Ako si imao iznos `v` u valuti `i` na kraju dana `d`, nakon konverzije dobijaš `v * A[d][i][j]` u valuti `j` na početku dana `d+1` (koji će se koristiti za narednu odluku).
  • DP algoritam traži za svaki čvor u sledećoj koloni maksimum preko svih ulaznih strelica — to je upravo operacija next[j] = max(next[j], dp[i] * A[d][i][j]).

Zadatak: Alex i kriptovalute

Alex započinje sa tačno 1 BTC i želi da poveća svoj kapital kroz niz od N dana trgovanja. Na platformi postoji K kriptovaluta, numerisanih od 1 do K, pri čemu je valuta broj 1 uvek BTC.

Opis problema

Svakog dana Alex dobija matricu kurseva dimenzije K × K, gde element A[i][j] označava kurs po kojem može konvertovati iznos x u valuti i u A[i][j] * x jedinica valute j.

Transakcije traju ceo dan, što znači da sredstva konvertovana danas ne mogu biti ponovo korišćena istog dana. Alex može i da odluči da ne obavi nikakvu transakciju tog dana.

Nakon N dana, cilj je da završi sa što većom količinom BTC.

Ulaz i izlaz


Ulaz:
N K
(N matrica K × K realnih brojeva)

Izlaz:
Maksimalna količina BTC-a nakon N dana (realan broj, greška ≤ 1e-6)

Primer


Ulaz:
1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0

Izlaz:
2.0000000000

Kako funkcioniše trgovina kriptovalutama

Bitcoin (BTC) je prva i najpoznatija kriptovaluta. Predstavlja digitalni novac koji funkcioniše nezavisno od banaka, a transakcije se beleže u javnoj knjizi zvanoj blockchain.

Kurs između različitih kriptovaluta (npr. BTC, ETH, LTC) stalno se menja, baš kao i kurs između evra i dolara. U ovom zadatku, ti kursevi su predstavljeni matricom brojeva A[i][j] – koliko jedinica valute j dobijaš za 1 jedinicu valute i.

Primer u praksi

Pretpostavimo da danas možeš zameniti 1 BTC za 2 ETH (Ether), a sutra 1 ETH za 1.5 BTC. Ako danas zameniš BTC u ETH, a sutra ponovo ETH u BTC, završavaš sa 3 BTC nakon 2 dana — što znači profit!

Dakle, zadatak traži da na osnovu dnevnih kurseva pronađeš optimalnu sekvencu konverzija kojom Alex dobija najviše BTC na kraju perioda trgovanja.

Ideja rešenja

Ovo je klasičan dinamički problem optimizacije. Umesto da Alex nasumično menja valute, možemo koristiti dinamičko programiranje da izračunamo za svaku valutu i svaki dan koliki je maksimalan iznos koji se može dobiti.

Neka dp[d][k] označava maksimalnu količinu valute k koju Alex može imati na kraju dana d.

  • Na početku: dp[0][1] = 1 (ima 1 BTC), a ostale valute su 0.
  • Za svaki sledeći dan i svaku valutu računamo najbolju vrednost koristeći matricu kurseva tog dana.
  • Na kraju, rezultat je dp[N][1] – maksimalan broj BTC-a posle svih dana.

Vremenska složenost

Za svaki dan prelazimo kroz sve parove valuta (i, j), pa je složenost O(N × K²), što je izvodljivo za zadate granice (N ≤ 80, K ≤ 50).

Vizualni prikaz

Na slici ispod prikazan je tok trgovanja kroz dane: svaka strelica pokazuje moguću konverziju između valuta. Cilj je pronaći put koji vodi do najvećeg broja BTC jedinica na kraju.

Ilustracija trgovanja kriptovalutama kroz dane

Vrati se na stranicu sa interaktivnim algoritmima: Alex i kriptovalute .