Cựu Học Sinh Lê Quý Đôn - Long An

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)

duyhung123abc 28-07-2009 10:30 AM
Một số bài toán cần nắm trong tin học
 
Topic này đc mở ra cho tất cả những ai thích lập trình, không phân biệt già trẻ. Em nhỏ thì học hỏi, mấy anh lớn thì truyền kinh nghiệm nhá :x

duyhung123abc 28-07-2009 10:32 AM
Ðề: Một số bài toán cần nắm trong tin học
 
Một bài toán về dãy số

Trích:
Cho một dãy gồm n số nguyên dương
a[1] a[2] a[3] … a[n]
với ai>0

Một dãy con liên tiếp của dãy trên là:
a[i] a[i+1] a[i+2] … a[j]
với (1<=i<=j<=N)

Hãy in ra độ dài dãy con liên tiếp dài nhất của dãy số trên có tổng các phần tử của dãy con <=M.

Giới hạn: N<=100000, M<=10^9

*Input: nhập từ file seq.inp với:
_ dòng đầu tiên chứa 2 số N, M
_ N dòng tiếp theo, dòng thứ i chứa duy nhất 1 số nguyên là giá trị ptử thứ i.

*Output: xuất ra file seq.out:
_ Gồm 1 dòng duy nhất chứa số phần tử của dãy con liên tiếp dài nhất

VD:
*input:
7 6
1 2 3 4 3 2 1
*output:
3

duyhung123abc 30-07-2009 05:54 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Bài toán này có 1 cách làm đơn giản là dùng 2 biến chạy i,j với j>=i. Với mỗi cặp i,j ta kiểm tra xem đoạn con liên tiếp từ phần tử thứ i đến phần tử thứ j có thỏa điều kiện <=M hay ko, nếu thỏa thì tính độ dài và cập nhật để thu đc độ dài đoạn con dài nhất.
Code:
kq:=0; {biến kq lưu độ dài lớn nhất tìm được, ban đầu gán kq=0}
for i:=1 to n-1 do
  for j:=i to n do
    begin
      tong:=0;
      for k:=i to j do tong:=tong+a[k]; {tính tổng các số từ i đến j}
      if (tong<=m) and (j+1-i>kq) then kq=j+1-i; (*)
    end;
writeln(kq);
trong đó phần được đánh dấu (*) diễn tả: "kiểm tra 2 điều kiện: tổng của dãy số phải <=m và chiều dài đoạn từ i đến j phải lớn hơn chiều dài lớn nhất tìm được trước đó"

Nhưng với cách làm này rõ ràng không quan trọng a[i] âm hay dương, nhưng đề bài lại cho dãy số dương, nên ta có một cách làm khác có thể tăng tốc hơn rất nhiều. Cách này sẽ đc post sau :D

johnceduy 30-07-2009 09:24 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Đây là code của em, nếu thíu xót hay tối tăm chỗ nào nhờ anh góp ý :teeth_smile:
Code:
Begin
    Write('Nhap vao n:');readln(n);
    For i:=1 to n do begin
    Write ('Nhap vao a[',i,']:');readln(a[i]);
    end;
    Write('Nhap vao m:');readln(m);
For i:=1 to n-1 do begin
 T:=a[i]+a[i+1];
 If T<=m then begin
 dem:=2;
 For j:=1 to n-1-i do begin
 If a[i+1+j]>0 then begin
 T:=T+a[i+1+j];
 If T<=m then dem:=dem+1
else break;
 end;
 end;
 end
else break;
 b[i]:=dem;
end;
max:=0;
For i:=1 to n do
 If b[i]>max then max:=b[i];
write('Dai nhat:',max);
readln;
end.

khanhan2006_2009 30-07-2009 09:37 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Bài này đã test thử trong pascal chưa.
A nghĩ là ko đúng vì biến T chỉ toàn cộng vào....nói chung là nhìn ko có lý lắm.

johnceduy 30-07-2009 09:41 PM
Ðề: Một số bài toán cần nắm trong tin học
 
dạ rồi ạ, khi T tăng vọt quá m thì nó dừng lại ngay, không lố đâu :D

duyhung123abc 30-07-2009 10:09 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Bài của em sẽ sai trong trường hợp khi cộng đến số thứ n mà tổng vẫn <=M, thì j sẽ tăng lên tiếp. Do pascal mặc định các số ban đầu của mảng =0, nên biến j sẽ chạy đến giá trị (j=n) và độ dài max có thể lên đến (n+2) => vô lý :D

Cám ơn sự hợp tác của pác An :x

Tuy nhiên cách này chỉ giải đc với n<=1000. Có ai nghĩ ra cách giải quyết với n<=100 000 chưa

duyhung123abc 31-07-2009 08:47 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Trích:
Nguyên văn bởi duyhung123abc (Post 59128)
Bài toán này có 1 cách làm đơn giản là dùng 2 biến chạy i,j với j>=i. Với mỗi cặp i,j ta kiểm tra xem đoạn con liên tiếp từ phần tử thứ i đến phần tử thứ j có thỏa điều kiện <=M hay ko, nếu thỏa thì tính độ dài và cập nhật để thu đc độ dài đoạn con dài nhất.
Code:
kq:=0; {biến kq lưu độ dài lớn nhất tìm được, ban đầu gán kq=0}
for i:=1 to n-1 do
  for j:=i to n do
    begin
      tong:=0;
      for k:=i to j do tong:=tong+a[k]; {tính tổng các số từ i đến j}
      if (tong<=m) and (j+1-i>kq) then kq=j+1-i; (*)
    end;
writeln(kq);
trong đó phần được đánh dấu (*) diễn tả: "kiểm tra 2 điều kiện: tổng của dãy số phải <=m và chiều dài đoạn từ i đến j phải lớn hơn chiều dài lớn nhất tìm được trước đó"

Nhưng với cách làm này rõ ràng không quan trọng a[i] âm hay dương, nhưng đề bài lại cho dãy số dương, nên ta có một cách làm khác có thể tăng tốc hơn rất nhiều. Cách này sẽ đc post sau :D
Với cùng cách tiếp cận trên, có thể giảm xuống còn 2 vòng lặp lồng nhau chứ không cần đến 3 vòng lặp. Nhận xét là ta xét cặp (i,j-1) trước và ngay sau đó xét tới cặp (i,j), nên ta có thể tính tổng cặp (i,j) dựa và tổng cặp (i,j-1). Gọi x là tổng của (i,j-1) thì tổng của (i,j) là (x + a[j]). Ta chuyển độ phức tạp từ O(N^3) xuống còn O(N^2)

johnceduy 31-07-2009 10:05 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Em thấy giới hạn n cao quá liệu có ai nhập nổi để test? :teeth_smile:

myhanh 01-08-2009 10:08 AM
Ðề: 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:
Người ta test bằng máy em à!

khanhan2006_2009 01-08-2009 10:08 AM
Ðề: 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ư.

duyhung123abc 01-08-2009 09:55 PM
Ðề: 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.

johnceduy 01-08-2009 10:09 PM
Ðề: 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

duyhung123abc 01-08-2009 10:26 PM
Ðề: 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);

duyhung123abc 01-08-2009 10:30 PM
Ðề: 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)

duyhung123abc 01-08-2009 10:46 PM
Ðề: 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.

duyhung123abc 12-08-2009 06:35 PM
Ðề: 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

nhan_lqd 16-08-2009 01:42 PM
Ðề: 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.

duyhung123abc 16-08-2009 02:23 PM
Ðề: 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

duyhung123abc 16-08-2009 06:48 PM
Ðề: 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).

duyhung123abc 14-10-2009 08:30 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Vài bài ôn tập cho HSG vòng 1 cấp tỉnh ngày mai.

Trích:
Bài 1:
Cho một chuỗi S chứa các chữ cái thường 'a'..'z' và một khoảng trắng. Mỗi thao tác ta chỉ có thể chuyển một chữ cái nào đó vào vị trí của khoảng trắng, in ra các thao tác để chuyển chuỗi ban đầu thành chuỗi có các kí tự tăng dần từ 'a'..'z' và khoảng trắng. VD: chuỗi ban đầu "aaczbc " thì chuyển thành "aabccz "

Bài 2:
Cho một dãy số gồm N phần tử, các phần tử có thể âm hoặc dương. Tìm dãy con liên tiếp có tổng max. In ra tổng max đó.

Bài 3:
Cho một chuỗi gồm chữ cái latinh thường và các số nằm xen trong chuỗi. Hãy sắp xếp lại các số trong chuỗi. VD: "abc20edf007as58d1" thì "abc1edf7as20d58"

johnceduy 15-10-2009 08:00 AM
Ðề: Một số bài toán cần nắm trong tin học
 
Bài 1) lấy bài của anh đưa em rồi dùng hàm val chuyển chuỗi thành số, sau khi sắp xếp xong thì biến số về chuỗi lại đc hok?

duyhung123abc 15-10-2009 08:39 AM
Ðề: Một số bài toán cần nắm trong tin học
 
Đáp án đây
Trích:
bài 1:
dùng phương pháp đếm, ta sẽ xác định đc trong chuỗi sau cùng tại vị trí nào sẽ có kí tự gì, sau đó, giả sử khoảng trắng đang đứng ở vị trí x, ta tìm trong chuỗi 1 kí tự lẽ ra phải ở vị trí x nhưng đang đứng sai chỗ (nhưng phải tránh kí tự nằm cuối chuỗi nếu tránh đc), ta đổi chỗ kí tự đó và khoảng trắng, cứ tiếp tục như thế. Nếu trường hợp nào đó khoảng trắng nằm cuối chuỗi nhưng chuỗi vẫn chưa đúng thì ta tìm 1 kí tự sai chỗ đổi chỗ nó với khoảng trắng.
Trích:
Bài 2:
Gọi S[i] là tổng các số trong đoạn 1..i. Ta có thể tính S[i] = S[i-1] + A[i];
Xét những dãy con kết thúc tại i, ta chỉ cần tìm số j sao cho (j<i) và (s[j] nhỏ nhất), khi đó (s[i] - s[j]) chính là tổng đoạn từ (j+1) đến i. Vậy ta lặp 1 vòng for chạy từ đầu đến cuối mảng, biến s là tổng từ 1 đến i, getmin là tổng nhỏ nhất, best là kết quả tối ưu.

s:=0; best:=a[1]; getmin:=0;
for i:=1 to n do
begin
inc(s,a[i]);
if (s-getmin>best) then best:=s - getmin;
if (s<getmin) getmin:=s;
end;
writeln(best);
Trích:
Bài 3:
Ta lần lượt tách các chuỗi số ra, xóa nó khỏi chuỗi ban đầu và để lại vị trí đó 1 dấu '?', sau khi sắp xếp xong thì chèn số theo thứ tự các vị trí có '?'

duyhung123abc 15-10-2009 08:56 AM
Ðề: Một số bài toán cần nắm trong tin học
 
Đây là đoạn code tách chuỗi số từ chuỗi ban đầu
Code:
procedure tachso;
var
  i,j:longint;
begin
  n:=0;
  i:=1;
  while i<=length(s) do
    begin
      j:=i;
      if (s[i]>='0') and (s[i]<='9') then
        begin
          inc(n);
          so[n]:='';
        end;
      while (s[j]>='0') and (s[j]<='9') and (j<=length(s)) do
        begin
          inc(j);
          so[n]:=so[n]+s[j];
          s[j]:='?';
        end;
      while (so[n][1]=0) and (length(so[n])>1) do delete(s,1,1);
      i:=j;
    end;

  while pos(s,'??')>0 do delete(s,pos(s,'??'),1);
end;

johnceduy 16-10-2009 02:27 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Đề về tới đây:
1) (7d) Một số nguyên dương n được gọi là số song tố khi n vừa là số nguyên tố và tổng các chữ số của n cũng là số nguyên tố (VD: 29 là số song tố thì 29 là số nguyên tố, tổng 2+9=11 là số nguyên tố). Viết chương trình nhập vào một chuỗi gồm: ký tự, số và khoảng trắng.
a)Đếm xem trong chuỗi có bai nhiu số nguyên tố.
b) Tính tổng các số song tố trong chuỗi.
3) (6d) Một máy rút tiền ATM có chứa các tờ giấy bạc mệnh giá 100,200,500,1000,2000,5000. Viết chương trình nhập vào số tiền N là bội số của 100 để máy sẽ cho ra số tờ giấy bạc là ít nhất.
VD: 37600 máy sẽ cho ra 7 tờ 5000+ 1tờ 500+ 1 tờ 100.

nhan_lqd 16-10-2009 08:08 PM
Ðề: Một số bài toán cần nắm trong tin học
 
Bổ sung thêm bài 2 Cấp tỉnh vòng 1 nè
Cho một mảng kích thước m*n chứa các số nguyên.Một ngưới xuất phát từ cột 1 đi dến cột n(bắt đầu từ ô nào của cột 1 cũng được).Quy tắc: từ ô A[i,j] chỉ có thể đi đến một trong các ô A[i,j+1], A[i+1,j+1], A[i-1,j+1].Nếu xuất phát từ ô ở dòng i=1 thì chỉ đuợc di chuyển sang ô A[i,j+1] hoặc ô A[i+1,j+1], nếu xuất phát từ ô ở dòng i=m thi chỉ được sang các ô A[i-1,j+1] hoặc ô A[i,j+1].Hãy tìm vị trí xuất phát và đường đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất.
Dữ liệu vào từ tệp bai2.inp:
dòng đầu ghi 2 so m,n lần lượt là số dòng và số cột.
các dòng tiếp theo ghi các số trên đường đi.
Dữ liệu ra ghi trong tep bai2.out:
n dòng đầu ghi tọa độ đường đi từ cột 1 đến cột n
dòng cuối ghi tổng lớn nhất tìm được.

VD:
inp
4 5
1 2 3 4 9
6 3 2 7 4
2 5 7 5 3
4 2 3 4 7
out
2 1
3 2
3 3
2 4
1 5
34


Múi giờ GMT +7. Hiện tại là 04:12 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.
Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này