[VNSPOJ] C11WATER - Đọng nước

Nền phẳng của một công trường xây dựng đã được chia thành lưới ô vuông đơn vị kích thước m x n ô. Trên mỗi ô (i,j) của lưới, người ta dựng một cột bê tông hình hộp có đáy là ô (i,j) và chiều lao là h_ij đơn vị. Sau khi dựng xong, thì trời đổ mưa to và đủ lâu. Giả thiết rằng nước không thấm qua các cột bê tông cũng như không rò rỉ qua các đường ghép giữa chúng.
Yêu cầu: Xác định lượng nước đọng giữa các cột.

Input

• Dòng đầu tiên chứa 2 số nguyên dương m,n (m, n <=1000)  
• m dòng tiếp theo, dòng thứ i chứa n số nguyên dương, số thứ j là h_ij (<=10⁶)

Các số trên cùng một dòng cách nhau ít nhất 1 dấu cách.

Output

• Khi ra số đơn vị khối nước đọng lại  

Example

Input:

5 7

3 3 3 3 3 3 3

3 1 1 1 1 1 3 

3 1 2 2 2 1 3 

3 1 1 1 1 1 3 

3 3 3 3 3 3 3  

Output:

27

Nguồn - Code - Solution(Đang cập nhật)

CÂY

Phong đang trồng cây. Một cây của Phong được định nghĩa là một đồ thị vô hướng gồm 𝑛 đỉnh và không có

chu trình. Phong quy ước gốc của cây sẽ là đỉnh số 1. Hỏi Phong có thể xây dựng bao nhiêu cây có gốc là 1?

2 cây được gọi là khác nhau nếu như trong tập cạnh của 2 cây, có tồn tại ít nhất 2 cạnh khác nhau.

Dữ liệu: Vào từ file văn bản COUNTINGTREE.INP gồm số 𝑛 (1 ≤ 𝑛 ≤ 13).

Kết quả: Ghi ra file văn bản COUNTINGTREE.OUT gồm một số nguyên duy nhất là kết quả bài toán Modulo 10^9+7.

Ví dụ:

COUNTINGTREE.INP	COUNTINGTREE.OUT
3	3

Giải thích: Ba cây có thể dựng được là:

1.   (1 – 3), (1 – 2)

2.   (1 – 2), (2 – 3)

3.   (1 – 3), (3 – 2)

Test - đề (word)

SỐ HỌC

Khôi Hoàng đang dạy bé Nhã Phương toán học. Khôi Hoàng ra đề cho bé Phương như sau :

"Cho em hai số nguyên 𝑝 và 𝑞, hãy tìm một số nguyên 𝑛 nhỏ nhất sao cho khi lấy chữ số đầu tiên đưa xuống thành chữ số cuối cùng thì sẽ được số mới bằng 𝑝/𝑞 lần số cũ"

Bé Phương không muốn mình cảm thấy thua thiệt nên đã nhờ anh Đinh Khôi giải giúp. Anh Khôi vì muốn lấy lệ với gái nên đã bảo :"Ừ, em về đi, mai anh sẽ đưa em lời giải". Nhưng thực tế anh Khôi đã bí rồi. Bạn hãy cứu anh ấy nào.

Dữ liệu: Vào từ file văn bản NUMBER.INP gồm hai số 𝑝𝑝 và 𝑞 (1 ≤ 𝑝, 𝑞 ≤ 2^31-1).

Kết quả: Ghi ra file văn bản BEAUTIFUL.OUT một số nguyên 𝑛 (1 ≤ 𝑛 ≤ 2×10⁹) đồng thời thỏa mãn điều kiện bài toán. Nếu không tồn tại 𝑛 thì in ra -1.

Ví dụ:

NUMBER.INP	NUMBER.OUT
1 4	102564

Giải thích: Nếu ta đưa số 1 ra sau cùng, ta được số 25641 và 25641 = 102564 × ¼.

Test - đề (word)

ĐƯỜNG ĐI NGẮN NHẤT

Phạm Hưng nhà ở thành phố Nha Trang. Thành phố gồm 𝑛 ngôi nhà được đánh số từ 1 đến 𝑛 và các ngôi nhà được nối với nhau bởi 𝑚 con đường hai chiều. Nhà Phạm Hưng có số thứ tự là s. Phạm Hưng muốn biết xem từ nhà mình tới các nhà còn lại độ dài đường đi ngắn nhất là bao nhiêu, biết độ dài các con đường bằng nhau và bằng 6.

Dữ liệu: Vào từ file văn bản SHORTPATH.INP với định dạng như sau:

·         Dòng đầu tiên chứa số nguyên 𝑇 là số bộ dữ liệu (1 ≤ T ≤ 10);

·         Tiếp theo là nội dung của 𝑇 bộ dữ liệu, mỗi bộ dữ liệu gồm:

o    Dòng đầu tiên chứa hai số nguyên 𝑛 và 𝑚 (2 ≤ 𝑛 ≤ 1000)

o    𝑚 dòng tiếp theo, mỗi dòng chứa hai số nguyên 𝑢 và 𝑣 (1 ≤ 𝑢, 𝑣 ≤ 𝑛, 𝑢 ≠ 𝑣) cho biết có đường nối giữa hai nhà có số 𝑢 và 𝑣;

o    Dòng cuối cùng chứa số nguyên 𝑠 (1 ≤ 𝑠 ≤ 𝑛).

Kết quả: Ghi ra file văn bản SHORTPATH.OUT với định dạng như sau:

·             Ứng với mỗi bộ dữ liệu, ghi ra một dòng duy nhất 𝑛 − 1 số nguyên là độ dài đường đi ngắn nhất từ nhà của Phạm Hưng đến nhà của các bạn khác (trừ nhà của Hưng ra). Nếu nhà đang xét không thể đi đến từ nhà Hưng thì ghi số -1.

Ví dụ:

SHORTPATH.INP	SHORTPATH.OUT
2 4 2 1 2 1 3 1 3 1 2 3 2	6 6 -1 -1 6

 Test - đề (word)

Dãy số Fibonacci

Nhật Khôi rất thích nghiên cứu về toán. Bài toán hiện tại mà cậu ấy đang nghiên cứu là dãy Fibonacci với quy luật như sau:

·         𝑓₀ = 0, 𝑓₁ = 𝑥;

·         𝑓_𝑛 = 𝑓_𝑛−1 + 𝑓_𝑛−2 (∀ 𝑛 > 1).

Nhật Khôi rất thích thú khi đã tính được tới số Fibonacci thứ 𝑛. Sau đó cậu quyết định đi ngủ. Trong lúc ngủ, không biết rằng Nga Hằng Nguyễn đã chui từ đâu ra và phá nát mất 2 số 𝑓₀ và 𝑓₁ của Nhật Khôi. Nhật Khôi ngồi khóc một mình trong 4 bức tường vì cậu ấy không thể tìm ra được số 𝑥 của mình. Điều mà Nhật Khôi vẫn còn nhớ trong đầu đó là số 𝑓₀ đầu tiên chắc chắn là số 0 và số 𝑛 và giá trị 𝑓_𝑛. Nhưng Nhật Khôi đã quên số 𝑥 rồi.

Yêu cầu: Hãy giúp Nhật Khôi tìm lại số 𝑥 của mình nhé!!!

Dữ liệu: Vào từ file văn bản FIBONACCI.INP gồm hai số là lượt là 𝑛 và 𝑓_𝑛  (2 ≤ 𝑛 ≤ 1000).

Kết quả: Ghi ra file văn bản FIBONACCI.OUT gồm một số nguyên duy nhất là số 𝑥.

Ràng buộc:

·         Có 40% số lượng tests thỏa mãn điều kiện: 0 ≤ 𝑓_𝑛  ≤ 1000000;

·         60% số lượng tests còn lại thỏa mãn điều kiện: 0 ≤ 𝑓_𝑛 ≤ 10¹⁸.

Ví dụ:

FIBONACCI.INP	FIBONACCI.OUT
6 8	1

 Test

CHUỖI ĐẸP

Huy đang gặp một vấn đề khó khăn trong việc xử lý chuỗi. Huy đang muốn chuẩn hóa chuỗi đó về dạng chuỗi đẹp. Một chuỗi được gọi là "chuỗi đẹp" nếu như tồn tại một vị trí 𝑝 trong chuỗi sao cho từ vị trí đầu tiên đến vị trí 𝑝 là chữ cái La-tinh in hoa, còn từ vị trí 𝑝 + 1 đến 𝑛 là chữ cái La-tinh in thường.

Lưu ý: Chuỗi mà toàn bộ các ký tự đều in hoa hay in thường cũng được gọi là một chuỗi đẹp.

Để biến từ một chuỗi 𝑠 thành một chuỗi đẹp, Huy phải sử dụng tiền túi của mình để chuẩn hóa nó. Một phép biến đổi tác động vào ký tự thứ 𝑖, sẽ biến ký tự đó từ in hoa thành in thường và ngược lại. Đồng thời Huy sẽ mất một số tiền không nhỏ là 𝑜rd(𝑠_𝑖) – với 𝑜rd(𝑐) là giá trị mã Ascii của ký tự 𝑐.

Yêu cầu: Hãy giúp Huy biến đổi từ một chuỗi 𝑠 ban đầu sao cho thành một chuỗi đẹp với chi phí nhỏ nhất có thể nhé!

Dữ liệu: Vào từ file văn bản BEAUTIFUL.INP gồm một dòng duy nhất là chuỗi 𝑠𝑠 (1 ≤ |𝑠| ≤ 100 000).

Kết quả: Ghi ra file văn bản BEAUTIFUL.OUT một số nguyên duy nhất là tổng số tiền nhỏ nhất mà Huy cần bỏ ra để biến chuỗi 𝑠𝑠 thành một “chuỗi đẹp”.

Ví dụ:

BEAUTIFUL.INP	BEAUTIFUL.OUT
bAa	65

Giải thích: Thay vì chuyển ký tự 'b' đầu tiên thành 'B' thì mất chi phí là 98 , thì ta sẽ chuyển từ 'A' thành 'a' thì chi phí chỉ mất 65.

Test

XÂU CON

Nguồn: Đề thi chọn đội tuyển Tin học tỉnh Khánh Hòa ngày 04/04/2017

Cho một xâu ký tự S gồm N ký tự thường trong bảng chữ cái tiếng Anh và một số nguyên dương K.

Yêu cầu: Bạn hãy tìm một chuỗi con liên tục dài nhất sao cho chuỗi con đó có chứa đúng K ký tự khác nhau.

Dữ liệu vào: Tệp văn bản SUBSTRING.INP gồm:

+ Dòng đầu ghi hai số nguyên N và K.

+ Dòng thứ hai gồm N ký tự chữ cái in thường trong bảng chữ cái tiếng Anh.

Kết quả: Ghi ra tệp văn bản SUBSTRING.OUT một số nguyên duy nhất là độ dài chuỗi con liên tục dài nhất tìm được.

Ví dụ:

SUBSTRING.INP	SUBSTRING.OUT
7 2 abbabef	5

Trong ví dụ trên, chuỗi dài nhất tìm được gồm 5 ký tự đầu là “abbab”, chỉ gồm 2 ký tự khác nhau là ‘a’ và ‘b’.

Giới hạn dữ liệu

+ 0 < K ≤ min(N , 26).

+ Có 60% số tests với 0 < N ≤ 2000.

+ Có 40% tests còn lại với 2000 < N ≤ 200000.

 Test - code - solution - đề (word)