# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  tài liệu để on thi HSG pascal

## accxaydung

cháo các bạn
mình là giáo viên dạy môn tin học còn rất trẻ( vừa ra trường được 2 năm) nhưng có trách nhiẹm ôn thi đội tuyển HSG tin học cấp tình. mình rất lo và lung túng vì tin học là môn mới,nên mình rất mong các anh, chị,em và tất cả các bạnp chỉ giúp cho mình một số kinh nghiệm và tài liệu để ôn thi đạt kết quả cao. mình cảm ơn nhiều
sau đây mình xin hỏi diễn đàn chỉ giúp cho mình lời giải để giải một số đề sau:
có gì mình sẽ vào diễn đàn lấy hoặc mình sẽ cảm ơn rất nhiều nếu các bạn post vào mail:[email protected]
rất chân thành cảm ơn:
*đề bài:*
*Bài 1:** Xâu đối xứng*
Xâu đối xứng là xâu đọc giống nhau nếu ta bắt đầu đọc từ trái qua phải hoặc từ phải qua trái. Ví dụ, xâu RADAR là xâu đối xứng, xâu TOMATO không phải là xâu đối xứng.
*Yêu cầu:* Cho một xâu S gồm không quá 200 kí tự. Cho biết S có phải là xâu đối xứng hay không? Nếu không, cho biết số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
*Dữ liệu:* Vào từ file văn bản BAI3.INP, gồm duy nhất 1 dòng ghi xâu S.
*Kết quả:* Ghi ra file văn bản BAI3.OUT, duy nhất số k là số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Nếu xâu S đã cho là đối xứng thì ghi k = 0.
*Bài 2:** Biểu thức Zero*
Cuội viết liên tiếp các số tự nhiên từ 1 đến N thành dãy: 1 2 3 ... N. Cuội đố Bờm điền các dấu phép toán + hoặc - vào giữa 2 số tự nhiên liên tiếp sao cho biểu thức thu được có kết quả bằng 0.
*Yêu cầu:* Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán thích hợp.
*Dữ liệu:* Vào từ file văn bản BAI4.INP gồm 1 dòng duy nhất ghi số N. N<10
*Kết quả:* Ghi ra file văn bản có tên BAI4.OUT:
· Dòng đầu tiên ghi số M là số cách điền dấu vào biểu thức.
· M dòng tiếp theo, mỗi dòng ghi một kết quả tìm được.
*Bài 3:**Miền 0*
Cho một hình chữ nhật gồm M hàng, N cột, được chia thành MxN ô vuông. Mỗi ô vuông được ghi một trong hai số nguyên 0 hoặc 1. 
Miền 0 là một miền liên tục các số 0 thuộc các ô chung cạnh với nhau. Diện tích miền là số lượng các ô vuông cùng giá trị thuộc miền đó.
*Yêu cầu:* Tính diện tích miền 0 lớn nhất của hình chữ nhật đã cho.
*Dữ liệu:* Vào từ file văn bản BAI5.INP:
· Dòng đầu tiên ghi hai số M, N.
· M dòng tiếp theo, mỗi dòng ghi N số lần lượt là giá trị các ô trong bảng số.
*Kết quả:* Ghi ra file văn bản BAI5.OUT số nguyên duy nhất là diện tích miền 0 lớn nhất.
*Giới hạn:* 1 < M, N < 100.
*Bài 4** - Dãy con lồi* 
Dãy giá trị nguyên A=(A1, A2, …, AN) được gọi là lồi, nếu nó giảm dần từ A1 đến một Ai nào đó, rồi tăng dần tới AN. 
Ví dụ dãy lồi: 10 5 4 2 −1 4 6 8 12 
Yêu cầu: Lập trình nhập vào một dãy số nguyên, bằng cách xóa bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất. 
Dữ liệu: Dayloi.inp có dạng 
- Dòng đầu là N (N≤2000) 
- Dòng tiếp theo là N số nguyên của dãy số (các số kiểu integer) 
Kết quả: Dayloi.out gồm: 
- Dòng đầu tiên ghi số phần tử lớn nhất của dãy con tìm được 
- Dòng tiếp theo ghi các số thuộc dãy con (không thay đổi trật tự các phần tử trong dãy ban đầu) 
Ví dụ 


*Bài 5** - Dây chuyền thông báo* 
Các học sinh trong một lớp học quyết định lập một dây chuyền thông báo như sau. Mỗi học sinh chọn một học sinh duy nhất khác làm người kế tiếp để truyền trực tiếp thông báo. Khi mỗi học sinh nhận được thông báo, anh ta sẽ truyền ngay cho người kế tiếp của mình. 
Dây chuyền thông báo được gọi là tốt nếu nó thoả mãn điều kiện: Khi một học sinh A1 bất kỳ gửi thông báo cho người kế tiếp A2, A2 lại gửi cho người kế tiếp A3,..., cứ như vậy thì cuối cùng thông báo sẽ đến mọi người trong lớp kể cả người ban đầu (A1) đã phát ra thông báo. Không nhất thiết mọi dây chuyền thông báo là tốt. 
Bài toán đặt ra là: Cho trước một dây chuyền thông báo, hãy tìm số ít nhất việc thay đổi người kế tiếp để có thể nhận được một dây chuyền thông báo tốt. *Dữ liệu:* file văn bản THONGBAO.INP trong đó dòng thứ nhất ghi số N < 10000 là số hcjc sinh trong lớp, các họcc sinh này có tên từ 1 đến N. Trong dòng tiếp theo ghi N số, số thứ i là tên người kế tiếp của học sinh i. 

*Kết quả:* file THONGBAO.OUT như sau: dòng thứ nhất ghi số K là số thay đổi cần tiến hành (nếu dây chuyền thông báo đã cho là tốt thì K=0). Nếu K>0, trong K dòng tiếp theo, mỗi dòng ghi hai tên học sinh, người sau là người kế tiếp mới được thay đổi của người trước. 
*Bài 6** - Bày tranh* 
Cho n bức tranh mã số từ 1..n (n≤50). Người ta cần chọn ra một bức để đặt ở cửa phòng tranh, số còn lại được treo thẳng hàng trong phòng trên m vị trí định sẵn có mã số 1..m từ trái qua phải. Các bức tranh phải được treo theo trật tự nghiêm ngặt sau đây: tranh có số hiệu nhỏ phải treo ở trên tranh có số hiệu lớn. 
Biết các thông tin sau về mỗi bức tranh: 
- Tranh thứ i treo tại cửa sẽ đạt trị thẩm mỹ c_;_ 
- Tranh thứ i treo tại vị trí j sẽ đạt trị thẩm mỹ v[i,j]. 
- m+1≥n. 
- Các giá trị thẩm mỹ là những số tự nhiên không vượt quá 50. 
Yêu cầu: Hãy xác định một phương án treo tranh để có tổng trị thẩm mỹ là lớn nhất. 
*Dữ liệu:* Picture.INP 
- Dòng thứ nhất ghi n, m (cách nhau 1 dấu cách) 
- Dòng tiếp theo là n giá trị c. 
- Tiếp đến là n dòng, dòng i gồm m vị trí v[i,1], v[i,2],..v[i,m]. 
*Kết quả:* Picture.OUT
- Dòng thứ nhất ghi giá trị thẩm mỹ lớn nhất tìm được 
- Dòng thứ hai: ghi mã số hiệu bức tranh treo ở cửa phòng tranh. 
- Dòng thứ 3 ghi n-1 số tự nhiên sắp tăng chặt cho biết mã số các vị trí được chọn để treo tranh 
_Ví dụ:_ 
*Bài 7:** Xâu gọn* 
_Xâu gọn S là xâu có tối đa 250 kí tự gồm các chữ cái A..Z, a..z và các số nguyên dương (không lớn hơn 50). Các số nguyên dương cho biết số lần xuất hiện của dãy kí tự trong khai triển (đầy đủ) của S, nếu kí tự xuất hiện một lần thì có thể không viết số lần xuất hiện._
*Ví dụ*_: Xâu gọn_ 
_S : ”A2B(C2A)2D3” có dạng khai triển là “AABCCACCADDD” (có chiều dài là 12)._ 
*Yêu cầu*_: Cho N xâu gọn. Tính chiều dài của mỗi xâu ở dạng khai triển._
*Dữ liệu vào*_: Tệp văn bản XAUGON.INP gồm:_
_· Dòng 1: Ghi số N (1__£N__£100) số lượng xâu gọn._
_· N dòng tiếp theo mỗi dòng ghi 1 xâu gọn._
*Dữ liệu ra*_: Tệp văn bản XAUGON.OUT ghi N dòng, mỗi dòng là chiều dài của xâu ở dạng khai triển tương ứng, nếu gặp xâu gọn sai cú pháp thì ghi số 0._
*Bài 8.** Dàn đèn*
Cho một bảng kích thước mxn được chia thành lưới ô vuông đơn vị, tại mỗi ô của bảng có một trong các ký tự:
· ".": Ô trống.
· "+": Ô có chứa một đèn chưa bật sáng.
· "*": Ô có chứa một đèn đã bật sáng.
Hai đèn đã bật sáng bất kỳ không nằm cùng hàng hoặc cùng cột.
Yêu cầu: Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: Số đèn sáng trên mỗi hàng cũng như trên mỗi cột của bảng tối đa là 1.
*Dữ liệu vào:* Tệp văn bản *DANDEN.INP* 
· Dòng 1: Ghi hai số m, n (1 £ m, n £ 200) cách nhau một ký tự trắng
· m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng_ 
Dữ liệu ra: Tệp văn bản DANDEN.OUT_ _
· Dòng 1: Ghi số đèn có thể bật thêm
· m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng sau khi đã bật sáng thêm các đèn.
_

----------


## seodienlanh

> *Bài 8.** Dàn đèn*
> Cho một bảng kích thước mxn được chia thành lưới ô vuông đơn vị, tại mỗi ô của bảng có một trong các ký tự:
> · ".": Ô trống.
> · "+": Ô có chứa một đèn chưa bật sáng.
> · "*": Ô có chứa một đèn đã bật sáng.
> Hai đèn đã bật sáng bất kỳ không nằm cùng hàng hoặc cùng cột.
> Yêu cầu: Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: Số đèn sáng trên mỗi hàng cũng như trên mỗi cột của bảng tối đa là 1.
> *Dữ liệu vào:* Tệp văn bản *DANDEN.INP* 
> · Dòng 1: Ghi hai số m, n (1 £ m, n £ 200) cách nhau một ký tự trắng
> ...


_
- Diễn đàn là nơi "vun đầy kiến thức, đắp đầy chuyên môn". Nên nếu HSG hoặc các thành viên trong diễn đàn có lời giải thì sẽ post lên forum để mọi người cùng tham khảo . Thầy vui lòng vào diễn đàn để tìm thông tin .
- Đề bài 8 , thầy kiểm tra lại nhá , HSG thấy chỗ này hơi vô lí "Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: Số đèn sáng trên mỗi hàng cũng như trên mỗi cột của bảng tối đa là 1.". HSG nghĩ là ít nhất chứ không phải nhiều nhất ._

----------


## komoro92

Mấy bài này sao thấy quen quen, hình như trong diễn đàn có lần đề cập tới rồi thì phải. Mà em thấy mấy bài này có nhìu bài theo QHD có phải không ạ?

----------


## hungtk15122010

*Bài 2: Biểu thức 0.



```
      const fi='bieuthuc0.inp';
            fo='bieuthuc0.out';

      var   f:text;
            n:byte;
            t:integer;
            kq:string;
            x:array[1..11] of byte;

      procedure inp;
      begin
            assign(f,fi);
            reset(f);
            readln(f,n);
            close(f);
      end;

      procedure try(i:byte);
      var   j:byte;
      begin
            for j:=1 to 2 do
            begin
                  x[i]:=j;
                  if j=1 then t:=t+i+1
                  else t:=t-i-1;
                  if (i=n-1) then
                  begin
                        if (t=0) then
                        begin
                              for i:=1 to n-1 do
                                    if x[i]=1 then kq:=kq+'+'
                                    else kq:=kq+'-';
                        end;
                  end
                  else try(i+1);
                  if j=1 then t:=t-i-1
                  else t:=t+i+1;
            end;
      end;

      procedure pri;
      var   i,k:integer;
      begin
            assign(f,fo);
            rewrite(f);  k:=0;
            writeln(f,length(kq) div (n-1));
            for i:=1 to length(kq) do
            begin
                  inc(k);
                  write(f,k,kq[i]);
                  if i mod (n-1)=0 then
                  begin
                        write(f,n);
                        writeln(f);
                        k:=0;
                  end;
            end;
            close(f);
      end;

BEGIN
      inp;
      t:=1;
      try(1);
      pri;
END.
```




*

----------


## trungvn2092

bài 1:
- x là xâu ban đầu , y là xâu đảo ngược của xâu ban đầu 
- goi l[n,n] là độ dài của xâu con chung dài nhất 
- n-l[n,n] là kết quả cần tìm


```
      const fi='doixung.inp';
            fo='doixung.out';

      var   f:text;
            x,y:string;
            n:integer;
            l:array[0..256,0..256] of integer;

      procedure inp;
      var   i:integer;
      begin
            assign(f,fi);
            reset(f);
            readln(f,x);
            n:=length(x);
            y:='';
            for i:=n downto 1 do y:=y+x[i];
            close(f);
      end;

      function max(a,b:integer):integer;
      begin
            max:=a;
            if max<b then max:=b;
      end;

      procedure sol;
      var   i,j:integer;
      begin
            for i:=0 to n do
            begin
                  l[i,0]:=0;
                  l[0,i]:=0;
            end;
            for i:=1 to n do
                  for j:=1 to n do
                        if x[i]=y[j] then l[i,j]:=l[i-1,j-1]+1
                        else l[i,j]:=max(l[i-1,j],l[i,j-1]);
      end;

      procedure pri;
      begin
            assign(f,fo);
            rewrite(f);
            write(f,n-l[n,n]);
            close(f);
      end;

BEGIN
      inp;
      sol;
      pri;
END.
```

----------


## hoanghuy87

- Em không hiểu bài toán đặt ra ở bài 5 là như thế nào ,
- Bài 6 : Các bức tranh phải được treo theo trật tự nghiêm ngặt sau đây: tranh có số hiệu nhỏ phải treo ở trên tranh có số hiệu lớn.
Vậy phải xếp theo trật tự từ 1-> m !? Bài toán trở nên vô nghĩa.

Mong thầy giải đáp.

----------


## tranhuytn668

Mình nói tạm qua một ít:
Bài 1: quy hoạch động
Gọi F[i,j] là số kí tự ít nhất để biến xâu bắt đầu từ vị trí i đến vị trí j thành xâu đối xứng
Khởi tạo f[i,i] = 0; // 1 kí tự
f[i,i+1] = 1 nếu s_ # s[j];
xét trường hợp f[i,j];
nếu s = s[j], hai kí tự ở 2 đầu = nhau, thì số kì tự cần thêm = số kí tự để biến xấu [i+1,j-1] thành đối xừng => f[i,j] = f[i+1, j-1];
nếu s # s[j], có 3 cách biến sau
1: sau khi biến được đoạn [i,j-1] thì cộng thêm 1 kí tự nữa để giống s[j]
2: sau khi biến được đoạn [i+1,j] thì cộng thêm 1 kí tự nữa để giống s
3: sau khi biến được đoạn [i+1,j-1] thì cộng thêm 2 kí tự nữa để giống s[j] và s
=> f[i,j] = max ( f[i+1,j] +1, f[i, j-1] + 1, f[i+1,j-1] + 2);
trong khi đó xây dựng hàm trace để truy vết
Bài 2 cũng quy hoạch động
Số 1 chắc chắn là phép + rồi, giờ còn n-1 số
Do đặt phép trừ hoặc phép cộng vào giữa các số, nên sẽ có 1 nhóm là trừ đi và 1 nhóm số là cộng thêm. Việc của bạn là tìm các chia n-1 số còn lại thành 2 nhóm sao cho tổng của chúng hơn kém nhau 1 đơn vị ( vì do 1 nhóm sẽ cộng với số 1 đầu tiên) Sau đó bạn quy hoạc động, không biết là bạn có biết bài chia kẹo không nhỉ.
...
chán chả buồn gõ nữa
Nhưng mình không hiểu bạn học ở Đại học cái gì mà đến những bài này không biết làm, có lẽ bạn đi vào chuyên ngành sư phạm hơn còn mình đi theo hẳn nghiệp cntt rồi, nhưng mà bạn yên tâm, bạn chỉ cần hướng dẫn cho học sinh trong đội tuyển cách học là được. Hồi cấp 3 bọn mình học là dư sức làm những bài kiểu như thế này rồi
Bạn có thể liên lạc trực tiếp IM [email protected]<script data-cfhash='f9e31' type="text/javascript">/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScr  ipt||function(){for(t=document.getElementsByTagNam  e('script'),e=t.length;e--if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if  (a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.l  ength-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString  (16)).slice(-2);p.replaceChild(document.createTextNode(decodeUR  IComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */</script> mình có thể giúp cho bạn 1 số kinh nghiệp và tài liệu thi QG mà mình là từng là người trong cuộc_

----------


## honganh_dn

bài 3:


```
      const fi='mien0.inp';
            fo='mien0.out';

      var   t,a:array[0..101,0..101] of integer;
            n,m,i,j,k,l,max,x,b:integer;
            f:text;

      procedure inp;
      begin
            fillchar(t,sizeof(t),0);
            assign(f,fi);
            reset(f);
            readln(f,n,m);
            max:=-maxint;
            for i:=1 to n do
            begin
                  for j:=1 to m do
                  begin
                        read(f,b);
                        if b=1 then a[i,j]:=0 else a[i,j]:=1;
                        t[i,j]:=t[i-1,j]+t[i,j-1]-t[i-1,j-1]+a[i,j];
                        for k:=1 to i do
                              for l:=1 to j do
                              begin
                                    x:=t[i,j]-t[i-k,j]-t[i,j-l]+t[i-k,j-l];
                                    if x>max then if k*l=x then max:=x;
                              end;
                  end;
                  readln(f);
            end;
            close(f);
      end;

      procedure pri;
      begin
            assign(f,fo);
            rewrite(f);
            write(f,max);
            close(f);
      end;

BEGIN
      inp;
      pri;
END.
```

bài 4:


```
      const fi='DAYLOI.INP';
            fo='DAILOI.OUT';

      var   f:text;
            k,l,n:longint;
            a,trc1,trc2,d1,d2:array[1..2000] of longint;

      procedure inp;
      var i,j,max,luu:longint;
      begin
            assign(f,fi);
            reset(f);
            readln(f,n);
            for i:=1 to n do
            begin
                  read(f,a[i]);
                  d1[i]:=1;
                  luu:=0;
                  for j:=i-1 downto 1 do
                        if (d1[i]<d1[j]+1) and (a[i]<=a[j]) then
                        begin
                              d1[i]:=d1[j]+1;
                              luu:=j;
                        end;
                  trc1[i]:=luu;
            end;
            close(f);
      end;

      procedure sol;
      var i,j,max,luu:longint;
      begin
            for i:=n downto 1 do
            begin
                  d2[i]:=1;
                  luu:=0;
                  for j:=i+1 to n do
                        if (d2[i]<d2[j]+1) and (a[i]<=a[j]) then
                        begin
                              d2[i]:=d2[j]+1;
                              luu:=j;
                        end;
                        trc2[i]:=luu;
                        if d1[i]+d2[i]>k then
                        begin
                              k:=d1[i]+d2[i];
                              l:=i;
                        end;
            end;
      end;

      procedure luuvet(i:longint);
      begin
            if trc1[i]<>0 then luuvet(trc1[i]);
            write(f,a[i],' ');
      end;

      procedure pri;
      begin
            assign(f,fo);
            rewrite(f);
            writeln(f,k-1);
            luuvet(l);
            while trc2[l]<>0 do
            begin
                  l:=trc2[l];
                  write(f,a[l],' ');
            end;
            close(f);
      end;

BEGIN
      inp;
      sol;
      pri;
END.
```

----------

