[Tin] Pascan và vấn đề thi HSG Tin học

Bài 1 - Trò chơi Tích - Tắc vuông
(Dành cho học sinh THCS và THPT)
Trên một lưới kẻ ô vuông có 2 người chơi như sau: người thứ nhất mỗi lần chơi sẽ đánh dấu x vào 1 ô trống. Người thứ hai được đánh dấu 0 vào 1 ô trống. Người thứ nhất muốn đạt được mục đích là đánh được 4 dấu x tạo thành 4 đỉnh của 1 hình vuông. Người thứ hai có nhiệm vụ ngăn cản mục đích đó của người thứ nhất. http://photobucket.com/images/scared...%20of%20santa/

Lập chương trình tìm thuật toán tối ưu cho người thứ nhất (người thứ nhất có thể luôn thắng).
Chú ý: Lưới ô vuông được coi là vô¬ hạn về cả hai phía.


Bài 2 - Đoạn thẳng và hình chữ nhật
(Dành cho học sinh THPT)
Hãy viết một chương trình xác định xem một đoạn thẳng có cắt hình chữ nhật hay không?
Ví dụ:
Cho tọa độ điểm bắt đầu và điểm kết thúc của đường thẳng: (4,9) và (11,2);
Và tọa độ đỉnh trái trên và đỉnh phải dưới của hình chữ nhật: (1,5) và (7,1);

Đoạn thẳng được gọi là cắt hình chữ nhật nếu đoạn thẳng và hình chữ nhật có ít nhất một điểm chung.
Chú ý: mặc dù tất cả dữ liệu vào đều là số nguyên, nhưng tọa độ của các giao điểm tính ra chưa chắc là số nguyên.
Input
Dữ liệu vào trong file Input.Inp kiểm tra N trường hợp (N <= 1000). Dòng đầu tiên của file dữ liệu vào là số N. Mỗi dòng tiếp theo chứa một trường hợp kiểm tra theo quy cách sau:
xstart ystart xend yend xleft ytop xright yboottm
trong đó: (xstart, ystart) là điểm bắt đầu và (xend, yend) là điểm kết thúc của đoạn thẳng. Và (xleft, ytop) là đỉnh trái trên, (xright, ybottom) là đỉnh phải dưới của hình chữ nhật. 8 số này được cách nhau bởi một dấu cách.
Output
Với mỗi một trường hợp kiểm tra trong file Input.txt, dữ liệu ra trong file Output.out phải đưa ra một dòng gồm hoặc là chữ cái "T" nếu đoạn thẳng cắt hình chữ nhật, hoặc là "F" nếu đoạn thẳng không cắt hình chữ nhật.
Ví dụ
Input.Inp
1
4 9 11 2 1 5 7 1
Output.out
F

Bài 1 : Xâu kí tự đơn điệu
Là sâu gồm chữ cái thường và chữ cái hoa trong đó không có chữ cái nào trùng hoặc không phải là chữ cái trong bảng tiếng anh. Lập CT nhập xâu và sử lí thành xâu đơn điệu
Bài 2 :Bàn cờ vua...
Đếm số quân cờ lớn nhất đặt vào bàn cờ tính theo đường thẳng bất kì .

bài 2 :
program dt;
http://photobucket.com/images/scared...%20of%20santa/

uses crt;

const inp='inp.txt'; out='out.txt';

var a: array [1..100,1..100] of byte;
i,j, maxxx :byte; n:integer;
fi,fo:text;
{===================================}
procedure demngang(x,y:byte; var d:byte);
begin
d:=0;
while a[x,y] = 1 do
begin
d:=d+1;
y:=y+1;
end;
end;
{+_+_____________________+}

procedure demdoc(x,y:byte; var d:byte);

begin
d:=0;
while a[x,y] = 1 do
begin
d:=d+1;
x:=x+1;
end;
end;
{+++++++++++++++++++++++++++++++++++++}
procedure demcheochinh(x,y:byte; var d:byte);
begin
d:=0;
while a[x,y] = 1 do
begin
d:=d+1;
x:=x+1;
y:=y+1;
end;
end;
{++++++++++++++++++++++++++++++++++++++++++++++}
function max(a,b:byte):byte;
begin
if a<b then max:=b else max:=a;
end;
{+++++++++++++++++++++++++++++++++++++++++++++++++ ++}
procedure demcheophu(x,y:byte; var d:byte);

begin
d:=0;
if a[x,y] = 1 then
while (a[x,y] = 1) and (x<>0) do
begin
d:=d+1;
x:=x-1;
y:=y+1;
end;
end;
procedure xuli;
var dcc,dcp,dn,dd: array [1..250] of byte;
ddm,dnm,dcpm, dccm, k:byte;
begin

k:=1;
for i:= 1 to n do
begin
for j:= 1 to n do
begin
demngang(i,j,dn[k]);
{ write(dn[k]); }
k:=k+1;
end;
writeln;
end;
k:=1;
for i:= 1 to n do
begin
for j:= 1 to n do
begin
demdoc(i,j,dd[k]);
{ write(dd[k]); }
k:=k+1;
end;
writeln;
end;
k:=1;
for i:= 1 to n do
begin
for j:= 1 to n do
begin

demcheochinh(i,j,dcc[k]);
{ write(dcc[k]);{P{}
k:=k+1;
end;
writeln;
end;
k:=1;
for i:= 1 to n do
begin
for j:= 1 to n do
begin
demcheophu(i,j,dcp[k]);
{ write(dcp[k]); {}
k:=k+1;
end;
writeln;
end;

ddm:=0;
dccm:=0;
dnm:=0;
dcpm:=0;
for i:=1 to n*n do
begin
if ddm<dd[i] then ddm:=dd[i];
if dccm<dcc[i] then dccm:=dcc[i];
if dcpm<dcp[i] then dcpm:=dcp[i];
if dnm<dn[i] then dnm:=dn[i];

end;
maxxx:=max(max(max (ddm,dnm),dccm),dcpm);
writeln;
{write(maxxx:2,ddm:2,dccm:2,dcpm:2,dnm:2); }
readln;
end;

{______________________+++++++}

procedure nhap;
begin
assign(fi,inp);
reset(fi);

read(fi,n);

for i:=1 to n do
for j:=1 to n do
read(fi,a[i,j]) ;


close(fi);
{ clrscr;
write(' nhap n ') ;
readln(n);
write ('nhep ma tran');
for i:=1 to n do
for j:=1 to n do
begin
Write('nhap a[',i,',',j,']=');
readln(a[i,j]) ;
end;

for i:=1 to n do
begin
for j:=1 to n do
begin
write(a[i,j]);
end;
writeln;
end;
readln; }
end;
{++++++++++++++++++++++++++++++++++++++++++_}
procedure xuat;

begin
assign (fo,out);
rewrite(fo);
write(fo, maxxx);
close(fo);
end;
begin
nhap;
xuli;
xuat;
end.

mọi nguơif xem hộ xem saio o đâu không né

bài 1

program saudondieu;

type st=string; cthuong='a'..'z'; choa='A'..'Z';

const input='inp.txt'; out='out.txt';

var fi,fo:text;
b, a:array[1..40] of st ;
procedure nhap;
var i:byte;
begin
assign(fi,input);
reset(fi);
for i:= 1 to 40 do
read(fi,a[i]);
close(fi);
end;
function saudon(sauvao:st): st;
var i,j:byte; t:st; ct:cthuong; ch:choa ;
k:array[1..256]of byte ;
begin
t:='';
for i:=1 to length(sauvao) do
if (ord(sauvao[i])>=65) and (ord(sauvao[i])<=90) or ( (ord(sauvao[i])>=97)and(ord(sauvao[i])<=122 ) )
then t:=t+sauvao[i];
j:=1;
for i:=1 to length(t) do
if t[i] = t[i+1] then
begin
k[j]:=i;
j:=j+1;
end;
for i:=j downto 1 do
delete(t,k[i],1);
saudon:=t;
end;
procedure xoa_cuoi(a:st; var b:st);
var t:byte;
begin
t:=length(a);
if a[t]=b[1] then delete(b,1,1);
end;
procedure xuli;
var i:byte;
begin
for i:= 1 to 40 do
b[i]:=saudon(a[i]);
for i:= 1 to 39 do
xoa_cuoi(b[i],b[i+1]);
end;
procedure xuat;
var i:byte;
begin
assign(fo,out);
rewrite(fo);
for i:=1 to 40 do
write(fo,b[i]);
close(fo);
end;
begin
nhap;
xuli;
xuat;
end.

mọi người làm thử xem
Bài 1

Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn ( đánh từ số 1 đến N) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng Đế di km (i=1,2,...., N). Hội thi có M xe taxi đánh số từ 1 đến M (MN) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản P2.INP:
- Dòng đầu tiên chứa hai số nguyên dương N, M (NM200);
- Dòng thứ hai chứa các số nguyên dương d1, d2, ..., dN;
- Dòng thứ ba chứa các số nguyên dương v1, v2, ..., vM.
- Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.
Kết quả: Ghi ra file văn bản P2.OUT:
- Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
- Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ..., N).

bài này nfay chị hoacuc oi

xin thông báo

Đội tuyển tin năm nay ra quân kết quả như sau :

Cao Văn Tùng 11A3 :16 điểm giải nhì

Đỗ Ngọc Thắng 11A8 : 15 điểm giải 3

Nguyễn Tiến Thành 11A6 :13 điểm giải 3

Moij người lâfm thử cái này xem




ĐỀ THI CHÍNH THỨC
Môn Tin học lớp 10
Ngày thi: 23/4/2011
Thời gian làm bài: 180 phút.
(không kể thời gian giao đề)

Chữ ký giám thị 1:
...............................
Chữ ký giám thị 2:
...............................
(Đề thi này có 03 trang)
Bài 1 ( 6 điểm) : Chu kì của xâu Tên chương trình : CYC.PAS
Một xâu P được gọi là tiền tố của xâu A nếu tồn tại xâu B sao cho xâu PB (ghép B vào sau P) bằng xâu A. Một tiền tố P của A được gọi là tiền tố thực sự nếu P khác rỗng và P khác A.
Xâu Q được gọi là xâu chu kì của xâu A nếu Q là một tiền tố thực sự của A và A là tiền tố của xâu QQ. Chẳng hạn, abab và ababab là hai xâu chu kì của xâu abababa. Chu kì cực đại của A là xâu chu kì dài nhất của A ( nếu A không có xâu chu kỳ thì coi như độ dài chu kỳ cực đai = 0 ).
Cho một xâu S chỉ gồm các chữ cái in thường (‘a’..‘z’), hãy tính tổng độ dài chu kì cực đại của tất cả các tiền tố của S.
Dữ liệu vào từ tệp CYC.INP
• Dòng 1: số nguyên N (độ dài xâu S , 1≤N≤ 250)
• Dòng 2: xâu S
Kết quả ra tệp CYC.OUT ghi số nguyên kết quả
Ví dụ :
cyc.inp cyc.out
8
babababa 24
Giải thích ví dụ
Tiền tố Chu kì cực đại Độ dài
‘b’ ‘’ 0
‘ba’ ‘’ 0
‘bab’ ‘ba’ 2
‘baba’ ‘ba’ 2
‘babab’ ‘baba’ 4
‘bababa’ ‘baba’ 4
‘bababab’ ‘bababa’ 6
'babababa’ ‘bababa’ 6
Tổng 24

Bài 2 (7 điểm ) : Trả tiền mua hàng Tên chương trình : MONEY.PAS
Một người đi mua hàng với giá trị của hàng là M đồng .Trong túi người đó có N loại tiền với các mệnh giá T1, T2, . . . TN, mỗi loại có một số lượng tương ứng S1, S2, . . . SN. Hỏi người đó có thể trả đúng số tiền mua hàng được không (không tính khả năng trả thừa tiền rồi người bán hàng trả lại ..), nếu có thể hãy đưa ra cách trả giúp cho người đó. (Biết M, N, Ti, Si nguyên dương; M ≤ 10000 ; N≤10 ; Si ≤ 10 ; Ti ≤10000 ; Ti > Ti+1 )
Dữ liệu vào từ tệp MONEY.INP
- Dòng 1: chứa số N và M
- Dòng 2: chứa N số Ti
- Dòng 3: chứa N số Si.
Kết quả ra tệp MONEY.OUT
- Dòng 1 ghi tổng số tờ phải trả trong trường hợp có cách trả tiền , nếu không thì ghi 101
- Trường hợp có cách trả thì dòng 2 ghi N số với ai là số tờ tiền phải trả tương ứng với loại tiền có mệnh giá Ti , nếu có nhiều cách trả với tổng số tờ ít nhất như nhau thì ghi ra dãy có thứ tự từ điển lớn nhất ( các số ghi cách nhau một dấu cách ).
Ví dụ 1:
MONEY.INP
5 91
13 9 6 3 1
4 10 4 6 5
MONEY.OUT
9
4 4 0 1 0
( ở đây còn cách trả 9 tờ nữa là
4 3 2 0 0 nhưng có thứ tự từ điển
nhỏ hơn …)
Ví dụ 2:
MONEY.INP
5 100
60 9 5 3 1
4 2 2 3 2
MONEY.OUT
101



Bài 3 (7 điểm): Tập số hữu tỷ Tên chương trình : CANTOR.PAS
Georg Cantor là nhà toán học nổi tiếng và một trong những chứng minh quan trọng của ông là việc chỉ ra rằng lực lượng của tập số hữu tỷ đúng bằng lực lượng tập số tự nhiên. Cơ sở của việc chứng minh đó là sơ đồ sau:
1/1
2/1 1/2
3/1 2/2 1/3
4/1 3/2 2/3 1/4
5/1 4/2 3/3 2/4 1/5
6/1 5/2 4/3 3/4 2/5 1/6
...
Trong sơ đồ trên, mỗi số hữu tỷ dương tương ứng với một số nguyên dương , số đầu tiên là 1/1, số thứ 2 là 1/2, số thứ 3 là 2/1, số thứ 4 là 3/1, số thứ 5 là 2/2, số thứ 6 là 1/3 , số thứ 7 là 1/4 , … ( đếm theo đường zíc zắc )
Yêu cầu: Cho một số nguyên dương , hãy tìm phân số có số thứ tự tương ứng với nó theo sơ đồ trên.
Dữ liệu vào từ tệp CANTOR.INP
Gồm 1 dòng ghi số nguyên dương n ( n≤1017 )
Kết quả ra tệp CANTOR.OUT
Gồm 1 dòng ghi phân số có thứ tự n dưới dạng a/b.
Ví dụ :

CANTOR.INP
3
7
9
11
14
1000000 1009/406
CANTOR.OUR
2/1
1/4
3/2
5/1
2/4

TỔNG QUAN VỀ CÁC BÀI THI

----------------Tên file chương trình----Dữ liệu vào-----Dữ liệu ra
Bài 1-----------HUUNGHI.PAS---------------------------Màn hình
Bài 2-----------XOACHUSO.PAS-------------------------Màn hình
Bài 3-----------XOAYOC.PAS------------Bàn phím------Màn hình
Bài 4-----------AMSTRONG.PAS-------------------------Màn hình
Bài 5-----------SODOCDAC.PAS---------Bàn phím------Màn hình





Bài 1: Cặp số ''hữu nghị'' (2 điểm)

------Hai số nguyên dương được gọi là ''hữu nghị'' nếu số này bằng tổng các ước thực sự của số kia và ngược lại (ước thực sự của một số nguyên dương là ước nhỏ hơn số đó, ví dụ số 6 có các ước thực sự là 1,2,3). Hãy tìm các cặp số ''hữu nghị'' từ 100 đến 1000.
------Kết quả: Đưa ra màn hình, mỗi cặp số tìm được ghi trên một dòng, số bé viết trước, các số cách nhau tối thiểu một dấu cách.

Bài 2: Xoá chữ số (2 điểm)

------Tìm tất cả các số có 4 chữ số thoả mãn tính chất: Nếu xoá đi 1 chữ số nào đó thì số đó giảm đi 9 lần.
------Kết quả: Đưa ra màn hình, gồm nhiều dòng, mỗi dòng 2 số: số thứ nhất là số có 4 chữ số thoả mãn tính chất trên, số thứ hai là số có 3 chữ số có được từ số thứ nhất sau khi đã xoá đi 1 chữ số để được số bằng 1/9 số thứ nhất, các số cách nhau tối thiểu một dấu cách. Các kết quả ghi không được trùng nhau
------Dòng cuối ghi số các số tìm được

Bài 3: Xoáy ốc (2 điểm)

------Lập chương trình nhập các số tự nhiên liên tiếp 1,2,3,4,...,N*N vào bảng A[N*N] theo chiều xoáy ốc ngược chiều kim đồng hồ.
------Sau đó in ra bảng A[N*N] ra màn hình. Ví dụ N=4 cấn nhập vào và in ra kết quả như sau:
---1--12-11-10
---2--13-16--9
---3--14-15--8
---4---5--6--7

---Dữ liệu vào: Nhập từ bàn phím số nguyên dương N<=20.
---Kết quả: Đưa ra màn hình bảng A[N*N] gồm các số tự nhiên sắp xếp theo yêu cầu trên.


Bài 4: Số Amstrong (2.5 điểm)

-----Số tự nhiên N có k chữ số, được gọi là số Amstrong nếu N bằng tổng các luỹ thừa bậc k của các số của nó.
-----Ví dụ:

-----Hãy tìm tất cả các số Amstrong có k chữ số, với 3<=k<=6
-----Kết quả: Đưa ra màn hình mỗi số tìm được viết trên một dòng.
-----Dòng cuối cùng ghi số các số tìm được.

Bài 5: Số độc đắc (1.5 điểm)


----- Viết các số tự nhiên từ 1 đến 2009 theo một vòng tròn cùng chiều quay kim đồng hồ. Cũng theo chiều đó, bắt đầu từ số 1, cứ đếm từ 1 đến số thứ 612 thì xoá số đó đi. Lại bắt đầu từ số còn lại đứng ngay sau số vừa bị xoá, lặp lại quá trình đến khi còn 1 số thì dừng lại.

-----a) Hỏi số còn lại là số nào?
-----b) Muốn số còn lại là số thứ L (0<L<2010) thì ban đầu cần xuất phát từ số nào?
-------- Dữ liệu vào: Nhập từ bàn phím số nguyên dương L (0<L<2010)
---------Kết quả: Đưa ra màn hình theo qui cách: dòng thứ nhất là kết quả cho câu hỏi a); dòng thứ hai là kết quả cho câu hỏi b).

Bài 1:Số đối xứng

Một số được gọi là đối xứng khi các chữ số của nó đối xứng qua tâm.Ví dụ:9,77,919,98289. Cho một số nguyên dương x (x co số chữ số <=100),hãy tìm số đối xứng lớn hơn và gần x nhất.

Dữ liệu vào: Từ tệp văn bản SODX.INP gồm 1 dòng ghi số x.

Kết quả :Ghi ra tệp văn bản SODX.OUT gồm 1 dòng ghi số đối xứng lớn hơn và gần x nhất.

Bài 2:Chiếm chỗ

Cho một lưới ô vuông gồm m dòng,n côt. Có k người chơi trò trơi chiếm chỗ như sau: Ban đầu mỗi người được chọn một ô ( bằng cách ghi số thứ tự của mình vào ô đó ), không được nhận ô người khác chọn. Sau đó mỗi lượt người chơi theo thứ tự từ nhỏ đến lớn, chọn tiếp các ô chưa có ai chọn kề cạnh với một trong các ô mình đã chọn từ các lượt trước đó. Quá trình được lặp lại cho đến khi tất cả các ô đều được chọn.

Yêu cầu : Xác định số các ô mỗi người đã chọn được.

Dữ liệu vào: Từ tệp văn bản CHIEMCHO.INP

- Dòng đầu là 3 số nguyên dương m,n,k.

- k dòng tiếp theo, mỗi dòng chỉ vị trí của dòng, cột của ô mà người chơi thư i chọn ban đầu.

Trong đó :m,n - chỉ số dòng, cột của lưới ô vuông (m,n<=500)

k- chỉ số người chơi (2<=k<=5)

Kết quả: Ghi ra tệp văn bản CHIEMCHO.OUT một dòng gồm k số, số thứ i là số ô mà người thứ i chọn được. Các số cách nhau ít nhất một khoảng trắng.