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.
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.
Vrati se na stranicu sa interaktivnim algoritmima: Alex i kriptovalute .