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.