Đề thi HSG TP.HCM năm 2006-2007

[m2mpro]

Bài 1: Dãy "tốt"
Một dãy E được gọi là "tốt" khi :Trong dãy E có tồn tại một số K và trong dãy E có ít nhất một số nhỏ hơn K, số các số nhỏ hơn K phải bằng số các số lớn hơn K.
INPUT: (set.inp)
- Dòng đầu tiên là số phần tử của dãy
- Dòng tiếp theo là các phần tử của dãy
OUTPUT: (set.out)
- Nếu dãy là "tốt" thì ghi ra 1 không thì in ra 0;
VÍ DỤ:
InPUT
-1 2 1 4 5 3 6
OUTPUT
1
( Trong đó k=3, -1 2 1 < k, 4 5 6 > k);

Bài 2: Số thừa
Một số gọi là số thừa khi tổng các ước số của nó cộng lại lớn hơn nó ( tính luôn số 1 nhưng không tính chính nó ).
Yêu cầu: Input là một số N, em hãy tìm ra một số thừa nhỏ nhất và không nhỏ hơn N và nhỏ hơn hoặc bằng 10000.
INPUT:
- Số N
OUTPUT:
- Số thừa không nhỏ hơn N.
VÍ DỤ:
INPUT: (anum.inp)
6
OUTPUT: (anum.out)<- Quên mất tên file :D
12
Giải thích: 1+2+3=6;1<7;1+2+4 < 8;1+3<9;1+2+5<10;1<11;1+2+3+4+6>12)

Bài 3: Lỗ Hỏng ( không nhớ là lỗ hổng hay là lỗ hỏng )
Cho một ma trận cấp m*n, trong đó có các lỗ hỏng ( vì lí do kĩ thuật :D), bạn hay tìm ra chu vi ma trận vuông lớn nhất không vướng các lỗ hỏng .
INPUT: (board.inp)
- Dòng đầu tiên là m(hàng) và n(cột)
- Dòng kế tiếp là số lỗ hỏng
- Các dòng tiếp theo mỗi hàng vị trí hàng và cột của các lỗ hỏng.
OUTPUT: (board.out)
- Chu vi của ma trận vuôn không bị lỗ hỏng
VÍ DỤ:
INPUT:
5 6
3
2 2
2 5
4 4
OUTPUT:
9
- Năm trước có mấy người làm trong 40 - 45 phút. ( thầy em nói )
- Nói chung thì .. cũng không khó lắm:D

P/S: Đã sửa tên file theo đúng đề bài :D

[mr_invincible]

INPUT: (sothua.inp)<- Quên mất tên file :D
6
OUTPUT: (sothua.out)<- Quên mất tên file :D
12


Tên file thế nào chả được mà bạn
Làm đề này mà trình độ tương đối khá thì chỉ mất khoảng 45 phút là đúng rồi :D

[trankientrung]

Mình thì thấy đọc cũng hiểu những không biết làm được không! :D

[phuclun]

Tên file thế nào chả được mà bạn
Làm đề này mà trình độ tương đối khá thì chỉ mất khoảng 45 phút là đúng rồi :D

Có thể thi TP ko chú trọng vấn đề này nhưng thường trong những cuộc thi cấp Tp trở lên sai tên file=đánh dấu bài=0 chấm mặc dù đúng hay sai.

[phuclun]

Bài 1 dễ thấy nếu số phần tử là chẵn thì in ra 0,nếu là lẻ sắp xếp lại,lấy phần tử a[n+1/2] là k{nếu a[n+1/2-1] hoặc a[n+1/2 +1] bằng k thì cũng in ra số 0).
bài 2 thì dùng while (true)do,mỗi lần tăng lên 1,xong tìm ước,tính tổng,nếu tìm đc thì in ra rồi exit ,nói chung cũng ko khó lắm.
Bài 3 có lẽ là bài khó nhằn nhất trong đây,BFS mà quất tới vậy.
P/s:đề ko có giới hạn sao,thế này làm kiểu gì mà chả đc.Bài 1,bài 2 10 phút chắc cũng code xong,bài 3 thêm nửa tiếng nữa.Chắc m2mpro làm 20Đ đề này quá.

[mr_invincible]

Có thể thi TP ko chú trọng vấn đề này nhưng thường trong những cuộc thi cấp Tp trở lên sai tên file=đánh dấu bài=0 chấm mặc dù đúng hay sai.

Nhưng mà đây đâu phải đi thi thật -> không biết tên file cũng không sao, còn đi thi thì tất nhiên là phải đúng tên file rồi :D

[mr_invincible]

Bài 1 dễ thấy nếu số phần tử là chẵn thì in ra 0,nếu là lẻ sắp xếp lại,lấy phần tử a[n+1/2] là k{nếu a[n+1/2-1] hoặc a[n+1/2 +1] bằng k thì cũng in ra số 0).


Phải loại bỏ các phần tử bằng nhau trước rồi mới có thể làm vậy chứ

[m2mpro]

Bài 1: Dãy "tốt"
Một dãy E được gọi là "tốt" khi :Trong dãy E có tồn tại một số K và trong dãy E có ít nhất một số nhỏ hơn K, số các số nhỏ hơn K phải bằng số các số lớn hơn K.
INPUT: (set.inp)
- Dòng đầu tiên là số phần tử của dãy
- Dòng tiếp theo là các phần tử của dãy
OUTPUT: (set.out)
- Nếu dãy là "tốt" thì ghi ra 1 không thì in ra 0;
VÍ DỤ:
InPUT
-1 2 1 4 5 3 6
OUTPUT
1
( Trong đó k=3, -1 2 1 < k, 4 5 6 > k);

Bài 2: Số thừa
Một số gọi là số thừa khi tổng các ước số của nó cộng lại lớn hơn nó ( tính luôn số 1 nhưng không tính chính nó ).
Yêu cầu: Input là một số N, em hãy tìm ra số thừa khong nhỏ hơn N.
INPUT:
- Số N
OUTPUT:
- Số thừa không nhỏ hơn N.
VÍ DỤ:
INPUT: (anum.inp)
6
OUTPUT: (anum.out)<- Quên mất tên file :D
12
Giải thích: 1+2+3=6;1<7;1+2+4 < 8;1+3<9;1+2+5<10;1<11;1+2+3+4+6>12)

Bài 3: Lỗ Hỏng ( không nhớ là lỗ hổng hay là lỗ hỏng )
Cho một ma trận cấp m*n, trong đó có các lỗ hỏng ( vì lí do kĩ thuật :D), bạn hay tìm ra chu vi ma trận vuông lớn nhất không vướng các lỗ hỏng .
INPUT: (board.inp)
- Dòng đầu tiên là m(hàng) và n(cột)
- Dòng kế tiếp là số lỗ hỏng
- Các dòng tiếp theo mỗi hàng vị trí hàng và cột của các lỗ hỏng.
OUTPUT: (board.out)
- Chu vi của ma trận vuôn không bị lỗ hỏng
VÍ DỤ:
INPUT:
5 6
3
2 2
2 5
4 4
OUTPUT:
9
- Năm trước có mấy người làm trong 40 - 45 phút. ( thầy em nói )
- Nói chung thì .. cũng không khó lắm:D

P/S: Đã sửa tên file theo đúng đề bài :D

[m2mpro]

Anh invicinble có đọc cái Ví dụ của dãy "tốt" chưa:
INPUT
7
3 3 3 3 3 3 3
OUTPUT
0

Còn bài 3 thì for 3 vòng là ra, trong đó
for vòng đầu là hàng
For vong tiếp là cột
FOr vòng cuối là chiều dài dài nhất mà ma trận vuông có thể nhận được ( xét theo cái nào nhỏ hơn trong hàng và cột );
Đây là bài giải của mình :

Program tap_hop_tot;
Uses crt;
Const
inp = 'thtot.inp';
out = 'thtot.out';
Type
mang = array [ 1..100 ] of integer;
Var
n:integer;
a:mang;
f:text;

Procedure readinp( var n:integer);
Var i:integer;
Begin
i:=1;
Assign(f,inp);
Reset(f);
Read(f,n);
While not eof(f) do
Begin
Read(f,a[i]);
Inc(i);
End;
End;

Procedure print(i:integer);
Begin
Assign(f,out);
Rewrite(f);
Write(f,i);
Close(f);
End;

Function checklon(k:integer):integer;
Var i,s:integer;
Begin
s:=0;
For i:=1 to n do
if a[i]>k then s:=s+1;
checklon:=s;
End;

Function checknho(k:integer):integer;
Var i,s:integer;
Begin
s:=0;
For i:=1 to n do
if a[i]<k then s:=s+1;
checknho:=s;
End;

Function nho(k:integer):boolean;
Var i:integer;
Begin
nho:=true;
For i:=1 to n do
if a[i]<k then exit;
nho:=false;
End;

Procedure check;
var i:integer;
begin
For i:=1 to n do
begin
if (checklon(i)=checknho(i)) and (nho(i)) then
begin
print(1);
exit;
end;
end;
print(0);
End;

BEGIN
readinp(n);
check;
END.


Program so_thua;
uses crt;
Const
inp = 'sothua.inp';
out = 'sothua.out';
Var
n:integer;
f:text;

Procedure readinp(var n:integer);
Begin
Assign(f,inp);
Reset(f);
read(f,n);
Close(f);
End;

Procedure print(k:string);
Begin
Assign(f,out);
Rewrite(f);
write(f,k);
Close(f);
End;

Function check(k:integer):boolean;
Var i,s:integer;
Begin
s:=0;
For i:=1 to k-1 do
if k mod i = 0 then s:=s+i;
If s>k then check:=true else check:=false;
End;

Procedure run;
Var i:integer;s:string;
Begin
i:=n;
Repeat
if check(i) then
begin
str(i,s);
print(s);
exit;
end;
i:=i+1;
until i>10000;
print('Khong tim thay');
End;

BEGIN
readinp(n);
run;
END.



Program lo_hong;
Uses crt;
Const
inp = 'lohong.inp';
out = 'lohong.out';
Type
matrix = array [1..100,1..100] of boolean;
Var
a:matrix;
m,n:integer;
f:text;

Procedure readinp(var m,n:integer);
Var i,j:integer;
Begin
Fillchar(a,sizeof(a),true);
Assign(f,inp);
Reset(f);
Readln(f,m,n);
Readln(f);
While not seekeof(f) do
begin
read(f,i,j);
a[i,j]:=false;
end;
End;

Procedure print(k:integeR);
Begin
Assign(f,out);
Rewrite(f);
Write(f,k);
Close(f);
End;

Function check(x,y,k:integer):boolean;
Var i,j:integer;
Begin
check:=false;
For i:=x to x+k-1 do
For j:=y to y+k-1 do
if a[i,j]=false then exit;
check:=true;
End;

Function tchuvi(k:integer):integer;
Begin
tchuvi:=k*4;
End;

Procedure run;
Var i,j,k,min,max:integer;
Begin
If m<=n then min:=m else min:=n;
max:=0;
For i:=1 to m do
For j:=1 to n do
For k:=1 to min do
If (check(i,j,k)) and (k>=max) then max:=k;
print(tchuvi(max));
End;

Procedure inmatrix;
Var i,j:integer;
Begin
FOr i:=1 to m do
begin
For j:=1 to n do
write(a[i,j]:7);
writeln;
end;
End;

BEGIN
clrscr;
readinp(m,n);
run;
inmatrix;
readln;
END.

Mọi người xem xem có sai chỗ nào không :D

[m2mpro]

Đã sửa lại câu: Số thừa : Tìm số nhỏ nhất không nhỏ hơn N;

[mr_invincible]

Anh invicinble có đọc cái Ví dụ của dãy "tốt" chưa:
INPUT
7
3 3 3 3 3 3 3
OUTPUT
0


Ý của tôi là loại các phần tử giống nhau, chỉ giữ lại 1
Như vậy sau khi loại dãy trên chỉ còn số 3 ->vẫn đúng

[amida]

Năm ngoái tớ làm cả 3/3 chưa đầy 1h đồng hồ, nhưng mất thên gần 1h nữa để tối ưu và điều chỉnh toàn bộ. Tuy nhiên tớ chỉ đc giải 3 bởi vì bài cuối đề bảo tính chu vi thì tớ ẩu tớ tính diện tính, tất cả chỉ là do con số 4 đánh lừa (Chu vi và diện tích của 1 hình vuông cạnh 4 thì bằng nhau = 16) :D Sai 1 bài 7đ mà đc giải 3 là mừng hết lớn. Nhớ lại vẫn thấy vớ vẩn nhưng vui :lol:

Đề TP năm ngoái đúng là quá dễ :)

[m2mpro]

đề bảo tính chu vi thì tớ ẩu tớ tính diện tính, tất cả chỉ là do con số 4 đánh lừa (Chu vi và diện tích của 1 hình vuông cạnh 4 thì bằng nhau = 16) :D

Tính diện tích: 4*4=16, 5*4=20 :D a*4=chuvi
Vậy bài của em cũng sai luôn :D, ý tưởng lớn gặp nhau :D

[phuclun]

Phải loại bỏ các phần tử bằng nhau trước rồi mới có thể làm vậy chứ

sao lại phải loại bỏ các thành phần bằng nhau,nếu loại bỏ thì có khả năng kết quả ra sai.

[m2mpro]

Ý của tôi là loại các phần tử giống nhau, chỉ giữ lại 1
Như vậy sau khi loại dãy trên chỉ còn số 3 ->vẫn đúng

Trường hợp này:
3 3 4 5 6
Loại các phần tử bằng nhau: 3 4 5 6 => Sai

[phuclun]

Trường hợp này:
3 3 4 5 6
Loại các phần tử bằng nhau: 3 4 5 6 => Sai

VD cuả m2mpro khi xoá và ko xoá đều là sai ,VD này khi chưa xoá là đúng ,khi xoá
là sai nè
1 1 2 3 4 5 5 5 6:đúng
Sau khi xoá:1 2 3 4 5 6-->sai

[mr_invincible]

Có lý. Vậy mình làm sai rồi :D, đi thi thê này thì chết