Một số bài toán cần nắm trong tin học

[khanhan2006_2009]

Nguyên văn bởi johnceduy

Em thấy giới hạn n cao quá liệu có ai nhập nổi để test?

Khi em học thì mới nhập test bằng tay thuj,đi thi người ta cho test bằng máy,dù số bự cỡ nào cũng...vô tư.

[duyhung123abc]

Thường người ta thao tác trên file, sẽ có 1 chương trình chấm kết quả đc xuất ra từ file output. Nhưng đối với riêng bài này, vì lười viết trình chấm nên anh đã để output là duy nhất .

[johnceduy]

hehe em non mà , thank các anh nhìu

[duyhung123abc]

Cách tốt hơn để giải quyết bài này có độ phức tạp O(N), dựa vào tính chất dãy số dương.

Xét dãy con liên tiếp kết thúc tại j, gọi i là vị trí xa nhất về bên trái sao cho đảm bảo điều kiện tổng từ i đến j <=M. Giả sử đã tìm đc một cặp (i,j) nào đó. Ta nhận xét: "Với mỗi cặp (x,y), nếu (y>j) thì chắc chắn (x>=i)".

Vd ta xét vị trí j, ta tìm đc i tương ứng của nó. Vì i là vị trí xa nhất sao cho tổng [i,j]<=M nên ta chắc chắn tổng từ [i-1,j]>M. Vậy với (j+1) ta chỉ cần kiểm tra điều kiện tổng từ i đến (j+1) <=M, nếu thỏa thì tiếp tục tăng j, nếu ko thì tăng i lên đến khi thỏa.

getmax:=low(longint); {gán biến getmax bằng giá trị nhỏ nhất của kiểu longint}
i:=1;
tong:=0;
for j:=1 to n do
  begin
    tong:=tong+a[j];
    while (tong>M) do begin tong:=tong-a[i]; i:=i+1; end;
    if (j - i + 1 > getmax) then getmax:=j - i + 1;
  end;
writeln(getmax);

[duyhung123abc]

đoạn code ở trên nhìn thì thấy 2 vòng lặp lồng nhau, nhưng thực chất vòng for sẽ gán cho biến j các giá trị từ 1 đến n, vòng while gán cho i các giá trị từ 1 đến n. Mỗi giá trị 1 đến n chỉ xuất hiện 1 lần trong biến i và j, nên thuật toán có độ phức tạp O(2N) ~ O(N)

[duyhung123abc]

thêm một bài nữa, bài này là một ứng dụng của bài trên kia

(Nguồn bài: Topcoder)

Cho một dãy các khẩu súng ngắn được xếp thành một dải hàng ngang. Có tất cả M loại súng và các khẩu súng cùng loại thì được xếp liên tiếp nhau. Ví dụ M=4
1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4
Các loại súng được xếp theo thứ tự từ 1 đến M.
Ta có C[i] là số lượng súng loại i mà cửa hàng có và P[i] là mức phá hủy của loại súng i. Bạn cần trang bị N khẩu súng ngắn cho đội quân của mình và có một yêu cầu là N khẩu súng bạn chọn phải liên tiếp nhau. Hãy in ra tổng độ phá hủy lớn nhất có thể chọn được.

*input: nhập từ file guns.inp với dữ liệu được mô tả như sau:
_ Dòng đầu chứa 2 số M,N (M<=50, N<=1000000)
_ Dòng tiếp theo chứa M số là các số C[i]
_ Dòng tiếp theo chứa M số là các số P[i]

*output: xuất ra file guns.out với 1 dòng duy nhất là tổng độ phá hủy lớn nhất có thể chọn được.

Biết rằng N không vượt quá tổng số lượng súng.

VD:
*input
3 20
5 37 4
7 2 8

*output
65

*Giải thích: với bộ test trên ta sẽ có
_ 5 khẩu súng loại 1 được xếp đầu tiên (độ phá hủy mỗi khẩu là 7)
_ 37 khẩu súng loại 2 được xếp tiếp theo (độ phá hủy mỗi khẩu là 2)
_ 8 khẩu súng loại 3 được xếp cuối cùng (độ phá hủy mỗi khẩu là 8)

Cách chọn N khẩu liên tiếp tối ưu là chọn 5 khẩu loại 1 và 15 khẩu loại 2. Độ phá hủy là 5*7 + 15*2

*Lưu ý: vd test 1 1 1 2 2 3 3 3 3 ta có thể chọn 1 1 2 2 3 3 vẫn hợp lệ vì đó là các khẩu liên tiếp nhau.

[duyhung123abc]

Bài mới đây

Nguồn bài: Topcoder
Cho một thỏi chocolate có chiều dài L và chiều rộng W và được chia thành LxW ô vuông đơn vị. Mỗi lần ta có thể bẻ thỏi chocolate theo một trong 2 chiều ngang hoặc dọc. Hãy tìm số lần bẻ ít nhất để thu đc thỏi chocolate có diện tích S.

Giới hạn: 1<= L,W,S <=10^9
*Input: vào từ file chocolate.inp:
_ dòng đầu chứa số T là số bộ test
_ T dòng sau mỗi dòng tương ứng với 1 test gồm 3 số L,W,S

*Output: xuất ra file chocolate.out, với mỗi test in ra trên 1 dòng số lần bẻ ít nhất để thu đc thỏi chocolate có diện tích S. Nếu không có cách nào thực hiện được thì in ra -1.
VD:
INPUT
2
5 4 12
3 3 9
OUTPUT
1
0

[nhan_lqd]

program chocolate;
const   fi='chocolate.inp';
        fo='chocolate.out';
var     L,W,S:int64;
        kq,T,d:integer;
procedure motep;
begin
  assign(input,fi);
  assign(output,fo);
  reset(input);
  rewrite(output);
end;
(*******************************)
procedure dongtep;
begin
  close(input);
  close(output);
end;
(********************************)
procedure docf;
begin
  readln(L,W,S);
end;
(*********************************)
procedure xuly;
var i,j:int64;
    kt:boolean;
begin
  kq:=-1;
  if S=L*W then kq:=0 else
  if ((S div L*L=S) and (S div L<=W)) or ((S div W*W=S) and (S div W<=L)) then
  kq:=1 else
  begin
    i:=S div 2;
    kt:=true;
    while kt do
    begin
      j:=s div i;
      if (i*j=S) and (((i<=W) and (j<=L)) or ((i<=L) and (j<=W))) then
      kq:=2;
      if (i<2) or (kq<>-1) then kt:=false else
      dec(i);
    end;
  end;
end;
(***********************************)
procedure inkq;
begin
  writeln(kq);
end;
(***********************************)
begin
  motep;
  readln(T);
  for d:=1 to T do
  begin
    docf;
    xuly;
    inkq;
  end;
  dongtep;
end.

[duyhung123abc]

bài em bị quá thời gian. Nếu S = 10^9 thì phải duyệt đến 5.10^8 => quá thời gian

[duyhung123abc]

Đây là đáp án của bài chocolate

_ Giả sử ta muốn cắt hình chữ nhật kích thước LxW thành hình chữ nhật kích thước AxB. Nếu hình chữ nhật AB có thể nằm trong hình chữ nhật LW thì ta chỉ cần tối đa 2 lần cắt. Nếu hcn AB bằng hcn LW thì không cần lần cắt nào, nếu cạnh nhỏ của AB bằng cạnh nhỏ của LW hoặc cạnh lớn của LW bằng cạnh lớn của AB thì ta chỉ cần 1 lần cắt.

_ Vậy ta chỉ kiểm tra lần lượt các hình chữ nhật có diện tích AxB = S, tương đương với việc phân tích S thành tích của 2 số A và B. Cách làm bình thường là ta duyệt A từ 1 đến (S/2), nếu S chia hết cho A thì ta gán B:=S div A và kiểm tra như trên. Nhưng ở đây S có thể lên tới 10^9 nên ta phải cải tiến chỉ duyệt A từ 1 đến sqrt(S).