Riga Crypto

Time limit: 2s Memory limit: 512MB Input: Output:

Banii ușori se fac mulți, banii grei se fac puțini.
--- Evil 'Claus

Cu banii proaspăt primiți de la olimpiade, Alex a decis să investească în criptomonede. Inițial, el deține 11 BTC și dorește să își crească această sumă. Pentru a realiza acest lucru, el va efectua schimburi pe parcursul următoarelor NN zile.

Pe platforma pe care o folosește Alex, există KK criptomonede, numerotate de la 11 la KK, unde 11 reprezintă BTC.

În fiecare zi, Alex primește o listă de schimburi disponibile sub forma unei matrici AA, unde A[i][j]A[i][j] înseamnă că poate schimba o sumă ce o detine xx, nu neaparat intreaga, din moneda ii în A[i][j]xA[i][j] \cdot x din moneda jj. Fiecare tranzacție durează exact o zi pentru a fi procesată, astfel încât Alex nu poate folosi banii schimbați în aceeași zi. Alex poate alege in cadrul unei zile sa nu efectueze niciun schimb.

Cerință

După cele NN zile, Alex dorește să rămână cu cât mai mult BTC. Determinați suma maximă de BTC cu care poate rămâne. Atenție, deoarece această valoare poate să nu fie un întreg, trebuie să afișați rezultatul cu o eroare maximă de 10610^{-6} (vezi secțiunea de output pentru detalii suplimentare și cod).

Date de intrare

Pe prima linie se vor afla NN și KK, numărul de zile, respectiv numărul de criptomonede. Vor urma NN matrici de KK linii a câte KK coloane. Pentru o matrice, numărul de pe linia ii și coloana jj reprezintă cursul în acea zi pentru schimburile din ii în jj. Matricile vor conține numere reale 105<A[i][j]<10510^{-5} < A[i][j] < 10^5.

Date de ieșire

Afisați numărul real xx, care reprezintă suma maximă de BTC cu care poate rămâne Alex. Deoarece xx este un număr real, răspunsul vostru trebuie să aibă o eroare relativă de cel mult 10610^{-6}.

Se garantează că pentru răspunsul final: x1013x \leq 10^{13}.

Fie xrealx_{\textrm{real}} răspunsul corect și xconcx_{\textrm{conc}} răspunsul concurentului. Se vor acorda puncte dacă:

xconcxreal1106\left|\frac{x_{\textrm{conc}}}{x_{\textrm{real}}} - 1\right| \leq 10^{-6}

Pentru a asigura precizia calculelor, vă sugerăm să folosiți tipul de date double sau long double și să includeți următoarele în programul vostru:

#include <iomanip>
#include <iostream>

// ...

std::cout << std::fixed << std::setprecision(10) << x;

Restricții și precizări

  • 1N801 \le N \le 80;
  • 1K501 \le K \le 50;
  • 105<A[i][j]<10510^{-5} < A{[}i{]}{[}j{]} < 10^5 pentru orice ii și jj.
# Punctaj Restricții
1 15 N=1N = 1
2 15 K=2K = 2
3 20 N,K8N, K \leq 8
4 50 Fără restricții suplimentare

Exemplu

stdin

1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0

stdout

2.0000000000

Explicație

N=1N = 1 deci avem o singură zi de schimburi. Vom denumi moneda 22 ETH și moneda 33 TON pentru a face explicațiile mai ușoare. Schimburile posibile aici sunt:


  • BTC -> 2.0 \cdot BTC (nu vom comenta asupra eticii investițiilor lui Alex)
  • BTC -> 1.0 \cdot ETH
  • BTC -> 2.5 \cdot TON

  • ETH -> 1.4 \cdot BTC
  • ETH -> 1.0 \cdot ETH
  • ETH -> 3.14159265359 \cdot TON

  • TON -> 3.0 \cdot BTC
  • TON -> 3.0 \cdot ETH
  • TON -> 3.0 \cdot TON

Atenție!, O tranzacție ia 2424h până se efectuează, deci Alex nu poate folosi 22 tranzacții în aceeași zi. Deci NU poate BTC -> ETH -> BTC cu prețurile dintr-o singură zi. Totuși, poate face BTC -> ETH într-o zi și ETH -> BTC într-o zi ulterioară. In acest exemplu solutia optima e sa ia BTC -> 2 \cdot BTC

Log in or sign up to be able to send submissions!