HAOI5000 - HAOI 5000

Tác giả: RR

Ngôn ngữ: Pascal

{Cho K thi sinh thi may tinh ngoi o N vi tri quanh 1 vong tron. Cac thi sinh
co the ngoi cung may (thi dong doi). Tim vi tri cua may giam thi sao cho tong
khoang cach tu may giam thi den may cac thi sinh la nho nhat. Tim tat ca cac
vi tri thoa man. Biet rang khoang cach tu may giam thi den may thi sinh duoc
tinh theo cong thuc:
  d=min(abs(u-v),N-abs(u-v))
voi u,v la may giam thi va may thi sinh}
{$R+,Q+,S+}
PROGRAM HAOI5000;
CONST
  fi='';
  fo='';
  maxn=1000000;
  maxk=100000;
  maxkq=maxn*maxk;
VAR
  n,k:longint;
  a:array[1..maxn] of longint;
  sl,sr:array[1..maxn] of longint;
  l,r:array[1..maxn] of qword;
Procedure ReadInput;
Var
  f:text;
  i,x:longint;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,n,k);
  For i:=1 to k do
  begin
    Read(f,x);
    inc(a[x]);
  end;
  Close(f);
End;
Procedure Tinh1;
Var
  i:longint;
Begin
  For i:=2 to n do sl[i]:=sl[i-1]+a[i-1];
  For i:=n-1 downto 1 do sr[i]:=sr[i+1]+a[i+1];
End;
Procedure Tinh2;
Var
  i:longint;
  k,k1:longint;
Begin
  k:=n div 2;
  k1:=k+n mod 2;
  For i:=2 to k1 do
    l[i]:=l[i-1]+sl[i];
  For i:=k1+1 to n do
    l[i]:=l[i-1]+sl[i]-sl[i-k]-sl[i-k1];
  For i:=n-1 downto k1 do
    r[i]:=r[i+1]+sr[i];
  For i:=k1-1 downto 1 do
    r[i]:=r[i+1]+sr[i]-sr[i+k1]-sr[i+k];
End;
Procedure WriteOutput;
Var
  f:text;
  i:longint;
  min:qword;
  sl:longint;
Begin
  Assign(f,fo); Rewrite(f);
  min:=maxkq;
  For i:=1 to n do
    If l[i]+r[i]<min then min:=l[i]+r[i];
  Writeln(f,min);
  sl:=0;
  For i:=1 to n do
    If l[i]+r[i]=min then inc(sl);
  Writeln(f,sl);
  For i:=1 to n do
    If l[i]+r[i]=min then Write(f,i,' ');
  Close(f);
End;
BEGIN
  ReadInput;
  Tinh1;
  Tinh2;
  WriteOutput;
END.

Download