Neka je \(d\) NZD brojeva \(n_1\) i \(n_2\). Ako broj \(n\) nije deljiv brojem \(d\), klikere nije moguće spakovati. U suprotnom, proširenim Euklidovim algoritmom možemo odrediti cele brojeve \(x_1\) i \(x_2\) tako da važi \(x_1n_1 + x_2n_2 = d\), tj.
\[x_1 \cdot \frac{n}{d} \cdot n_1 + x_2 \cdot \frac{n}{d}\cdot n_2 = n\]
Koeficijenti uz \(n_1\) i \(n_2\) predstavljaju brojeve kutija i moraju biti nenegativni, što trenutno ne mora biti slučaj. Sva rešenja prethodne jednačine su oblika
\[\frac{x_1n - kn_2}{d} n_1 + \frac{x_2n + kn_1}{d} n_2 = n\]
Želimo da oba koeficijenta budu pozitivna, pa mora da važi \(x_1n - kn_2 \geq 0\) i \(x_2n + kn_1 \geq 0\), tj.
\[L = \frac{-x_2\cdot n}{n_1} \leq k \leq \frac{x_1\cdot n}{n_2} = U\]
Za datu vrednost \(k\) cena koju plaćamo je
\[\frac{x_1n - kn_2}{d}\cdot c_1 + \frac{x_2n + kn_1}{d} c_2 = \frac{x_1c_1n + x_2c_2n}{d} + \frac{n_1c_2-n_2c_1}{d}\cdot k\]
Vidimo da je u pitanju linearna funkcija po \(k\), što znači da je monotona i da se optimalna vrednost dobija na granicama intervala. Najmanja moguća vrednost \(k\) je \(\left\lceil{L}\right\rceil\), a najveća \(\left\lfloor{U}\right\rfloor\) (ako je \(L \leq U\)). Za ove dve vrednosti \(k\) izračunavamo cenu i biramo povoljniju.
// odredjujemo x1, x2 tako da je x1*n1 + x2*n2 = d
// gde je d nzd brojeva n1 i n2
long long x1, x2;
long long d = prosireni_euklid(n1, n2, x1, x2);
if (n % d != 0)
cout << -1 << endl;
else {
// interval [kL, kU] u kom se nalaze vrednosti k tako
// da oba koeficijenta (x1*n-k*n2) / d i (x2*n+k*n1) / d
// budu pozitivna
long long kL = ceil(-x2 * n / n1);
long long kU = floor(x1 * n / n2);
if (kL > kU) {
cout << -1 << endl;
} else {
// odredjujemo manju cenu
long long m1L = (x1*n - kL*n2) / d;
long long m2L = (x2*n + kL*n1) / d;
long long cL = m1L*c1 + m2L*c2;
long long m1U = (x1*n - kU*n2) / d;
long long m2U = (x2*n + kU*n1) / d;
long long cU = m1U*c1 + m2U*c2;
cout << min(cL, cU) << endl;
}
}#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long prosireni_euklid(long long a, long long b,
long long& x, long long& y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long x0, y0;
long long d = prosireni_euklid(b, a % b, x0, y0);
x = y0; y = x0 - a / b * y0;
return d;
}
int main() {
int n;
cin >> n;
int c1, n1; cin >> c1 >> n1;
int c2, n2; cin >> c2 >> n2;
// odredjujemo x1, x2 tako da je x1*n1 + x2*n2 = d
// gde je d nzd brojeva n1 i n2
long long x1, x2;
long long d = prosireni_euklid(n1, n2, x1, x2);
if (n % d != 0)
cout << -1 << endl;
else {
// interval [kL, kU] u kom se nalaze vrednosti k tako
// da oba koeficijenta (x1*n-k*n2) / d i (x2*n+k*n1) / d
// budu pozitivna
long long kL = ceil(-x2 * n / n1);
long long kU = floor(x1 * n / n2);
if (kL > kU) {
cout << -1 << endl;
} else {
// odredjujemo manju cenu
long long m1L = (x1*n - kL*n2) / d;
long long m2L = (x2*n + kL*n1) / d;
long long cL = m1L*c1 + m2L*c2;
long long m1U = (x1*n - kU*n2) / d;
long long m2U = (x2*n + kU*n1) / d;
long long cU = m1U*c1 + m2U*c2;
cout << min(cL, cU) << endl;
}
}
return 0;
}