Đề thi Tin học không chuyên THCS Tp

[Samir Duran]

Em xin hỏi các anh thuật giải bài toán "Pháo binh" trong kỳ thi vừa rồi ?
<Tóm tắt> Cho trước ma trận m x n ; (m,n <= 100) các phần th\ử chỉ chứa giá trị 0 và 1 [1 tượng trưng cho ô đó có 1 tên địch đang ẩn núp] . Pháo cannon của ta có bán kính sát thương k [k in [1..5]] và khi bắn ờ vị trí [ti,tj] thì toàn bộ tên địch ở trong ma phương tâm [ti,tj] (kể cả đưởng chéo , ngang và dọc , nói cách khác là hình vuông đỉnh trên trái là (ti-k,tj -k) và đỉnh dưới phải là (ti+k,tj+k) ) sẽ bị tiêu diệt. Vậy hãy lập trình tìm tọa độ vị trí pháo kích sao cho tiêu diệt toàn bộ tên địch với lượng đạn tối thiểu ?
Vd : nhập vào :
0 1 1 1 0
1 0 1 1 0
1 1 1 0 0
k = 1 ; tức là diện tích sát thương là ma phương 9 ô .
=> phải bắn ít nhật 2 phát , ở [2,2] và [2,3] .
Em rớt là tại vì làm giải thuật sai bài này (tức quá !!!!) Mong mọi người giúp đỡ !

[ky_si_khong_dau]

bạn thử dùng cách này xem nha. Ở đây mình chỉ nói thuật toán mà thôi, còn code cụ thể thì tự viết ra mới sướng. Mình cũng thi Tin hoc khong chuyên nhiều rồi nên cũng bị tức nhiều lắm

Chúng ta xây dựng một thủ tục xoá mảng với diện thích xoá la S , s tính theo k như đề bài. Thực chất là biến s ô trong ma trận thành a[i,j]:=0;

Lần lượt duyệt ma trận từ phải sang trái, tìm vị trí đầu tiên mà ta có thể bắn (xoá) được nhiều quân địch nhất và phải bao hàm cả quân địch tìm thấy đầu tiên trong qua trình duyệt của ta. Như ở ví dụ thì nó là ô [2,2] vì khi ta duyệt ma trận từ trái sang thì ô [2,2] là ô mà khi bắn ta vừa bắn được quân địch đầu tiên [1,2] và nhiều quân địch khác nhất. Ta xoá ngay trên ma trận gộc rồi continue lăp lặi như trên cho tới khi không còn quân đich nào.

việc duyệt từ trái sang phải và việc bắn bao gồm cả quân địch đầu tiên sẽ lại bỏ được trường hợp tìm nhầm vi du :
0 1 1 1 1 0 0
0 1 1 1 1 1 0
1 0 1 1 1 0 0
k=1;
trường hợp nhầm sẽ tìm ô có thể bắn được nhiều nhất , là ô 2,4 nêu bắn vào ô này thì ta phải bắn thêm 2 phát nữa là 2,2 và 2,6.
Nhưng nêu duyệt từ trái sang phải và tìm bao hàm quân địch đầu tiên thì ta sẽ có kết quả tối ưu là
[2,2] và [2,5]

Mình mới nghĩ ra thuật toán như vậy , không biết có ai có thuật toán hay hơn hay phat hiện lỗ hổng nào xin chỉ cho mình biết. Thanks !

[Teak]

Vì không có giấy nháp gì cả nên mình chỉ nói vậy thôi, nếu có gì sai thì sửa giúp mình nghe. Thanks !
Mình nói cách duyệt nè :
VD k=1
Bạn xét xem thử có 2 số 1 nào mà abs(i1-i2)>2 hoặc abs(j1-j2)>2 không. Nếu có thì bắt buộc phải inc(so_pháo). Nếu tìm thêm được 1 số abs(i1-i3) hoặc abs(i1-i3)>2 thì ta sẽ xet(i2,j2và i3,j3), nếu true thì inc(sophao). Như vậy sẽ dễ dành tìm được vị trí đặt. Ok ?
Hix, tui cũng rớt tin không chuyên THCS ở Đà Nẵng. Tức lắm ! Hix ! Đồng cảnh ngộ ! Liên hệ tui nghe : Y!M :mai_zo_mai_zo

[beckvn]

Em cũng thi cái này, làm thuật toán này và sai thuật toán này, em xin mạo muộn đưa ra phản chứng do em tự nghĩ ra khi bình tĩnh suy nghĩ
ta có ma trận sau
0 0 1 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 1 0 0
Với k = 1, nếu như anh nói, nó sẽ bắn ở ô [3,3] 1 phát, bắn ở ô [1,3], [5,3] mỗi ô 1 phát ==> 3 quả
Nhưng nhìn kĩ lại, ta thấy chỉ cần bắn ở ô [2,3] và ô [4,3] mỗi ô 1 phát là okay ==> 2 phát
Em thấy bài này nên giải theo cách vét cạn kết hợp xét nhánh thiển cận:
Bước 1: tìm số quả pháo lớn nhất có thể để có thể nổ hết toàn bộ ma trận ( tòan bộ nhé), ở ví dụ với n=4,m=5 thì số quả báo tổng là tongPhao = 4
Bước 2: for sophao = 1 to => 4 do
_ Dùng vét cạn cho từng số quả pháo
_ Vd sophao = 1 , ta sẽ thử từng vị trí [i,j], cho nổ từng vị trí xem có thể hết dc ko
_ Ở mỗi lần for, lưu lại maxphao là số fáo nổ lớn nhất có thể nổ với biến sophao, xét xem có thể nổ hết ma trận ko, nếu có thì in ra vị trí, đó là nghiệm tối ưu
_ Ở lần for kế, xét xem số pháo có thể nổ có lớn lơn biến maxphao ko, nếu ko thì nhảnh qua for kế, còn ko thì tiến hành nổ, đếm, đo.....
Bước 3: tạo tập tin data và debug :d ( <=== Quan trong nhất đó )

[Miraculous]

Mình thấy bài này gần giống với bài đánh bomb gì đó. Đại khái là trên chiến trường có một số chiếc xe tăng, nhiệm vụ của ta là phải đưa ra giải pháp đánh bomb sao cho số lượng bomb phải sử dụng là ít nhất. Một quả bomb có tầm sát thương là một ma trận kích thước 3*3 mà nơi thả bomb là tâm, cũng giống như bài trên với k=1 đó.
Bài này chỉ khác bài trên ở chỗ chúng ta duyệt các ma trận có kích thước 3*3
thay vì (2k+1)*(2k+1).
Mình thấy bài nãy cũng đơn giản thôi. Cỡ thằng Teak làm bài này 20ph là xong.
Để ở TP hay thiệt, đề ở Đà Nẵng ra dở quá, ai cũng nói hêt, nhìn vào là không muốn làm rồi.

[bingbongsong]

mod sao còn chưa ban mấy tay này nhỉ?:(

[thanhhuynh282]

cho cái đề thi hsg THCS mấy anh gửi về cho em theo mail nguyenthanhhuynh_2821995@yahoo.com

[=========> Bổ sung bài viết <=========]

khó quá đi cưng !!!!!!!