VMUNCH - Gặm cỏ

Link Sub: http://vn.spoj.com/problems/VMUNCH/
Người Gửi: Dương Lee

• Problem:

Bessie rất yêu bãi cỏ của mình và thích thú chạy về chuồng bò vào giờ vắt sữa buổi tối.  
Bessie đã chia đồng cỏ của mình là 1 vùng hình chữ nhật thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột, đồng thời đánh dấu chỗ nào là cỏ và chỗ nào là đá. Bessie đứng ở vị trí R_b,C_b và muốn ăn cỏ theo cách của mình, từng ô vuông một và trở về chuồng ở ô 1,1 ; bên cạnh đó đường đi này phải là ngắn nhất.  
Bessie có thể đi từ 1 ô vuông sang 4 ô vuông khác kề cạnh.  
Dưới đây là một bản đồ ví dụ [với đá ('*'), cỏ ('.'), chuồng bò ('B'), và Bessie ('C') ở hàng 5, cột 6] và một bản đồ cho biết hành trình tối ưu của Bessie, đường đi được dánh dấu bằng chữ ‘m’.
Bản đồ               Đường đi tối ưu         
1 2 3 4 5 6  <-cột      1 2 3 4 5 6  <-cột       
1 B . . . * .           1 B m m m * .       
2 . . * . . .           2 . . * m m m       
3 . * * . * .           3 . * * . * m       
4 . . * * * .           4 . . * * * m       
5 * . . * . C           5 * . . * . m
Cho bản đồ, hãy tính xem có bao nhiêu ô cỏ mà Bessie sẽ ăn được trên con đường ngắn nhất trở về chuồng (tất nhiên trong chuồng không có cỏ đâu nên đừng có tính nhé)
Input
Dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C 
Dòng 2..R+1: Dòng i+1 mô tả dòng i với C ký tự (và không có dấu cách) như đã nói ở trên.

Output
Dòng 1: Một số nguyên là số ô cỏ mà Bessie ăn được trên hành trình ngắn nhất trở về chuồng.

Example:

Input

5 6
B...*.
..*...
.**.*.
..***.
*..*.C

Output:

9

• Solution:

- Các bước làm: 
+ Đọc dữ liệu (+ Tìm luôn vị trí của 'B' và 'C'). 
+ Khởi tạo liên kết: Với mỗi ô của bãi cỏ thì xét các ô kề cạnh xung quanh nó xem ô nào đi được thì tạo liên kết (v[][][]). 
+ Duyệt BFS (Áp dụng theo quy tắc thông thường của duyệt BFS) + mảng dấu vết (mark[con][con] = mark[cha][cha]+1).  
-> in ra mark [C][C];

• Code:

C++:

JAVA:

C11PAIRS - Đếm cặp

Link Sub: http://vn.spoj.com/problems/C11PAIRS/

Người Gửi: Dương Lee

• Problem:

N người đang đứng xếp hàng chờ mua vé vào buổi hòa nhạc. Mọi người đều phát chán khi phải chờ đợi, vì vậy họ nhìn quanh xem có ai quen hay không.  

Hai người A và B đứng trong hàng có thể nhìn thấy nhau nếu:  

Người A và người B đang đứng cạnh nhau. 

Giữa người A và người B, không có ai cao hơn hẳn một trong hai người. 

Hãy đếm xem có bao nhiêu cặp có thể nhìn thấy nhau trong hàng.

Input

Dòng đầu tiên chứa số nguyên dương N, là số người đang đứng trong hàng.
Mỗi dòng trong N dòng tiếp theo chứa một số nguyên là chiều cao của một người tính bằng nanomet. (Tất cả mọi người đều thấp hơn 231 nanomet).

Output

Một số nguyên duy nhất là kết quả cần tìm.

1 ≤ N ≤ 5.105

Trong 1/3 số test 1 ≤ N ≤ 5000

Example:

Input

7
2
4
1
2
2
5
1

Output:

10

• Solution:

Các cặp có thể nhìn thấy nhau là (1, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6), (6, 7).

- Ý tưởng: Sử dụng stack để loại các cặp không thể nhìn thấy được. Chú ý cách làm dưới đây chỉ 100/100 khi nộp C++ (gcc 6.3) [CPP] + Duyệt từng người một: {mỗi người có 3 thông tin: +chiều cao: height; +kiểm tra sau nó: check_behind (Sử dụng để kiểm tra xem có sau nó có con nào lớn hơn không?); +kiểm tra đoạn giốn nhau: the_same (Sử dụng để đếm xem sau nó có bao nhiêu con có cùng độ cao); } +TH1: Stack rỗng: Cho người đó vào với (chiều cao, 0 có ai sau nó, 0 có con nào bằng với nó). VD: test trên (i==1: h_i=2) push (2, 0, 0); stack []: {(2, 0, 0);} +TH2: Stack không rỗng và hight_TOP < h_i: loại những con bé hơn trong stack và count++; (Vì đã gặp con cao hơn thì các con sau sẽ không thể nhìn thấy con trước đó và hai con liên tiếp sẽ nhìn thấy nhau.) VD: test trên (i==2: h_i=4) height_TOP = 2 < 4; ->pop() ->stack rỗng. -> push (4, 0, 0). cout++; stack []: {(4, 0, 0);} +TH3: Stack không rỗng và hight_TOP > h_i: Các con sau vẫn có thể nhìn thấy nên push tiếp cùng với cập nhật chỉ số và count++ (hai con liên tiếp nhìn thấy nhau.) VD: test trên (i==3: h_i=1) height_TOP= 4 > h_i; -> push (1, 1, 0) (chec_behind=1 vì sau con 1 có con 4 lớn hơn). +TH4: Stack không rỗng và hight_TOP = h_i: trường hợp này khá đặc biệt vì các con bằng nhau liên tiếp vẫn có thể nhìn thấy nhau và vẫn có thể nhìn thấy con cao hơn sau nó. VD: 4 2 2. thì (người thứ 3 vẫn nhìn được người 2 và người 1). -> ta sẽ push vào chỉ số push (h, check_behind_TOP, the_same_TOP+1) (có nghĩa là: cho vào h, sau h có hay không có con cao hơn nó sẽ phụ thuộc vào con sau nó, sau nó có the_same+1 con cùng chiều cao với nó). Và coutn++ (liên tiếp nhìn thấy) và coun+=the_same_TOP (số con có cùng độ cao sau nó) và count++ (nếu sau nó có con cao hơn). Cuối cùng thì in ra count. ^^ Xem hình để hiểu rõ hơn.

• Code:

C++:

JAVA:

KPLANK - Bán dừa

Link Sub: http://vn.spoj.com/problems/KPLANK/

Người Gửi: Dương Lee

• Problem:

Nếu các bạn biết câu chuyện thương tâm "ăn dưa leo trả vàng" của Pirate hẳn đã phải khóc hết nước mắt khi anh ấy, vì lòng thương chim, đã bán rẻ trái dưa leo siêu bự của mình.  

Dưa leo cũng đã bị chim to lấy đi rồi, Pirate giờ chuyển sang nghề bán dừa để bù lỗ. Bất đắc dĩ thôi, vì trên đảo toàn là dừa...  

Nhưng mà bán cái gì thì đầu tiên cũng phải có biển hiệu đã. Pirate quyết định lùng sục trên đảo các mảnh ván còn sót lại của những con tàu đắm để ghép lại thành tấm biển. Cuối cùng anh cũng tìm được N tấm ván hình chữ nhật, tấm thứ i có chiều rộng là 1 đơn vị và chiều dài là ai đơn vị. Pirate dựng đứng chúng trên mặt đất và dán lại với nhau để được một mảnh ván to hơn (xem hình minh họa).

Việc cuối cùng chỉ là đem mảnh ván này đi cưa thành tấm biển thôi. Nhưng hóa ra đây lại là công việc khó khăn nhất. Pirate rất thích hình vuông và muốn tấm biển của mình càng to càng tốt, nhưng khổ nỗi trên đảo lại không có nhiều dụng cụ đo đạc. Không êke, không thước đo độ, nên Pirate chỉ còn cách dựa vào cạnh của N tấm ván ban đầu để cưa cho thẳng thôi. Pirate chỉ có thể cưa theo những đoạn thẳng chứa một cạnh nào đó (dọc hoặc ngang) của các tấm ván.  

Hãy giúp anh ấy cưa được tấm biển lớn nhất có thể.

Input

Dòng thứ nhất: ghi số nguyên N - số tấm ván. 

N dòng tiếp theo: mô tả độ cao của các tấm ván theo thứ tự trái sang phải sau khi đã dán lại.

Output

Một số nguyên duy nhất là độ dài cạnh của tấm biển lớn nhất có thể cưa được.
Độ cao của các tấm ván là các số nguyên dương không vượt quá 109.
1 ≤ N ≤ 106.
60% số test có 1 ≤ N ≤ 2000.
80% số test có 1 ≤ N ≤ 105.

Example:

Input

7
5
2
4
3
3
1
4

Output:

3

• Solution:

- Giải thích: Hình dưới đây minh họa phương án tối ưu.

- Ý tưởng: + Áp dụng stack tại mỗi tấm ván tìm vị trí xa nhất bên trái mà tấm ván đó còn cắt được. + Áp dụng stack tại mỗi tấm ván tìm vị trí xa nhất bên phải mà tấm ván đó còn cắt được. - Thực hiện: + Đặt vị trí 0 và n+1 có độ cao là: 0 (hai điểm chốt hai đầu). + Duyệt 1: Duyệt từng phần tử i:(1->n) cho i (vị trí) vào stack. (trước khi cho vào stack thì pop hết tất cả các độ cao mà lớn hơn [i] - Điều này có nghĩa là loại các tấm ván cao hơn nó là các tấm ván có thể cắt được). Còn lại (top) chính là vị trí xa nhất không cắt được -> Lưu vị trí đó. + Duyệt 2: Tương tự nhưng duyệt (n->1). + Sau khi duyệt ta có left và right ở tại mỗi tấm ván.Vậy thì chỉ cần lấy left[]-right[]-1 là đã có chiều dài tối đa khi cắt theo tấm ván đó. -> Chỉ cần so sánh lấy max là được.

• Code:

C++:

JAVA:

DTTUI1 - Cái túi 1

Link Sub: http://vn.spoj.com/problems/DTTUI1/
Người Gửi: Dương Lee

• Problem:

Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng vàng. Đảo có N cục vàng. Anh ấy muốn chuyển hết cả N cục vàng của mình về nhà. Nhưng khổ nổi các cục vàng này lại có trọng lượng và kích thước khổng lồ. Khánh đem theo một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống vàng này. Khổ quá đi! Lấy cục nào, bỏ cục nào bây giờ! Các bạn giúp anh ấy tìm ra một cách chọn vàng để thu được giá trị lớn nhất mà vẫn không làm rách túi đi.
Input
Dòng 1: Chứa 2 số nguyên: số cục vàng N (1 ≤ N ≤ 40) và tải trọng tối đa của túi M (1 ≤ M ≤ 10^9). 
N dòng sau: Mỗi dòng chứa 2 số nguyên: trọng lượng Wi và giá trị Vi của cục vàng thứ i (1 ≤ Wi, Vi ≤ 10^8).

Output
Một số nguyên duy nhất là giá trị lớn nhất thu được.

Example:

Input

3 4
1 4
2 5
3 6

Output:

10

• Solution:

Bài này N=40 (không quá lớn) nên ta có thể phân tập. Các bước làm: - Chia đôi tập dữ liệu nhận vào: P2: N2=N/2 và P1: N1=N-(N/2); - Sinh nhị phân các trường hợp chọn vàng của P1 và P2 (sao cho khối lượng không quá M ở mỗi tập + nhánh cận để giảm time). - Sắp xếp P2 tăng dần theo khối lượng. - Quy hoạch lại giá trị của mỗi cục vàng (S[]) sao cho S[i] = max (P2_[1->i]_V). - Với mỗi W của P1_i tìm vị trí (VT) P2 có W sao cho (P2_W + P1_i_W <= M). (Tìm nhị phân). - Với mỗi VT ta đã có sẵn S[VT] là giá trị max V của P2 đã quy hoạch ngay trên. Chỉ cần lấy Ans = max (Ans, P1_i_V+S[VT]). *Chú ý: Vì mỗi P1_W và P2_W nó đã <= M rồi nên cũng cần so sánh Ans với P1_V, P2_V;

• Code:

C++:

JAVA:

PBCWATER - Tính toán lượng nước

Link Sub: http://vn.spoj.com/problems/PBCWATER/

Người Gửi: Dương Lee

• Problem:

Nền phẳng của 1 công trình xây dựng được chia thành lưới ô vuông đơn vị kích thước  MxN ô. Trên mỗi ô (i,j) của lưới, người ta dựng 1 cột bê tông hình hộp có đáy là ô (i,j) và chiều cao là h[i,j] đơn vị. Sau khi dựng xong thì trời đổ mưa to và đủ lâu. Nhà thầu xây dựng muốn tính lượng nước đọng lại giữa các cột để có kế hoạch thi công tiếp theo. Giả thiết, nước ko thẩm thấu qua các cột bê tông cũng như ko rò rỉ qua các đường ghép giữa chúng.

Nhiệm vụ của bạn là giúp nhà thầu tính toán lượng nước đọng lại giữa các cột.

Input

Dòng đầu tiên ghi 2 số nguyên dương M và N  

Dòng thứ i trong M dòng tiếp theo, ghi N số nguyên dương h[i,1],h[i,2]...h[i,N].

Giới hạn:     1<=M,N<=100,1<=H[i,j]<=1000

Output

1 dòng duy nhất chứa số đơn vị khối nước đọng lại.

Example:

Input

5 5
9 9 9 9 9
9 2 2 2 9
9 2 5 2 9
9 2 2 2 9
9 9 9 9 9

Output:

60

• Solution:

*Ý tưởng: - Ta xét từng phân khúc từ dưới lên (giống chặt cây thành từng đoạn có độ cao là 1); - Xét đường biên nếu biên thấp hơn bên trong thì đánh dấu bên trong không có nước đọng. - Duyệt lại và đếm xem có bao nhiêu ô có nước đọng. *Thực hiện: - Tạo mảng riêng H_Sp với các chỉ số 0 và 1; - Mảng riêng có đặc điểm: + Tại hàng i, cột j: H[i][j]<1?H_Sp[i][j]=0:H_Sp[i][j]=1; và H[i][j]--; VD: 1 1 0 3 0 2 1 1 1 -> Chặt lần 1 sẽ thu được: H_Sp: 1 1 0 1 0 1 1 1 1 H: 0 0 0 2 0 1 0 0 0 + Sẽ chặt cho đến khi Hmax =0; + Với mỗi H_Sp thu được sẽ duyệt đường biên nếu biên H_Sp[i][j]==0? thì có nghĩa là đường biên này đang thấp hơn các cột khác. -> Ta sẽ loang từ biên loang vào 4 phía, đánh dấu các ô ==0 -> 1 (Bước này dùng để xác định tại các ô đó sẽ không có nước đọng) VD: với H_Sp trên khi loang vào sẽ được: 1 1 1 1 0 1 1 1 1 + Cuối cùng thì chỉ cần duyệt lại mảng H_Sp để đếm các ô ==0 (nước đọng) và lặp lại quá trình cho đến Hmax=0;

• Code:

C++:

JAVA: