Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;

int a,b,c,i,num;
long long n,re,d[100000],f[100000];

void push(long long x,long long y)
{
     if (d[x]<0 || d[x]>y)
     {
         num++;
         f[num]=x;
         d[x]=y;
     }     
}

int main()
{
    cin >> n >> a >> b >> c;
    fr(i,0,c-1) d[i]=-1;
    d[0]=0; i=0; 
    while (i<=num)
    {
          push((f[i]+a)%c,d[f[i]]+a);
          push((f[i]+b)%c,d[f[i]]+b);
          i++;         
    }
    fr(i,0,c-1)
       if (d[i]>=0 && d[i]<n)
         re+=(n-1-d[i])/c+1;
    cout << re << endl;
    return 0;
}

Code mẫu của happyboy99x

#include<cstring>
#include<queue>
#include<iostream>
using namespace std;

const int N = 1e5;
long long d[N], h;
int a, b, c, INF;

void enter() {
    cin >> h >> a >> b >> c;
}

void solve() {
    memset(d, 0x3f, sizeof d);
    d[0] = 0;
    priority_queue<pair<long long, int> > q;
    q.push(make_pair(0, 0));
    while(!q.empty()) {
        long long du = -q.top().first;
        int u = q.top().second; q.pop();
        if(d[(u + a) % c] > du + a) {
            d[(u + a) % c] = du + a;
            q.push(make_pair(-d[(u + a) % c], (u + a) % c));
        }
        if(d[(u + b) % c] > du + b) {
            d[(u + b) % c] = du + b;
            q.push(make_pair(-d[(u + b) % c], (u + b) % c));
        }
    }
}

void print() {
    long long res = 0;
    for(int u = 0; u < c; ++u) {
        if(d[u] >= h) continue;
        res += (h - d[u] - 1) / c + 1;
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    solve();
    print();
    return 0;
}

Code mẫu của ladpro98

#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;
}

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100111;
  oo=1000111000111000111;
var
  f1,f2:text;
  n:int64;
  hsize,a,b,c:longint;
  d:array[0..MAXN] of int64;
  h,hpos:array[0..MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure swap(var a,b:longint); inline;
var temp:longint;
begin temp:=a; a:=b; b:=temp; end;

procedure inp;
begin
  read(f1,n);
  read(f1,a,b,c);
  if a>b then swap(a,b);
  if a>c then swap(a,c);
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
      if (d[h[j]]<d[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (d[h[i]]<d[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]); hpos[h[1]]:=1;
  dec(hsize);
  downHeap(1);
end;
procedure solve;
var
  u,v:longint;
begin
  for u:=0 to a-1 do d[u]:=oo;
  d[1 mod a]:=1; push(1 mod a);
  while (hsize>0) do
    begin
      pop(u);
      v:=(u+b) mod a;
      if d[v]>d[u]+b then
        begin
          d[v]:=d[u]+b;
          if hpos[v]=0 then push(v)
          else upHeap(hpos[v]);
        end;
      v:=(u+c) mod a;
      if d[v]>d[u]+c then
        begin
          d[v]:=d[u]+c;
          if hpos[v]=0 then push(v)
          else upHeap(hpos[v]);
        end;
    end;
end;
procedure ans;
var
  u:longint;
  count,ln:int64;
begin
  count:=0;
  for u:=0 to a-1 do
    begin
      ln:=(n div a)*a+u;
      if ln>n then ln-=a else if ln+a<=n then ln+=a;
      if ln>=d[u] then count+=(ln-d[u]) div a+1;
    end;
  if count=0 then count:=1;
  writeln(f2,count);
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 100005
#define maxe 100005

ll n;
int a, b, c, add[2], du[2], f[maxn];
priority_queue<II> que;

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    cin >> n >> a >> b >> c;
    if(a == 1){
        cout << n;
        return 0;
    }
    ms(f, 0x3f);
    f[1 % a] = 0;
    add[0] = b / a; du[0] = b % a;
    add[1] = c / a; du[1] = c % a;
    que.push(mp(0, 1 % a));
    int u, v, c, cong;
    while(!que.empty()){
        u = que.top().se; c = -que.top().fi; que.pop();
        if(f[u] < c) continue;
        Rep(i, 2){
            if(u + du[i] >= a) cong = 1;
            else cong = 0;
            v = (u + du[i]) % a;
            if(f[v] > f[u] + add[i] + cong){
                f[v] = f[u] + add[i] + cong;
                que.push(mp(-f[v], v));
            }
        }
    }
    ll res = 0;
    Rep(i, a){
        if(f[i] < inf && n >= i)
            res += max((n - i) / a - f[i] + 1, 0ll);
    }
    cout << res;

    return 0;
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MELE2;
Const
  input  = '';
  output = '';
  maxn = 3;
  maxd = 100000;
  maxv = 1000000000000000001;
Var
  fi,fo: text;
  a: array[1..maxn] of integer;
  d: array[0..maxd] of qword;
  heap,pos: array[0..maxd] of integer;
  free: array[0..maxd] of boolean;
  nHeap: integer;
  h,res: qword;

Procedure init;
Var
  i: integer;
Begin
  Assign(fi, input);
    Reset(fi);

  Readln(fi, h);
  For i:= 1 to maxn do read(fi, a[i]);

  Close(fi);
End;

Procedure swap(var x,y: integer);
Var
  z: integer;
Begin
  z:= x;
  x:= y;
  y:= z;
End;

Procedure sort;
Var
  i,j: integer;
Begin
  For i:= 1 to maxn - 1 do
    For j:= i + 1 to maxn do
      if a[i] > a[j] then swap(a[i],a[j]);
End;

Procedure update(v: integer);
Var
  child,parent: integer;
Begin
  child:= pos[v];
  If child = 0 then
    Begin
      inc(nHeap);
      child:= nHeap;
    End;

  parent:= child div 2;
  While (parent > 0) and (d[heap[parent]] > d[v]) do
    Begin
      heap[child]:= heap[parent];
      pos[heap[child]]:= child;

      child:= parent;
      parent:= child div 2;
    End;

  heap[child]:= v;
  pos[v]:= child;
End;

Function pop: integer;
Var
  r,c,v: integer;
Begin
  pop:= heap[1];

  v:= heap[nHeap];
  dec(nHeap);

  r:= 1;
  While r * 2 <= nHeap do
    Begin
      c:= r * 2;
      If (c < nHeap) and (d[heap[c + 1]] < d[heap[c]]) then inc(c);
      If d[v] <= d[heap[c]] then break;

      heap[r]:= heap[c];
      pos[heap[r]]:= r;
      r:= c;
    End;

  heap[r]:= v;
  pos[v]:= r;
End;

Procedure Dijkstra;
Var
  u,i,tmp: integer;
Begin
  Fillchar(free, sizeof(free), true);

  Fillchar(pos, sizeof(pos), 0);
  nHeap:= 0;

  For i:= 0 to a[1] - 1 do d[i]:= maxv;
  d[1]:= 1;

  update(1);
  Repeat
    u:= pop;
    free[u]:= false;

    For i:= 1 to maxn do
      Begin
        tmp:= (u + a[i]) mod a[1];
        If free[tmp] and (d[tmp] > d[u] + a[i]) then
          Begin
            d[tmp]:= d[u] + a[i];
            update(tmp);
          End;
      End;
  Until nHeap = 0;
End;

Procedure query;
Var
  i: integer;
Begin
  Assign(fo, output);
    Rewrite(fo);

  res:= 0;
  If a[1] = 1 then res:= h else
  For i:= 0 to a[1] - 1 do
    if d[i] <= h then
      res:= res + (h - d[i]) div a[1] + 1;

    Writeln(fo, res);
  Close(fo);
End;

Begin
  init;
  sort;
  Dijkstra;
  query;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<queue>
#define MAX   100100
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
ll a,b,c,n;
ll d[MAX];
ll res;
void swap(ll &a,ll &b) {
    ll sw;
    sw=a;a=b;b=sw;
}
void init(void) {
    scanf("%lld",&n);
    scanf("%lld",&a);
    scanf("%lld",&b);
    scanf("%lld",&c);
    if (a<=b && a<=c) swap(a,c);
    else if (b<=c && b<=a) swap(b,c);
    ll i;
    for (i=1;i<=c;i=i+1) d[i]=n+1;
}
void dijkstra(void) {
    priority_queue<ii,vector<ii>,greater<ii> > q;
    while (!q.empty()) q.pop();
    d[0]=0;
    q.push(ii(0,0));
    ll px,py;
    ii p;
    while (!q.empty()) {
        p=q.top();q.pop();
        px=p.first;py=p.second;
        if (d[(py+a)%c]>px+a) {
            d[(py+a)%c]=px+a;
            q.push(ii(px+a,(py+a)%c));
        }
        if (d[(py+b)%c]>px+b) {
            d[(py+b)%c]=px+b;
            q.push(ii(px+b,(py+b)%c));
        }
    }
}
ll f(ll x,ll mod) {
    if (x<mod) return (0);
    return ((x-mod)/c+1);
}
void process(void) {
    dijkstra();
    res=0;
    ll i;
    //for (i=0;i<c;i=i+1) printf("%lld ",d[i]); printf("\n");
    for (i=0;i<c;i=i+1)
        if (d[i]<n) res=res+f(n-1,i)-f(d[i]-1,i);
    printf("%lld ",res);
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math, sysutils;

const
    maxq = 1000000;

var
    res, h : int64;
    a, b, c : integer;
    f : array[0..100000] of int64;
    q : array[0..maxq] of integer;
    u, v, i, le, ri : integer;

procedure add(x : integer);
begin
    inc(ri);
    if ri > maxq then ri := 1;
    q[ri] := x;
end;

function del : integer;
begin
    del := q[le];
    if le = ri then
    begin
        le := 1;
        ri := 0;
    end
    else
    begin
        inc(le);
        if le > maxq then le := 1;
    end;
end;

begin
    read(h,a,b,c);
    for i:=0 to a-1 do f[i] := h + 1;
    f[0] := 0;
    add(0);
    while ri <> 0 do
    begin
        u := del;
        v := (u+b) mod a;
        if f[v] > f[u] + b then
        begin
            f[v] := f[u] + b;
            add(v);
        end;
        v := (u+c) mod a;
        if f[v] > f[u] + c then
        begin
            f[v] := f[u] + c;
            add(v);
        end;
    end;
    res := 0;
    for i:=0 to a-1 do if f[i] < h then
    begin
        res := res + ( h - 1 - f[i] ) div a + 1;
    end;
    writeln(res);
end.