MELE2 - ELEVATOR II
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define long long long
#define li pair<long, int>
#define X first
#define Y second
const long oo = 1000000000000000001ll;
const int N = 100005;
using namespace std;
long res, n;
long k[4];
long d[N];
void Dijkstra() {
priority_queue<li, vector<li>, greater<li> > Q;
int u, v; long du;
Q.push(li(0, 0));
for(int i = 1; i < k[1]; i++) d[i] = oo;
while (Q.size()) {
u = Q.top().Y; du = Q.top().X; Q.pop();
if (du != d[u]) continue;
for(int i = 2; i <= 3; i++) {
v = (u + k[i]) % k[1];
if (d[v] > d[u] + k[i]) {
d[v] = d[u] + k[i];
Q.push(li(d[v], v));
}
}
}
}
int main()
{
cin >> n; cin >> k[1] >> k[2] >> k[3]; sort(k + 1, k + 4);
Dijkstra();
n--;
for(int i = 0; i < k[1]; i++) {
if (d[i] > n) continue;
res += (n - i) / k[1] - (d[i] - i) / k[1] + 1;
}
cout << res;
return 0;
}