Đề thi HSG Tin học tỉnh Nam Đinh 2009-2010

[nguyendangvan]

đây là đề thi học sinh giỏi minh sưu tập được nhưng chưa biết cách giải mong các thành viên giúp đỡ và chỉ rõ thuật toán áp dụng để giải mỗi bài, thanhk[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Bài 1: (6 điểm) Mua hàng
Có n người xếp thành hàng theo thứ tự để mua hàng. Thòi gian người bán hàng phục vụ cho người thứ i là ti đơn vị thời gian. Hãy tìm thời gian mà người thứ k phải chờ để mua hàng.
Dữ liệu: Vào từ tệp văn bản MH.INP
- Dòng 1: chứa 2 số n, j nguyên dương (1≤k≤n≤100);
- Dòng 2: chứa n số t1, t2,...tn ( Các giá trị ti đều nguyên dương va nhỏ hơn 1000).
Kết qủa : Đưa ra tệp văn bản MH.OUT chứa duy nhất số C thở mãn yêu cầu của dữ liệu vào.
Ví dụ:

<div style="text-align: center">MH.INP​

</div>

<div style="text-align: center">MH.OUT​

</div> 5 3
1 3 2 4 1
4




Bài 2: (7 điểm) Giả thuyết của GÔN – BẮC
Giả thuyết của GÔN – BẮC ( Cho đến nay vẫn chưa bị bác bỏ, nhưng cũng chưa chứng minh được đầy đủ) nói rằng mỗi số chẵn n lớn hơn 2 là tổng của hai số nguyên tố.
Yêu cầu: Cho số n chẵn lớn hơn 2, hãy xác định số lượng các cặp số nguyên tố có tổng bằng số n.
Kết quả : Đưa ra tệp văn bản GONBAC.OUT chứa duy nhất một số theo yêu cầu của bài.
Ví dụ :

<div style="text-align: center">GONBAC.INP​

</div>

<div style="text-align: center">GONBAC.OUT​

</div> 16
2


Bài 3: (7 điểm) Bố trí xe
Vưa qua kì thi máy tính cầm tay cấp quốc gia được tổ chức tại nam Định, Ban tổ chức đã bố trí xe ô tô để đưa mỗi đoàn học sinh cảu mỗi tỉnh đi tham quan các địa điểm khác nhau. Có tất cả n đoàn hoạc sinh đánh số từ 1 đên n, đoàn thứ I cần đi tới địa điểm cách nơi ở là di đơn vị( coi như di là khoảng cách tình theo chiều cả đi lẫn về). có m chiếc xe ô tô sử dụng được đánh số từ 1 đến m (m≥n), có thể dùng để phục vụ đưa các đoàn đi tham quan. Được biết xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích xăng trên một đơn vị độ dài. Hãy lựa chọn và bố trí n xe, mỗi xe chi phục vụ một đoàn theo yêu cầu sao cho tổng thể tích xăng cần thiết là ít nhất.
Dữ liệu: Vào từ tệp văn bản XE.INP có cấu trúc:
- Dòng 1: Chứa 2 số nguyên dương n, m (1≤n≤m≤200);
- Dòng 2 chứa n số d1, d2,…dn;
- Dòng 3: Chứa m số v1, v2,…vm.( Các giá trị di, vj đều nguyên dương và không qúa 32000).
Kết quả: Đưa ra tệp văn bản XE.OUP, chứa 2 dòng
- Dòng 1: Chứa số lượng xăng cần ít nhất theo yêu cầu;
- Dòng 2: chứa n số x1, x2,…xn thể hiện đoàn thứ I được bố trí đi xe xi;
Ví dụ:

<div style="text-align: center">XE.INP​

</div>

<div style="text-align: center">XE.OUT​

</div> 3 5
3 8 5
3 2 4 1 5
27
1 4 2



Chú ý:
- Tệp chương trình Bài 1 đặt tên là: MH.PAS
- Tệp chương trình Bài 2 đặt tên là: GONBAC.PAS
- Tệp chương trình Bài 3 đặt tên là: XE.PAS
- Trong các tệp dữ liệu vào hoạc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách.

[vietkanpy]

Bạn ở trường nào của Nam Định thế? Mình cũng ở Nam Định nhưng chưa từng gặp loại đề nào thế này, chắc của lớp 8 mới học Pascal hả?
Bài 1: tính tổng T từ 1-> k là ra kết quả.
Bài 2: lập mảng chứa tất cả các số nguyên tố < n. Dựa vào mảng đã lập được, với mỗi vị trí thứ i, tìm vị trí j>i sao cho tổng = n. Nếu tìm được thì tăng biến đếm.
Bài 3: xếp tăng V, xếp giảm D. Xe thứ i thì đi đoàn D tiêu thụ V. -> Xong
Bài 3 vẽ ra giấy là thấy ngay cách làm thôi mà.

[thanhtungbooking]

bạn có thể giải cụ thể các bài được không?

[linhti0209]

Vì có chút việc bận nên có lẽ mình chưa có code ngay cho bạn. Mình sẽ sớm code và post cho bạn. Chắc bạn học ở TDN hả? Vì mình thấy có 1 bài mình đã được thày cho làm rồi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[ledinh121189]

Bài 1 của bạn đây, mình làm theo đúng yêu cầu đề bài, bạn đọc code sẽ hiểu[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

const inp='mh.inp';
out='mh.out';
var fi,fo:text;
i,n,k,tong,so:longint;
begin
assign(fi,inp);reset(fi);
assign(fo,out);rewrite(fo);
readln(fi,n,k);
tong:=0;so:=0;
for i:=1 to k do
begin
tong:=tong+so;
read(fi,so);
end;
write(fo,tong);
close(fi);close(fo);
end.

Bài 2: Mình làm vội bài này với thuật toán cơ bản, chưa tối ưu, nếu bạn có thể tối ưu hơn ở bước kiểm tra tính nguyên tố thì tối ưu lại code nhé.

const inp='gonbac.inp';
out='gonbac.out';
var fi,fo:text;
i,n,kq:longint;
procedure nhap;
begin
assign(fi,inp);reset(fi);
readln(fi,n);
close(fi);
end;
function nt(x:longint):boolean;
var ok:boolean;
i1,du:longint;
begin
ok:=true;
du:=x mod 6;
if (x>6) and (du in [0,2,3,6]) then ok:=false;
if ok then
for i1:=2 to trunc(sqrt(x)) do if x mod i1=0 then
begin
ok:=false;
break;
end;
nt:=ok;
end;
procedure xuli;
begin
kq:=0;
if n=4 then kq:=1
else
begin
i:=1;
repeat
i:=i+2;
if nt(i) and (n-i>=i) and nt(n-i) then kq:=kq+1;
until i>(n-2)div 2;
end;
end;
procedure xuat;
begin
assign(fo,out);rewrite(fo);
write(fo,kq);
close(fo);
end;
begin
nhap;
xuli;
xuat;
end.

Bài 3:

const inp='xe.inp';
out='xe.out';
var fi,fo:text;
sttd,sttv,d,v:array[1..200]of integer;
i,j,tg,vt,tong,n,m:integer;
procedure nhap;
begin
assign(fi,inp);reset(fi);
readln(fi,n,m);
for i:=1 to n do
begin
read(fi,d);
sttd:=i;
end;
readln(fi);
for i:=1 to m do
begin
read(fi,v);
sttv:=i;
end;
close(fi);
end;
procedure xuli;
begin
for i:=1 to n-1 do
begin
vt:=i;
for j:=i+1 to n do if d[vt]<d[j] then vt:=j;
tg:=d[vt];d[vt]:=d;d:=tg;
tg:=sttd[vt];sttd[vt]:=sttd;sttd:=tg;
end;
for i:=1 to m-1 do
begin
vt:=i;
for j:=i+1 to m do if v[vt]>v[j] then vt:=j;
tg:=v[vt];v[vt]:=v;v:=tg;
tg:=sttv[vt];sttv[vt]:=sttv;sttv:=tg;
end;
tong:=0;
for i:=1 to n do tong:=tong+d*v;
end;
procedure xuat;
begin
assign(fo,out);rewrite(fo);
writeln(fo,tong);
for i:=1 to n do
for j:=1 to n do if sttd[j]=i then
begin
write(fo,sttv[j],' ');
break;
end;
close(fo);
end;
Begin
nhap;
xuli;
xuat;
End.

[khuvucmuabannhadat]

Bài 2: giới hạn bn vậy bạn ?

Ý tưởng của mình ( chắc nhanh hơn bạn Long)
- Tạo mạng hằng NT
- Cho vòng for chạy từ i -> k (k là vị trí mà tại đó a[k]<=n) ùi tìm kiếm nhị phân phần tử n-a
+ Nếu tìm đc : thì k:= vị trí tìm thấy - 1 , tăng biến đếm
+ Không tìm thấy thì vòng for tự động tăng i
- In biến đếm

[kitelag]

Nhanh hơn sao được chị Hằng, riêng cái khoản tạo mảng NT đã kém em rồi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

[dungmxh]

Mình đâu nói là tạo trong bài [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Vik hẳn 1 ct tạo, lấy mảng hằng đưa vào bài thôi !

[zinzin8x]

Cách này mà cho giới hạn mã nguồn là chết chắc. Nếu n chỉ tầm 100 đã có rất nhiều số nguyên tố trong khoảng 1->100 rồi. Làm cách này nghe chừng không ổn lắm

[Tuanvuong]

k bik bạn có nhầm, số nguyên tố < 100 có 26 số àhh [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]