View Full Version : [DIS] Một bài toán 30-4
Hì bài này có Zero đã làm cách đây khá lâu tình cờ mấy hôm trước đọc lại nó trong quyển tuyển tập đề 30-4 và xem cách giải của nó :D chương trình chạy rất chậm với n=m = 100.
Cho một khu đất có kích thước m*n ô, mỗi ô có độ cao xđ (< 10^12) có một trận mưa đủ lớn đã đổ xuống mảnh đât làm lấp đầy các ô trũng.
bài toán đặt ra là cho bản đồ vùng đất cùng với độ cao hãy tính xem có bao nhiêu nước đọng lại sau trận mưa?
Nước không lọt qua các khe mà chỉ chảy được đến các ô chung cạnh có chiểu cao nhỏ hơn
vd :
0 9 0
9 1 9
0 8 0
ờ đây nước chứa ở ô giữa (có độ cao 1) và lượng nước là 7
Junior IT
11-11-2002, 21:52
bài này hình như Zero từng nói voi skywalker phải ko? Mình cũng từng giải bài này rồi, chương trình khá chậm khi số càng lớn, hôm khác mình post lên cho bạn nhe'
skywalker
12-11-2002, 12:11
đúng rồi, hôm trước anh zero đã đưa lên dd rồi, lúc đó vẫn chưa ai giải được, kể cả anh zero :D
còn bây giờ cách giải là sao vậy, anh zero chỉ cho em với, còn source thi ko cần
del_gate
13-11-2002, 07:37
Theo em nghĩ chúng ta chỉ cần 2 vòng for lồng nhau là xong mà.
for i:=1 to m do
for j:=1 to n do
if a[i,j]<min(a[i+1,j],a[i-1,j],a[i,j+1],a[i,j-1])then
s:=s+min(a[i+1,j],a[i-1,j],a[i,j+1],a[i,j-1]);
Đấy chỉ là ý kiến cúa em thôi .Nếu sai thì mong các bạn góp ý .Cảm ơn nhiều
Bạn Zero hãy cho nhiều mẫu hơn đi ,mình vừa nghĩ ra một cách có thể nhanh hơn nhưng chư kiểm chứng .
Yeah
Bài này đã đố skywalker nhưng mình có nói lúc đó là mình không làm được đâu ? lúc đó ngon rồi.
To Junior IT : Bài này của Zero làm nhanh lắm : có lẽ không mất tí nào.
To Quang Vu Ok
9 9 9 9 9
9 0 0 0 9
9 0 1 0 9
9 1 0 1 9
9 9 8 9 9
S = 69 (hy vọng đúng)
7 7 7 7 7 7 7
7 0 0 0 0 0 7
7 0 9 9 9 0 7
7 0 9 0 9 0 7
7 0 9 9 9 0 7
7 0 0 0 0 0 7
7 7 7 7 7 7 7
S = 121
Thế nào ?
Mấy hôm nữa Zero sẽ post bài của cuộc thi chọn đôịi tuyển vòng I của tổng hợp rất trâu với người cao điểm nhất là 60/200 !! Người thấp nhất đậu là 5/200.
To Skywalker : cách giải ? ok
Đây là cách giải thô với độ phức tạp O(m*n*log(m*n)) (thực ra thì bé hơn nhiều)
Đầu tiên bạn bao vòng quanh khu đất đó đưa tất cả các ô ở ngoài cùng vào một cái mảng một chiều (Q)
Sau đó bạn đi từ ô có độ cao thấp nhất đi vào sau đó lan ra 4 ô chung cạnh nếu gặp ô nào có độ cao + lượng nước thấp hơn nó và chưa bị đưa vào Q thì đổ vào ô này lượng nước mới sao cho = độ cao + lượng nước của nó rồi cho ô này vào trong Q, rồi bạn lại tìm trong Q ô thấp nhất để di cứ thế.
Tất nhiên có thể cải tiến để cho cách này nhanh hơn nhưng không đáng kể.
Đây là VD :
9 9 9 9
8 1 0 9
9 0 0 9
9 9 9 9
Q ban đầu là 9 9 9 9 9 9 9 9 9 9 9 8
Ô thấp nhất là 8
Đi vào ==> cho ô 1 thêm 7 nước, bây giờ nước của ô 1 là 7
Cho nó vào Q
9 9 9 9 9 9 9 9 9 8
Lại đi tiếp từ ô này ==> sẽ đi hết các ô 0 ở bên trong
bây giờ các ô có độ cao + nước là
9 9 9 9
8 8 8 9
9 8 8 9
9 9 9 9
Sau đó xét đến các ô có độ cao 9 còn lại trong Q thì không đổ thêm nước vào đâu được nữa nên Stop
Có thể mình còn nhầm lẫn chỗ nào đó nhưng tư tưởng thì như dậy đó bạn thử coi .
Cái đĩa có lẽ bạn phải chờ mình thêm mấy hôm nữa vì dạo này mình bận thi quá mà cái đĩa cũ có lỗi chưa đi làm lại đước.
skywalker
14-11-2002, 19:24
đúng rồi đó, em cũng nghĩ ra cách đó và đã làm thử :D
đây là source còn nóng hổi, anh chị nào tốt bụng test giùm em coi còn lủng chỗ nào ko
(file txt, phải đổi lại là .pas mới xem được nha)
phucdeptrai
16-11-2002, 17:11
Các bạn ơi, bài đó dễ lắm. Các bạn hãy dùng đệ quy đó.
Đệ quy ? cách của bạn có độ phức tạp là bao nhiêu ?
Nói thiệt nha Skywalker cách của bạn trâu quá! Riêng việc đặt mảmg dau với giá trị false là đã quá chậm rồi chưa kể đến các công đoạn khác Ok ? độ phức tạp về mặt lý thuyết đã là O(n^4) rồi.
Cách của bạn hình như không giống cách của mình (?) nó hơi giống cách giải mẫu của quyển đề thi 30-4 không biết có phải không ? nếu không phải cho mình xin lỗi nhé.
skywalker
18-11-2002, 05:42
em chỉ nghe được một lời gợi ý là hãy làm như mình đổ nước thật xuống vùng đất đó, nghĩa là nước sẽ chảy vào chỗ thấp nhất trước, rồi từ đó tới chỗ thấp nhì ... , em nghĩ cách của anh zero cũng cùng tư tường đó thôi, nhưng còn cài thì mỗi người cài một cách, giờ thì em phải xin source của anh zero rồi, anh gừi lên sớm nhe :D
em nghĩ, về tư tưởng thì ai cũng giống ai(tức là coi nước chảy từ trên cao xuống) chỉ quan trọng là mình cài đặt thế nào thôi. em xin viết thuật giải tóm tắt cho mọi người dễ hiểu:
chuyển bài toán về đồ thị có m*n đỉnh, trong đó các cung của đồ thị nối hai đỉnh liên tiếp cùng hàng và hai đỉnh liên tiếp cùng cột,OK?
- như vậy mỗi đỉnh của đồ thị đại diện cho một cột trong ma trận, và cạnh nối giữa hai đỉnh nghĩa là nước có thể chảy từ đỉnh nọ sang đỉnh kia...
- tiếp tục, duyệt từ đầu tới cuối ma trận và xét xem có hai đỉnh kề nhau có độ cao bằng nhau thì gộp chúng chung lại thành một điểm (gộp chung lại bằng cách chuyển tất cả các đỉnh kề với đỉnh i thì chuyển sang cho kề với đỉnh j, và b[i]:=b[i]+1=1+1 - b[i] chính là độ "chất chồng " của đỉnh)...
- đánh dấu các đỉnh bao ở phía ngoài lại
- xuất phát từ một đỉnh(không phải là đỉnh ngoài đâu nhé),có hai trường hợp xảy ra:
+ nếu nó thấp hơn tất cả các đỉnh kề với nó ==> chọn đỉnh thấp nhất kề với nó, cho i tăng lên bằng đỉnh kề j; còn
nướcđọng:=nướcđọng + b[i]*(độcao j - độ cao i);
gộp chung điểm i và điểm j lại làm một và xét tiếp ....
+ nếu tồn tại một đỉnh kề với i và thấp hơn i (gs j thấp hơn i)==>
trượt xuống j và xét....
*** em post như vậy các bác hiểu rồi chứ......
hic..hic...nếu có gì giống của tên sky thì các bác thông cảm nhé, vì thực sự em chưa đọc được bài của tên ấy ( cái máy nó hơi hâm hâm ).......đó mới chỉ là thuật giải, còn em vẫn chưa cài đặt thử, bác nào có đủ độ "kiên nhẫn" để đọc thì cho ý kiến hộ em nhé/
quả là vô cùng thất vọng!!!!
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.