fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4.  
  5. void Code_By_Mohamed_Khaled() {
  6.     ios_base::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     cout.tie(nullptr);
  9. #ifndef ONLINE_JUDGE
  10.     freopen("input.txt", "r", stdin);
  11.     freopen("output.txt", "w", stdout);
  12. #endif
  13. }
  14.  
  15. double a;           // initial amount
  16. string initCrypto;  // initial currency
  17. ll N;               // number of opportunities
  18.  
  19. vector<string> baseC, quoteC;
  20. vector<double> priceP;
  21.  
  22. // For each currency, list of indices where it appears as base or quote
  23. unordered_map<string, vector<int>> mpBase, mpQuote;
  24.  
  25. // memo[i][cur] = best value of 1 unit of cur in terms of initial crypto
  26. vector<unordered_map<string,double>> memo;
  27.  
  28. double dp_solve(int idx, const string &cur) {
  29.     if (idx == N) {
  30.         // if no more opportunities, only 1 unit of initial currency has value 1,
  31.         // others have 0 value
  32.         return (cur == initCrypto ? 1.0 : 0.0);
  33.     }
  34.     auto it = memo[idx].find(cur);
  35.     if (it != memo[idx].end()) return it->second;
  36.  
  37.     double best = (cur == initCrypto ? 1.0 : 0.0);
  38.  
  39.     // try using any future opportunity where cur is the base currency
  40.     auto &vecB = mpBase[cur];
  41.     auto itB = lower_bound(vecB.begin(), vecB.end(), idx);
  42.     while (itB != vecB.end()) {
  43.         int j = *itB;
  44.         // convert 1 unit cur -> priceP[j] units of quoteC[j]
  45.         double val = priceP[j] * dp_solve(j+1, quoteC[j]);
  46.         best = max(best, val);
  47.         ++itB;
  48.     }
  49.     // try using any future opportunity where cur is the quote currency
  50.     auto &vecQ = mpQuote[cur];
  51.     auto itQ = lower_bound(vecQ.begin(), vecQ.end(), idx);
  52.     while (itQ != vecQ.end()) {
  53.         int j = *itQ;
  54.         // convert 1 unit cur -> (1/priceP[j]) units of baseC[j]
  55.         double val = (1.0/priceP[j]) * dp_solve(j+1, baseC[j]);
  56.         best = max(best, val);
  57.         ++itQ;
  58.     }
  59.  
  60.     return memo[idx][cur] = best;
  61. }
  62.  
  63. int main() {
  64.     Code_By_Mohamed_Khaled();
  65.     cout << fixed << setprecision(6);
  66.  
  67.     ll t;
  68.     cin >> t;
  69.     while (t--) {
  70.         cin >> a >> initCrypto >> N;
  71.  
  72.         baseC.assign(N, "");
  73.         quoteC.assign(N, "");
  74.         priceP.assign(N, 0.0);
  75.         mpBase.clear();
  76.         mpQuote.clear();
  77.         memo.clear();
  78.         memo.resize(N+1);
  79.  
  80.         for (int i = 0; i < N; i++) {
  81.             cin >> baseC[i] >> quoteC[i] >> priceP[i];
  82.             mpBase[baseC[i]].push_back(i);
  83.             mpQuote[quoteC[i]].push_back(i);
  84.         }
  85.         // ensure index lists are sorted (they are in insertion order already)
  86.         // but just in case:
  87.         for (auto &p : mpBase) sort(p.second.begin(), p.second.end());
  88.         for (auto &p : mpQuote) sort(p.second.begin(), p.second.end());
  89.  
  90.         // solve for value of 1 unit of initCrypto
  91.         double rate = dp_solve(0, initCrypto);
  92.         // multiply by initial amount
  93.         double answer = rate * a;
  94.         cout << answer << "\n";
  95.     }
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
1
100 BTC 9
XRP ETH 0.0006
ETH BTC 0.04
ADA ETH 0.001
XRP ETH 0.001
ETH ADA 900
ADA BTC 0.0001
BTC ETH 32
AXD GTR 10
FDS YTR 20
stdout
copy 
250.000000
https://ideone.com/Buo5tX
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!