Cựu Học Sinh Lê Quý Đôn - Long An - Một số bài toán cần nắm trong tin học

Cựu Học Sinh Lê Quý Đôn - Long An (http://www.lqdlongan.com/forum/index.php)

- Tin học phổ thông (http://www.lqdlongan.com/forum/forumdisplay.php?f=117)

- - Một số bài toán cần nắm trong tin học (http://www.lqdlongan.com/forum/showthread.php?t=7904)

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

Trích:

Nguyên văn bởi johnceduy (Post 59174)

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

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ư.

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

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 :D.

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

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

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

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.

Code:

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);

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

đ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)

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

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 :wink_smile:

Trích:

(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.

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

Bài mới đây

Trích:

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

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

Code:

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.

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

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

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

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

Trích:

_ 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).