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

[duyhung123abc]

Vài bài ôn tập cho HSG vòng 1 cấp tỉnh ngày mai.

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]

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]

Đáp án đây

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.

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

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]

Đây là đoạn code tách chuỗi số từ chuỗi ban đầu

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]

Đề 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]

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