Go Back   Cựu Học Sinh Lê Quý Đôn - Long An > :: Góc Học Tập :: > Tin học > Tin học phổ thông

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

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

this thread has 25 replies and has been viewed 15294 times

Gởi Ðề Tài Mới Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 01-08-2009, 11:08 AM   #11
Hồ sơ
khanhan2006_2009
Senior Member
 
khanhan2006_2009's Avatar
 
Tham gia ngày: Sep 2007
Cư ngụ: Nhà
Số bài viết: 827
Tiền: 25
Thanks: 135
Thanked 392 Times in 190 Posts
khanhan2006_2009 is on a distinguished road
Default Ðề: Một số bài toán cần nắm trong tin học

Trích:
Nguyên văn bởi johnceduy View Post
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ư.
__________________
"hcmiu.edu.vn"
khanhan2006_2009 is offline   Trả Lời Với Trích Dẫn
Old 01-08-2009, 10:55 PM   #12
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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 .
__________________
Quyết tâm thành pro
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 01-08-2009, 11:09 PM   #13
Hồ sơ
johnceduy
Senior Member
 
johnceduy's Avatar
 
Tham gia ngày: Dec 2008
Cư ngụ: Lê Quý Đôn
Số bài viết: 115
Tiền: 25
Thanks: 54
Thanked 83 Times in 18 Posts
johnceduy is on a distinguished road
Default Ðề: 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
__________________
Nhớ, nhớ, nhớ quá đi!

johnceduy is offline   Trả Lời Với Trích Dẫn
Old 01-08-2009, 11:26 PM   #14
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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);
__________________
Quyết tâm thành pro

thay đổi nội dung bởi: duyhung123abc, 01-08-2009 lúc 11:28 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 01-08-2009, 11:30 PM   #15
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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)
__________________
Quyết tâm thành pro
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 01-08-2009, 11:46 PM   #16
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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

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.
__________________
Quyết tâm thành pro
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 12-08-2009, 07:35 PM   #17
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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
__________________
Quyết tâm thành pro

thay đổi nội dung bởi: duyhung123abc, 16-08-2009 lúc 02:34 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 16-08-2009, 02:42 PM   #18
Hồ sơ
nhan_lqd
Junior Member
 
nhan_lqd's Avatar
 
Tham gia ngày: Aug 2009
Số bài viết: 6
Tiền: 25
Thanks: 0
Thanked 10 Times in 2 Posts
nhan_lqd is on a distinguished road
Default Ðề: 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.
nhan_lqd is offline   Trả Lời Với Trích Dẫn
Old 16-08-2009, 03:23 PM   #19
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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
__________________
Quyết tâm thành pro
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 16-08-2009, 07:48 PM   #20
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: 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).
__________________
Quyết tâm thành pro
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Trả lời


Ðiều Chỉnh
Xếp Bài

Quyền Sử Dụng Ở Diễn Ðàn
Bạn không được quyền gởi bài
Bạn không được quyền gởi trả lời
Bạn không được quyền gởi kèm file
Bạn không được quyền sửa bài

vB code đang Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt
Chuyển đến

Chủ đề tương tự
Ðề tài Người Gởi Chuyên mục Trả lời Bài mới gởi
Muốn con thông minh, cha mẹ phải sáng tạo trong trò chơi nhk Chuyện trẻ thơ 0 16-04-2009 12:44 PM
Rối loạn giấc ngủ peanux Chia sẻ kinh nghiệm 0 11-03-2008 08:45 AM
Chúng Ta trong Thế giới phẳng Gem ..:: Thảo luận nghiêm túc ::.. 2 09-09-2007 04:44 PM
Ufo VÀ SỰ SỐng NgoÀi TrÁi ĐẤt LeGiang Thiên văn học 0 25-05-2007 11:13 AM


Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Múi giờ GMT +7. Hiện tại là 07:16 PM.

Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này

Tự động[F9]TELEX VNI VIQR VIQR* TắtKiểm chính tảDấu cũ
phan mem quan ly ban hang | thuê vps