Bài tập Tin học: 2017

Thứ Tư, 28 tháng 6, 2017

[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:

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

Thứ Hai, 10 tháng 4, 2017

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

Chủ Nhật, 9 tháng 4, 2017

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).

+ Có 60% số tests với 0 < N ≤ 2000.

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

Test - code - solution - đề (word)

GAMES

Nguồn: Đề thi chọn học sinh giỏi Tin học tỉnh Khánh Hòa ngày 04/04/2017

Tý vừa mới khám phá ra một trò chơi trên mạng rất thú vị. Một trong những điều thú vị là người chơi phải nhập vai một người thám hiểm để đi tìm kho báu. Trò chơi mô phỏng một vùng biển trong đó có một quần thể gồm N hòn đảo được đánh số thứ tự từ 1 đến N. Trong quần thể các hòn đảo này có một hòn đảo đang chứa một kho báu có giá trị rất lớn, nhưng để vào được kho báu người chơi phải có chìa khóa để mở cửa kho báu. Giữa các hòn đảo này đã có M cây cầu bắc qua sao cho giữa hai hòn đảo chỉ có không quá một cây cầu bắc qua và từ một hòn đảo bất kỳ có thể đến được các đảo khác bằng con đường đi qua những cây cầu này. Khi đi qua mỗi cây cầu, người chơi phải bỏ ra một số tiền dùng để mua vé qua cầu. Chìa khóa để mở kho báu được treo ở giữa một cây cầu đặc biệt, khi đi qua cây cầu này, người chơi không cần phải mua vé nhưng để lấy được chìa khóa người chơi phải đi qua cầu đúng một lần duy nhất (không quay lại đầu cầu đã đi qua) vì sau khi lấy chìa khóa và qua khỏi cầu thì cầu sẽ bị sập.

Yêu cầu: Trò chơi cho biết chỉ số hòn đảo ban đầu khi người chơi xuất phát, vị trí cây cầu có treo chìa khóa và chỉ số của hòn đảo chứa kho báu, bạn hãy lập trình tính xem Tý có thể chơi để lấy được chìa khóa và đến được kho báu để lấy châu báu hay không và nếu được thì phải tốn ít nhất bao nhiêu tiền để mua vé qua cầu.

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

+ Dòng đầu ghi số nguyên N và M (2 ≤ N ≤ 1000, N ≤ M ≤ N(N-1)/2);

+ Dòng thứ hai ghi 4 số nguyên s, t, a và b, trong đó s là thứ tự hòn đảo xuất phát của người chơi, t là chỉ số hòn đảo chứa kho báu và a, b (a ≠ b) là số thứ tự của hai hòn đảo có cây cầu bắc qua đang giữ chìa khóa mở kho báu.

+ Dòng thứ i (i =1..M) trong M dòng tiếp theo ghi 3 số nguyên u_i, v_i_, z_i với ý nghĩa là có cây cầu bắc từ đảo có chỉ số u_i đến đảo có chỉ số v_i (1≤ u_i, v_i_, ≤ N, u_i ≠ v_i_,) và phải mua vé với số tiền z_i là số nguyên (0<z_i≤ 1000).

Kết quả: Ghi ra tệp văn bản GAMES.OUT tổng số tiền ít nhất mà người chơi phải chi phí để đi từ s qua cầu (a, b) để lấy chìa khóa và cuối cùng đến t để lấy kho báu. Nếu người chơi không thể thực hiện được thì chỉ ghi số -1.

Ví dụ:

GAMES.INP	GAMES.OUT		GAMES.INP	GAMES.OUT
6 6 1 6 4 5 1 2 5 1 3 2 2 3 1 2 4 2 3 4 4 5 6 8	13		6 6 1 4 4 5 1 2 5 1 3 2 2 3 1 2 4 2 3 4 4 5 6 8	-1

Test - code (FP) - code (C++) - solution - đề (word)

NGÀY HỘI

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

Hành tinh Hough xa xôi được chia thành 2 nửa bán cầu có trình độ khoa học kỹ thuật khác hẳn nhau. Ở Hough A, ngành khoa học máy tính và tự động hóa phát triển mãnh mẽ, mọi công việc của họ đều được thực hiện một cách tự động. Trái ngược với Hough A, ở Hough B trình độ của họ vẫn đang ở mức thời kỳ đồ sắt bởi lẽ họ đề cao lao động chân tay.

Mặc dù trình độ khoa học kỹ thuật ở hai bán cầu rất khác nhau nhưng họ vẫn chung sống hòa bình với nhau từ thế kỷ này qua thế kỷ khác. Hằng năm họ còn tổ chức một cuộc thi lớn dành cho tất cả người dân trên hành tinh. Ở Hough A có n người tham dự còn Hough B có m người tham dự. Nhờ chương trình đo sức khỏe nên Hough A biết trước được chỉ số sức khỏe của tất cả người dân trên hành tinh. Trong cuộc thi, mỗi lượt sẽ có 2 người ở hai bán cầu lên thi đấu, người có chỉ số sức khỏe tốt hơn sẽ dành chiến thắng, mỗi người chỉ được thi đấu tối đa một lần.

Yêu cầu: Hãy cho biết mỗi người tham dự Hough B có chỉ số sức khỏe lớn hơn bao nhiêu người tham dự của Hough A.

Dữ liệu vào: Từ tệp văn bản HOUGH.INP gồm:

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

+ Dòng thứ 2 ghi n số nguyên dương a₁, a₂,…, a_n cho biết chỉ số sức khỏe của n người tham dự cuộc thi ở Hough A.

+ Dòng thứ 3 ghi m số nguyên dương b₁, b₂,…, b_mcho biết chỉ số sức khỏe của m người tham dự cuộc thi ở Hough B.

Kết quả: Ghi vào tệp văn bản HOUGH.OUT gồm m dòng, dòng thứ i cho biết người thứ i ở Hough B có chỉ số sức khỏe nhiều hơn bao nhiêu người ở Hough A.

Ví dụ: