MELE2 - ELEVATOR II

Tác giả: ll931110

Ngôn ngữ: Pascal

{$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.

Download