Dạo này thấy box Pascal ỉu xìu quá!

[truongngocdai]

- Người chiến thắng đợt 1: F12 (xin mời F12 liên hệ với mình để nhận giải )
- Đề bài dành cho đợt 2:

Cho dãy n số nguyên dương a1, a2, ..an và một số k bất kì (k nhỏ hơn hoặc = tổng các ai). Tìm cách biểu diễn k thành tổng của L số ai (mỗi ai chỉ dùng một lần), nếu không biểu diễn được thì cố gắng với sai số càng ít càng tốt.

Yêu cầu dành cho các bạn dùng Free Pascal
N <= 100 000 ; ai <= 2 000 000 000

Yêu cầu dành cho các bạn sử dụng Turbo Pascal
N <= 5 000 ; ai <= 32 000

Input: DAY.INP
- Dòng đầu ghi số N
- Dòng thứ 2 ghi số K
- N dòng sau dòng thứ i+2 ghi các số ai

OUTPUT: DAY.OUT
- Dòng đầu ghi số chênh lệch (trị tuyệt đối)
- Dòng thứ hai ghi số l cần chọn.
- L dòng sau dòng thứ l + 2 ghi số chọn thứ l

VD1
day.inp
3
4
1
2
3

day.out
0
2
1
3

VD2
day.inp
3
10
4
5
2

day.out
1
2
4
5

- Khuyến khích các bạn sử dụng Turbo Pascal nhưng tuy nhiên dùng Free Pascal thì sẽ được ưu tiên hơn
- Giới hạn thời gian: 5 phút


Thời hạn cuối cùng để nộp bài "dự thi": 1 - 3 - 2007

[trinick_13]

Thê thì quá tốt rùi. Làm bằng FP sướng hơn đó anh em.

[trinick_13]

Pác Trai Ngọc Đượng . Em vừa gửi cho pác bài giải đấy, xem đi rùi có chi nói em. Em test nhiều rùi đó

[F12]

Bài khó quá. NP rồi.

Chết thật, ngoài chạy nhanh hơn và bộ nhớ rộng rãi, FP còn gì hơn TP nhỉ ?

[truongngocdai]

Bài khó quá. NP rồi.

Chết thật, ngoài chạy nhanh hơn và bộ nhớ rộng rãi, FP còn gì hơn TP nhỉ ?

- Nói chung FP hơn TP 1 điểm nữa về kiểu dữ liệu
- À, mời anh F12 liên hệ với em để nhận giải thưởng đợt 1

[trinick_13]

Anh F12 ơi ! Nick anh là zì thía ? :-$:-$:-$

[trinick_13]

Pác F12 ơi. Nếu pác pót code lên thì dù được giải cũng không có kem đâu! Pác Trai Ngọc Đượng nói với em thế đó. Nên pác hãy từ bỏ ý định pót code đi nhé. Để em pót lên có chi được giải 1 em chia cho pác 1/2 nhé! Hi HI

[truongngocdai]

Pác F12 ơi. Nếu pác pót code lên thì dù được giải cũng không có kem đâu! Pác Trai Ngọc Đượng nói với em thế đó. Nên pác hãy từ bỏ ý định pót code đi nhé. Để em pót lên có chi được giải 1 em chia cho pác 1/2 nhé! Hi HI

Bạn không nên post bài và chat ở đây

[truongngocdai]

Đã có người giải được bài: F12 (sử dụng Free Pascal)

{$M 10000000 0}
program daya;

uses Dos;

const
  fi = 'day.inp';
  fo = 'day.out';
  maxn = 100001;
  Limit = 10; { han che thoi gian Limit giay }

var
  f       : text;
  n       : longint;
  k       : int64;
  a       : array[1..maxn] of longint;
  c,w     : array[1..maxn] of boolean;
  sum     : array[1..maxn] of int64;
  result  : int64;
  count   : int64;

  gio,phut,giay,ptgiay : word;
  time0,time : longint;


procedure khoitao;
begin
  fillchar(a,sizeof(a),0);
  fillchar(w,sizeof(w),0);
  gettime(gio,phut,giay,ptgiay);
  time0 := gio*3600+phut*60+giay;
end;

function time_out : boolean;
begin
  gettime(gio,phut,giay,ptgiay);
  time := gio*3600+phut*60+giay;
  time_out := (time-time0) >Limit;
end;

procedure doc;
var i:longint;
begin
  assign(f,fi);
  reset(f);
  read(f,n,k);
  for i := 1 to n do read(f,a[i]);
  close(f);
end;

var tg,mid:longint;
procedure quicksort(l,r:longint);
var i,j:longint;
begin
  i:=l;
  j:=r;
  mid:=a[l+random(r-l+1)];
  while i<=j do
    begin
      while a[i]>mid do inc(i);
      while mid>a[j] do dec(j);
      if i<=j then
        begin
          tg:=a[i];a[i]:=a[j];a[j]:=tg;
          inc(i);
          dec(j);
        end;
    end;
  if l<j then quicksort(l,j);
  if i<r then quicksort(i,r);
end;

procedure duyet(i:longint);
begin
  if time_out then exit;
  if result=0 then exit;
  if abs(count-k)<result then
    begin
      result:=abs(count-k);
      w:=c;
    end;
  if count>=k+result then exit;
  if count+sum[i+1]<k-result then exit;
  if i<=n then
    begin
      c[i]:=true;
      count:=count+a[i];
      duyet(i+1);
      count:=count-a[i];
      { }
      c[i]:=false;
      duyet(i+1);
    end;
end;

procedure lam;
var i:longint;
begin
  result:=k;
  quicksort(1,n);
  sum[n+1]:=0;
  for i := n downto 1 do sum[i]:=sum[i+1]+a[i];
  duyet(1);
end;

procedure viet;
var i,j:longint;
begin
  assign(f,fo);
  rewrite(f);
  writeln(f,result);
  j:=0;
  for i := 1 to n do
    if w[i] then inc(j);
  writeln(f,j);
  for i := 1 to n do
    if w[i] then writeln(f,a[i]);
  close(f);
end;

begin
  khoitao;
  doc;
  lam;
  viet;
  writeln((time-time0) / 60);
  readln;
end.

[pineflower]

bạn nào test thấy code của mình đã chuẩn thì có thể post lên topics luôn, (ko post lên code chưa hoàn chỉnh hoặc thuật toán). Hiện tại mình đã nhận được bài giải của: F12

Đây là code của F12

program robot;

const
  fi = 'robot.inp';
  fo = 'robot.out';
  maxn = 20;
  gd : array[1..4] of integer = (-1,0,1,0);
  gc : array[1..4] of integer = (0,1,0,-1);

var
  f,g                 : text;
  m,n,h               : integer;
  a                   : array[1..maxn,1..maxn] of byte;
  c                   : array[1..maxn,1..maxn,0..20] of integer;
  queue               : array[1..9000,1..3] of byte;
  first,last,result   : integer;

procedure khoitao;
begin
  fillchar(a,sizeof(a),0);
  fillchar(c,sizeof(c),0);
  fillchar(queue,sizeof(queue),0);
  result:=0;
end;

procedure doc;
var i,j:integer;
begin
  readln(f,m,n);
  readln(f,h);
  for i := 1 to m do
    begin
      for j := 1 to n do read(f,a[i,j]);
      readln(f);
    end;
end;

procedure lam;
var i,j,p,q,ii,jj,k:integer;
begin
  queue[1,1]:=1;
  queue[1,2]:=1;
  queue[1,3]:=0;
  first:=1;
  last:=1;
  c[1,1,0]:=1;
  while first<=last do
    begin
      i:=queue[first,1];
      j:=queue[first,2];
      p:=queue[first,3];
      inc(first);
      for k := 1 to 4 do
        begin
          ii:=i+gd[k];
          jj:=j+gc[k];
          if (ii>0) and (jj>0) and (ii<=m) and (jj<=n) then
            begin
              if a[ii,jj]=1 then q:=p+1 else q:=0;
              if (q<=h) and (c[ii,jj,q]=0) then
                begin
                  c[ii,jj,q]:=c[i,j,p]+1;
                  inc(last);
                  queue[last,1]:=ii;
                  queue[last,2]:=jj;
                  queue[last,3]:=q;
                end;
            end;
        end;
    end;
  result:=maxint;
  for i := 0 to h do
    if (c[m,n,i]>0) and (result>c[m,n,i]) then result:=c[m,n,i];
  if result=maxint then result:=-1 else dec(result);
end;

procedure viet;
begin
  writeln(g,result);
end;

procedure mofile;
begin
  assign(f,fi); reset(f);
  assign(g,fo); rewrite(g);
end;

procedure dongfile;
begin
  close(f);
  close(g);
end;

var test,testcase:integer;
begin
  mofile;
  readln(f,test);
  for testcase:=1 to test do
    begin
      khoitao;
      doc;
      lam;
      viet;
    end;
  dongfile;
end.

Mình có đôi chút nhận xét về bài của F12:
- Bạn lưu trữ dữ liệu vào 1 mảng 3 chiều ? Ko nên vậy! Chỉ cần đọc vào từng ma trận rồi làm luôn rồi tiếp tục ma trận sau ...
- Có thể bạn nên sử dụng các kiểu dữ liệu "tự chế" thì đỡ tốn hơn


Mong các bạn đóng góp ý kiến cho bài giải của F12

P/S: Bài giải này sẽ là tối ưu nhất nếu như trong 1 tuần tới ko có bài giải nào tốt hơn

Chà lâu lắm không quay lại box này, xin ủng hộ ý kiến của bác, nhưng em không hiểu những điều bác nói ở trên có nghĩa là gì. Bài của F12 hoàn toàn đúng và cái chỗ dùng mảng 3 chiều chẳng có gì sai cả. Nếu ko dùng mảng 3 chiều thì vẫn có cách để cài được nhưng nó sẽ phức tạp hơn rất nhiều. Trở lại bài trên, nếu không dùng mảng 3 chiều thì sẽ ko thể đúng được. Vả lại, kiểu dữ liệu "tự chế" là gì vậy? Em chưa nghe thấy bao giờ. Không biết em nói thế này có đúng không nhưng cần phải có một chuẩn mực trong lập trình. Có thể anh và mọi người lập trình rất giỏi nhưng khi làm việc trong một tập thể thì những kiểu dữ liệu tự chế là rất không nên. hoặc có thể sự dụng một số mẹo mực nào đó để tăng tốc độ chương trình. Nhưng trong trường hợp này có cần phải tối ưu quá đến như vậy không? Việc làm như vậy không những ảnh hưởng đến phong cách lập trình và tương lai của chúng ta sau này. Chúng ta hãy tự hỏi sao các nhân viên của Microsoft lại làm việc với nhau ăn ý như vậy, thậm chí là chưa từng gặp mặt nhau bao giờ, vậy mà các phiên bản của Windows ra lò liên tục mặc dù không tránh khỏi sai sót. Em rất đồng ý với bác đây là một cuộc thi, thì phải có người hơn kẻ kém, nhưng theo em nghĩ rằng nếu một cải tiến nào đấy mà làm giảm thực sự tốc độ chương trình (Thấy rõ cách biệt qua độ phức tạp của chương trình) thì cái đó mới nên tuyên dương khuyến khích, chứ đào sâu để tìm nhưng lỗi nhỏ nhặt, cải tiến để không tốt hơn là mấy thì em nghĩ rằng không nên. Mong nhận được góp ý của bác và mọi người