Kiến thông minh

Bảng B tin học trẻ toàn quốc 2011 - Bài 2/2
Kiến chúa tổ chức cuộc thi 'kiến thông minh' trên một đoạn thằng nằm ngang n đơn vị, tổ kiến nằm ở một đầu mút của đoạn thẳng đó. Khi mỗi chú kiến thợ vào thi, Kiến chúa rải n miếng đường đánh số từ 1 đến n. Miếng đường thứ i có trọng lượng Wi được đặt trên đoạn thẳng ở vị trí cách tổ kiến đúng i đơn vị độ dài (i=1,2,...,n).
Mỗi chú kiến thợ cần thực hiện đúng 3 lần kiếm mồi trong bài thi của mình. Mỗi lượt, chú kiến thợ xuất phát từ tổ đến vị trí miếng đường và tha về tổ của mình, lượt chơi tiếp theo tiến hành tương tự, tất nhiên tất cả những miếng đường đã tha về tổ thì không còn ở vị trí cũ nữa
Một bài thi của một chú kiến là hợp lệ nếu tổng quãng đường di chuyển của chú kiến trong cả ba lượt kiếm mồi không vượt quá T. điểm của bài thi là tổng trong lượng của ba miếng đường mà chú kiến thợ kiếm được.
Em được cho trước số nguyên dương n, số nguyên dương T, hai số nguyên dương a, m để xác định dãy W1, W2, ..., Wn theo công thức Wi=a^i mod m +1
Yêu cầu: Xác định điểm tối đa mà chú kiến thợ có thể kiếm được trong bài thi của kiến chúa.
Ví dụ với n=5, T=15, a=4, m=9. Dãy W1..5 = (5,8,2,5,8).
Phương án kiếm được nhiều điểm nhất (18 điểm) cho chú kiến thợ là tha ba miếng dường số 1, 2 và 4 về tổ. Tổng quãng đường di chuyển là 14.
Em cần tạo 10 file kết quả có dạng ANT?.TXT, trong mỗi file, ghi một số nguyên duy nhất là kết quả tìm được ứng với mỗi bộ giá trị (n, T, a, m) cho dưới đây:
File kết quả       n                    T                   a                     m
ANT0.TXT      3                     12                 2                     5       
ANT1.TXT      5                     15                 4                     9       
ANT2.TXT      10                   25                 9                     20         
ANT3.TXT      100                 100               11                   135             
ANT4.TXT      1 000              3 000            2                     9 999                   
ANT5.TXT      2 222              1 234            5                     99 991                   
ANT6.TXT      3 333              5 678            99                   999 983                     
ANT7.TXT      9 999              9 999            9 999              99 999                         
ANT8.TXT      999 999          5 555 555     789                 999 999 929     
ANT9.TXT      1 000 000       2 000 000     3 000 000       999 999 937                                               

                                                           Lời giải tham khảo

var w:array[1..10000] of longint;
    d:array[1..10000] of integer;
    i,j:integer;
    k,max,kl,qd,a,T,m,n:longint;
function tl(i:integer):longint;
begin
 k:=1;
 for j:=1 to i do k:=(k*a) mod m;
 tl:=k+1;
end;
procedure ss;
begin
 if kl>max then
  begin
    max:=kl;
    for i:=1 to k do write(d[i],' ');
    for i:=1 to k do d[i]:=0;
    writeln;
  end;
end;
procedure try(i:integer);
begin
   for j:=i to n do
     if qd+j*2<T then
       begin
        kl:=kl+w[j];
        qd:=qd+j*2;
        writeln(qd,' ',kl);
        inc(k);
        d[k]:=j;
        try(j+1);
        kl:=kl-w[j];
        qd:=qd-j*2;
        writeln(qd,' ', kl);
        dec(k);
       end
     else ss;
end;
begin
  write('nhap n,T,a,m:'); readln(n,T,a,m);
  for i:=1 to n do w[i]:=tl(i);
  k:=0;
  try(1);
  write(max);
  readln;
end.