Đội ôn thi tin học trẻ không chuyên năm 2012

[cuong276]

Thuật toán đúng hay không có quan trọng đâu.
Chỉ cần text số sai cái là bị trừ điểm chứ không đùa đâu
Cần text đúng mọi trường hợp thì khi đó mới xem thử thuật toán có tối ưu hay không.
(Kinh nghiệm thi cử của mình)

 

[tmb12]

Thuật toán đúng hay không có quan trọng đâu.
Chỉ cần text số sai cái là bị trừ điểm chứ không đùa đâu
Cần text đúng mọi trường hợp thì khi đó mới xem thử thuật toán có tối ưu hay không.
(Kinh nghiệm thi cử của mình)

Vậy mình cứ viết code lộn xộn sao cũng được miễn chương trình chạy tốt trong mọi trường hợp là đậu à?

 

[cuong276]

Vậy mình cứ viết code lộn xộn sao cũng được miễn chương trình chạy tốt trong mọi trường hợp là đậu à?

Code lộn xộn thì chẳng bao giờ làm nổi bài đâu bạn à.
Phải xác định hướng đi cho bài làm đã rồi mới code
Sau khi chạy ngon rồi thì mới nhìn đến thuật toán
Xem thử thuật toán đã tối ưu hay chưa.
Giá như mình lĩnh ngộ được những điều này sớm thì hay

 

[mikelhpdatke]

Code lộn xộn thì chẳng bao giờ làm nổi bài đâu bạn à.
Phải xác định hướng đi cho bài làm đã rồi mới code
Sau khi chạy ngon rồi thì mới nhìn đến thuật toán
Xem thử thuật toán đã tối ưu hay chưa.
Giá như mình lĩnh ngộ được những điều này sớm thì hay

Đi thi những kỳ thi lớn, thuật toán mà sai thì ăn gạch. Nhưng mà nếu bí quá thì làm thuật đơn giản cũng ăn vài test.

 

[thiennu274]

Mấy bạn xem dùm mình cái code chạy bài dãy con chung dài nhất này. Sửa giúp mình, có một vài text thử nó chưa tối ưu lắm

type mang=array[1..100] of integer;
var a,b:array[1..100] of integer; t:array[0..100,0..100] of integer;
i,j,maxa,maxb:integer;

function max(a,b:integer):integer;
begin
if a>b then max:=a
else max:=b;
end;
begin
write('mang a co bao nhiu so: ');
readln(maxa);
for i:= 1 to maxa do
begin
write('nhap so thu ', i,' : ');
readln(a);
end;
write('mang b co bn so: ');
readln(maxb);
for i:= 1 to maxb do
begin
write('nhap so thu ', i,' : ');
readln(b);
end;
for i:= 0 to maxa do t[i,0]:=0;
for j:= 0 to maxb do t[0,j]:=0;
for i:= 1 to maxa do
for j:=1 to maxb do
if a=b[j] then t[i,j]:=t[i-1,j-1]+1 else t[i,j]:=max(t[i-1,j],t[i,j-1]);
i:=maxa;j:=maxb;
writeln('day con chung co do dai la: ',t[maxa,maxb]);
while (i>0) and (j>0) do
if a=b[j] then
begin
write(a:3);
i:=i-1;j:=j-1;
end
else
if t[i,j]=t[i,j-1] then j:=j-1 else
if t[i,j]=t[i-1,j] then i:=i-1;
readln;
end.

Làm piếng viết procedure, chơi trong chương trình chính lun

 

[mikelhpdatke]

Đọc qua cái ct cũng ko thấy j sai :-?, lần sau post code lên trình bay cẩn thận tý, nhìn và sửa cũng dễ. Mà có test nào nói rõ ra thì mọi người mới sửa được chớ 8-X

 

[starlove_maknae_kyuhyun]

sr các bạn vì mình quay lại box lập trình hơi trễ ! thành thật xin lỗi nhé ! mình có bận một thời gian !

Bài mới nhé :
bài 1: viết chương trình bài toán tìm độ dài dãy con nhiều số nhất có tổng đúng bằng k
file.INP :

n k
n dãy con

Đề ngắn gọn vậy thôi các bạn làm đi nhé !

 

[mikelhpdatke]

F[i,j] là độ dài dãy con dài nhất trong i phần tử đầu có tổng chia hết cho j.
KQ bài toán là F[n,k].
Xét đến số thứ i.
F[i,j]:=Max(F[i-1,j],F[i-1,j-A])+1;

 

[mikelhpdatke]

Có ai làm được bài này chưa, hay mình post thuật + code luôn :-?

 

[11thanhkhoeo]

Code lộn xộn thì chẳng bao giờ làm nổi bài đâu bạn à.
Phải xác định hướng đi cho bài làm đã rồi mới code
Sau khi chạy ngon rồi thì mới nhìn đến thuật toán
Xem thử thuật toán đã tối ưu hay chưa.
Giá như mình lĩnh ngộ được những điều này sớm thì hay

Chú nói sai rồi
+ Không nghĩ thuật toán thì sao code được. Có lẽ chú không hiểu thuật toán là gì. Cái hướng đi mà chú nói chính là thuật toán

Thân

 

[11thanhkhoeo]

Cho một mảng vuông kích thước N x N (N<100). Các ô ghi các số 0 hoặc 1. Tìm đường đi robot từ góc trái trên tới góc phải dưới theo nguyên tắc chỉ được dịch chuyển sang phải & xuống dưới sao cho các số trên đường đi tạo thành số hệ nhị phân có giá trị lớn nhất.
Dữ liệu vào là file robot.inp: dòng 1 ghi giá trị N. N dòng tiếp theo trên mỗi dòng N ghi 0 hoặc 1.
Ghi vào file robot.out (xuất số thập phân)
VD: 5
1 0 1 1 0
0 0 1 0 1
0 0 1 0 1
1 0 0 1 1
1 1 0 1 0
Số nhị phân lớn nhất: 101110110

 

[mikelhpdatke]

F[i,j] là giá trị dãy nhị phân lớn nhất khi đi từ (1,1) đến (i,j).
Khi đó
F[i,j]:=Max(F[i,j-1],F[i-1,j])+A[i,j]. Nên xử lý xâu cho bài này

 

[cuong276]

Bài này tương tự như cái bài tìm đường đi có tổng lớn nhất mà tớ đã làm
Tớ nghĩ cộng xâu vào rồi đổi ra số thập phân rồi so sánh thôi
Đường nào có số lớn hơn thì ta đi
Hướng làm là vậy đó
Có sai chỗ nào không

 

[mikelhpdatke]

Bài này tương tự như cái bài tìm đường đi có tổng lớn nhất mà tớ đã làm
Tớ nghĩ cộng xâu vào rồi đổi ra số thập phân rồi so sánh thôi
Đường nào có số lớn hơn thì ta đi
Hướng làm là vậy đó
Có sai chỗ nào không

Vấn đề so sánh ý, bạn cứ so sánh trực tiếp thôi. VD:

a:='100111';
b:='100000';
If a>b then writeln(a);

CT sẽ viết a.

 

[mikelhpdatke]

Box dạo này vắng tay như chùa bà đanh 8-X

Không ai làm bài này thì để mình làm vậy )
Gọi
F[i,j,k] là giá trị lớn nhất khi đi i quãng đường đầu, với giới hạn là j và số lần đi là k.
Khi đó
Nếu j-QD(i)<0 then F[i,j,k]:=F[i-1,j,k];
Else
F[i,j,k]:=Max(F[i-1,j,k],F[i-1,j-i*2,k-1]+W);
Cơ sở, cứ gán mảng F=0

 

[mikelhpdatke]

Bài này vẫn chưa nghĩ ra :-?
Bài 1: Đĩa hát
Trên thị trường hiện đang có bán N đĩa hát. Đĩa hát thứ i có chứa các bài hát x1, x2, ..., xk và giá là ti.
Yêu cầu: Hãy tìm cách mua các đĩa hát sáo cho có đủ các bài hát từ 1 đến m và tổng tiền là ít nhất.

Dữ liệu: Cho trong file DISK.INP:
- Dòng đầu ghi 2 số n, m (0< n  30, 0<m 200).
- Dòng thứ i trong n dòng sau: ghi thông tin về đĩa hát thứ i: Số đầu là giá tiền, các số tiếp theo là các bài hát của đĩa đó (mỗi đĩa không quá 15 bài hát).
Kết quả: Ghi ra file DISK.OUT có 2 dòng: Dòng đầu ghi số tiền cần thiết; dòng sau ghi số hiệu của các đĩa cần mua.
Ví dụ:
DISK.INP
5 4
5 1 2 3 5
6 2 4 5
5 1 3 4
1 4
4 2 4
Disk.out
6
1 4

 

[11thanhkhoeo]

Bài này duyệt vét cạn và kiểm tra thôi mà.

Nếu tông lớn hơn tông cũ thì loại luôn

 

[mikelhpdatke]

Cách của anh e nghĩ ra lâu rồi ). Sao không QHĐ được bài này a nhể? E thấy khó ở chỗ mấy cái bài hát

 

[starlove_maknae_kyuhyun]

Bài mời nhé :


Cái ảnh này hơi mơ nhưng phóng lên có thể đọc được :

 

[starlove_maknae_kyuhyun]

bài 2: