Chú kiến thông minh

CHÚ KIẾN THÔNG MINH

Một bầy kiến đứng quanh một hình tròn (tức là trên đường tròn) được chia làm n ô. Mỗi ô có một số con, tổng số kiến ko vượt quá n. Sau khi nhận được tin cấp báo sắp có con mồi đi từ tâm hình tròn ra, các chú kiến tìm cách làm thịt con mỗi này. Một chú kiến nhỏ thông minh trong bầy đề xuất rằng để khả năng bắt được con mồi là cao nhất thì mỗi con nên đứng canh trên 1 ô khác nhau. Để tiết kiệm sức, cần một kế hoạch di chuyển sao cho tổng quãng đường phải di chuyển là ít nhất có thể được. Biết rằng đoạn đường giữa hai ô kề nhau bất kì có độ dài là 1 đơn vị, và để đi từ ô i đến ô j, nếu đi theo lộ trình i,a1,a2,..,an,j thì quảng đường là n+2. Chú ý chỉ được di chuyển qua các cô trên đường tròn.

Dữ liệu vào: Đọc từ file văn bản ANT.INP có cấu trúc:
+ Dòng đầu ghi số n
+ n dòng tiếp theo: mỗi dòng ghi 1 số tự nhiên thể hiện só kiến đang đứng trên ô thứ i. (các ô được liệt kê theo chiều kim đồng hồ).

Dữ liệu ra: Ghi vào file văn bản ANT.OUT gồm một dòng:
+ Ghi một số duy nhất thể hiện tổng đoạn đường phải di chuyển của cả bầy kiến.


Ví dụ:
ANT.INP
6
0
2
1
3
0
0

ANT.OUT
4

Giải thích: Liệt kê theo chiều kim đồng hồ thì số kiến trên các ô 1..6 là 0,2,1,3,0,0 . Một con kiến đi từ ô 2 sang ô 1, mất 1 đơn vị thời gian. Số kiến giờ là
1 1 1 3 0 0
Tương tự ta có
1 1 1 3 0 0 (quãng đường: 1)
1 1 1 2 0 1 (quãng đường: 3)
1 1 1 1 1 1 (quãng đường: 4)

Code:

program con_kien;
const fi='conkien.inp';
      fo='conkien.out';
var a:array[1..1000] of integer;
    i,j,n,m,gt,k,l:integer; f:text;

procedure nhap;
 begin
  assign(f,fi);
  reset(f);
  readln(f,n);
  for i:=1 to n do begin readln (f,a[i]); if a[i]>1 then inc(l); end;
  close(f);
 end;

procedure tinh;
 begin
  k:=0; gt:=0;
  while l>0 do
  begin
    inc(k);
    for i:=1 to n do
    if a[i]=0 then
      begin
      j:=i-k;
      if j<1 then j:=j+n;
      if a[j]>1 then
        begin
        a[i]:=1;
        gt:=gt+k;
        dec(a[j]);
        if a[j]=1 then dec(l);
        end
      else
        begin
        j:=i+k; if j>n then j:=j-n;
        if a[j]>1 then
          begin
          a[i]:=1;
          gt:=gt+k;
          dec(a[j]);
          if a[j]=1 then dec(l);
          end;
        end;
      end;
  end;
 end;

procedure xuat;
 begin
  assign(f,fo);
  rewrite(f);
  write(f,gt);
  close(f);
 end;

begin
 nhap;
 tinh;
 xuat;
end.