BỘ BA CAO THỦ

Nguồn: http://vn.spoj.com/problems/NKTRIO

Ở thời loạn, giang hồ có rất nhiều cao thủ võ lâm, mỗi người trong số họ lại có những tuyệt chiêu. Nếu 2 cao thủ giang hồ so tài với nhau thì từ những sở trường và sở đoản của họ, ta có thể biết trước được cao thủ nào sẽ thắng. Những cao thủ đang có ở VNOI như conankudo, gothdn, kaiel, nahnhnahk, pirate... đang muốn thi tài để xem ai được chọn làm bộ ba cao thủ.

Để mưu nghiệp lớn, minh chủ võ lâm Nuga cần tìm ra một bộ ba trong số các cao thủ giang hồ hiện tại. Để các cao thủ này quy phục dưới trướng của mình và không làm phản, Nuga muốn bộ ba cao thủ này có thể khắc chế được nhau; điều này có nghĩa là nếu 3 cao thủ được chọn là A, B và C thì A phải thắng được B, B phải thắng được C và C phải thắng được A.

Bạn hãy giúp Nuga chọn ra một bộ ba cao thủ thoả mãn yêu cầu của ông.

Dữ liệu vào: Từ tệp văn bản NKTRIO.INP

Dòng đầu tiên ghi n là số cao thủ trên giang hồ (3 ≤ n ≤ 1000)

Tiếp theo là n dòng, mỗi dòng có n số. A[i,j] = 1 là người i thắng j. Dữ liệu luôn đảm bảo A[i,j] + A[j,i] = 1. A[i,i] = 0 với mọi i.

Dữ liệu ra: ghi vào tệp văn bản NKTRIO.OUT

Ghi ra ba số nguyên A, B và C là thứ tự của ba cao thủ thoả mãn A thắng B, B thắng C và C thắng A. Trong trường hợp có nhiều cách lựa chọn, bạn chỉ cần chỉ ra một cách; trong trường hợp không có cách lựa chọn thoả mãn yêu cầu, ghi ra ba số -1.

Ví dụ:

NKTRIO.INP	NKTRIO.OUT
5 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0	2 3 5
3 0 1 1 0 0 1 0 0 0	-1 -1 -1

TRÒ CHƠI CÁC Ô VUÔNG THẦN BÍ

Xét một bảng có 8 ô vuông trong đó mỗi ô vuông có một màu khác nhau, các mùa được ký hiệu bởi 8 số nguyên dương đầu tiên. Các trạng thái của bảng được cho bởi dãy ký hiệu màu của các ô được viết lần lượt theo chiều kim đồng hồ bắt đầu từ góc trái trên và kết thúc ở góc trái dưới.

1	2	3	4
8	7	6	5

Ví dụ trạng thái của bảng trong hình trên được cho bởi dãy (1, 2, 3, 4, 5, 6, 7, 8). Trạng thái này được gọi là trạng thái khởi đầu.

Có thể dùng 3 phép biến đổi cơ bản có tên là ‘A’, ‘B’, ‘C’  trong đó:

      ‘A’: Đổi chỗ dòng trên và dòng dưới

      ‘B’: thực hiện một phép hoán vị vòng quanh sang phải

      ‘C’ Quay theo chiều kim đồng hồ 4 ô giữa

Biết rằng từ trạng thái khởi đầu luôn có thể chuyển về một trạng thái bất kỳ bằng cách dùng các phép biến đổi cơ bản nói trên. Tác động của 3 phép biến đổi cơ bản được mô tả trong hình sau:

+ Phép A

1	2	3	4		1	2	3	4
1	2	3	4	A →	8	7	6	5
8	7	6	5		1	2	3	4
8	7	6	5		8	7	6	5

+ Phép B

1	2	3	4		1	2	3	4
1	2	3	4	B →	4	1	2	3
8	7	6	5		5	8	7	6
8	7	6	5		8	7	6	5

+ Phép C

1	2	3	4		1	2	3	4
1	2	3	4	C →	1	7	2	4
8	7	6	5		8	6	3	5
8	7	6	5		8	7	6	5

Trong đó các số viết bên cạnh bảng dùng để chỉ các ô vuông của bảng và ô vuông ở vị trí p chứa số i có nghĩa là sau khi áp dụng phép biến đổi tương ứng ô vuông mà vị trí trước khi biến đổi của nó là i được chuyển đến vị trí p

Yêu cầu: Viết chương trình tìm dãy biến đổi cơ bản để chuyển bảng từ trạng thái khởi đầu về một trạng thái cho trước sao cho số phép biến đổi là ít nhất có thể.

Dữ liệu vào: File OVUONG.INP chứa 8 số nguyên liền nhau mô tả trạng thái đích

Dữ liệu ra: ghi vào file OVUONG.OUT

+ Dòng đầu tiên ghi số phép biến đổi của dãy

+ Các dòng tiếp theo ghi dãy các phép biến đổi theo thứ tự, mỗi phép biến đổi ghi trên một dòng

Ví dụ:

OVUONG.INP	OVUONG.OUT
26845731	7 B C A B C C B

TEST - Đề (word)

QUÂN TƯỢNG

Nguồn: http://vn.spoj.com/problems/QBBISHOP/

Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (r_i, c_i), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.

Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

Dữ liệu vào: Từ tệp văn bản QBBISHOP.INP

+ Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.

+ Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:  Ghi vào tệp văn bản QBBISHOP.OUT

Gồm 1 dòng duy nhất là số nước đi tìm được

Ví dụ:

QBBISHOP.INP	QBBISHOP.OUT
8 3 7 2 1 4 5 4 3 4 4 7	3

Hạn chế:

Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.

ĐẾM SỐ AO

Nguồn bài: http://www.spoj.com/PTIT/problems/BCLKCOUN/

Sau khi kết thúc OLP Tin Học SV, một số OLP-er quyết định đầu tư thuê đất để trồng rau.

Mảnh đất thuê là một hình chữ nhật N x M (1<=N<=100; 1<=M<=100) ô đất hình vuông.

Nhưng chỉ sau đó vài ngày, trận lụt khủng khiếp đã diễn ra làm một số ô đất bị ngập

Mảnh đất biến thành một số các ao. Các OLP-er quyết định chuyển sang nuôi cá :D Vấn đề lại nảy sinh, các OLP-er muốn biết mảnh đất chia thành bao nhiêu cái ao để có thể tính toán nuôi trồng hợp lý. Bạn hãy giúp các bạn ý nhé.

Chú ý: Ao là gồm một số ô đất bị ngập có chung đỉnh. Dễ nhận thấy là một ô đất có thể có tối đa 8 ô chung đỉnh.

 Dữ liệu vào: Từ tệp văn bản BCLKCOUN.INP

+ Dòng1: 2 số nguyên cách nhau bởi dấu cách: N và M

+ Dòng 2..N+1: M kí tự liên tiếp nhau mỗi dòng đại diện cho 1 hàng các ô đất.

Mỗi kí tự là 'W' hoặc '.' tương ứng với ô đất đã bị ngập và ô đất vẫn còn nguyên.

 Dữ liệu ra: ghi vào tệp văn bản BCLKCOUN.OUT 1 số nguyên duy nhất là số ao tạo thành.

 Ví dụ:

BCLKCOUN.INP	BCLKCOUN.OUT
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.	3

ĐƯỜNG HẦM DÀI NHẤT

Các nhà khảo sát địa chất đã ghi lại độ sâu tối đa ứng với các vị trí có thể đào được mà không gặp mạch nước ngầm của một khu đất có dạng hình chữ nhật. Các số đo được ghi lại trên một bản đồ gọi là bản đồ độ sâu. Bản đồ độ sâu là một hình chữ nhật được chia thành MxN ô vuông, mỗi ô vuông ghi một số nguyên biểu thị độ sâu có thể đào được tại vị trí đó của khu đất. Người ta muốn đào một đường hầm thoát nước dài nhất của khu đất này bắt đầu từ một ô có độ sâu nào đó (không nhất thiết bắt đầu ở các ô  biên) và kết thúc ở một ô tùy ý. Do nước chảy từ nơi cao xuống nơi thấp, nên đường hầm thoát nước khi đào qua các ô phải theo nguyên tắc đi từ ô có độ sâu nhỏ hơn đến ô chung cạnh có độ sâu lớn hơn.  

Yêu cầu:  Hãy đưa ra độ dài tối đa của đường hầm thoát nước có thể đào được.

Dữ liệu vào: Ghi trong file text, tên file là DUONGHAM.INP gồm hai dòng:

- Dòng đầu ghi hai số nguyên M và N ( 0<M £ 100; 0 < N £100).

- M dòng tiếp theo, mỗi dòng ghi N số nguyên  ai

(0< ai £ 100, i = 1,..,N).

Dữ liệu ra: Ghi ra file text tên file là DUONGHAM.OUT gồm một số nguyên là số ô mà  đường hầm dài nhất đi qua.

DUONGHAM.INP	DUONGHAM.OUT
3   4  10  21    3    7 11  31  12  14  5   21  13  16	5