ĐƯỜ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

ĐƯỜNG ĐI CỦA ROBOT

Trong chương trình chinh phục mặt trăng, các nhà khoa học đang chế tạo một con rô-bốt có thể di chuyển trên bề mặt của mặt trăng. Một trong những bài kiểm tra đầu tiên của rô-bốt là di chuyển trên lưới ô vuông có kích thước NxM (2≤N, M≤200) từ (1, 1) đến ô (N, M), các dòng được đánh số từ 1 đến N, các cột được đánh số từ 1 đến M. Rô-bốt có thể di chuyển từ ô này qua ô khác nếu hai ô chung cạnh. Trong những lần thử nghiệm đầu tiên rô-bốt đều tìm được đường đi ngắn nhất để di chuyển, sau đó các nhà khoa học đã đặt thêm K chướng ngại vật vào K ô khác nhau trên lưới, lúc này rô-bốt thường đi thẳng vào các chướng ngại vật hoặc không thể tìm ra đường đi ngắn nhất.

Hãy giúp các nhà khoa học lập trình lại cho rô-bốt để nó có thể di chuyển từ ô (1, 1) đến ô (N, M) theo con đường ngắn nhất mà không va chạm với chướng ngại vật

Giả thiết ở ô (1, 1) và (N, M) không có chướng ngại vật và luôn có ít nhất một đường đi

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

+ Dòng đầu tiên chứa 3 số nguyên dương N, M, K

+ K dòng tiếp theo mỗi dòng ghi 2 số nguyên u và v cho biết tọa độ của một chướng ngại vật

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

+ Dòng đầu tiên ghi một số nguyên S cho biết số bước đi ngắn nhất

+ S dòng tiếp theo mỗi dòng ghi tọa độ 1 ô cho biết hành trình của rô bốt từ ô (1, 1) đến ô (N, M)

Ví dụ:

0	0	0	0
1	1	0	1
0	0	0	0
0	1	1	0
0	0	0	0

ROBOT1.INP	ROBOT1.OUT
5 4 5 2 1 2 2 2 4 4 2 4 3	8 1 1 1 2 1 3 2 3 3 3 3 4 4 4 5 4

ROBIN

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

Một ngày đẹp trời nọ, trên vương quốc của các Coders 2011, bỗng xuất hiện 1 lão phù thủy độc ác, lão phù thủy sirDat_LS đã có âm mưu thôn tính đất nước  của đức vua vodanh9x. Lão phù thủy này rất yêu con gái của đức vua là Rose và đã bắt Rose về nơi ở của lão ta.

Đức vua vodanh9x liền tìm hiệp sĩ Robin và sẽ hứa gả con gái cho Robin nếu chàng cứu được công chúa Rose trở về. Lão phù thủy sirDat_LS độc ác với khuôn mặt rất ghê tởm khiến công chúa mỗi khi nhìn thấy hắn thì công chúa lại ngất đi.

Và rồi, chàng Robin của chúng ta đã tìm được đến nơi ở của lão phù thủy. Nơi ở của lão là 1 mê cung có N phòng, và N phòng này liên thông với nhau và có đúng N-1 đường đi (coi mỗi đường đi là 1 cạnh).

Nhưng khó khăn thay, lão phù thủy đã đánh số mỗi đường đi là 1 hoặc 2. Nếu chàng Robin muốn đến cứu công chúa, thì từ nơi xuất phát đến nơi có công chúa phải có ít nhất một đường đi được đánh số 2, nếu không chàng Robin sẽ chết.

Yêu cầu: Cho m truy vấn (m <= 10^5) mỗi truy vấn có dạng (x,y), trong đó x là nơi xuất phát của Robin và y là nơi nhốt công chúa. Xác định đường đi ngắn nhất từ x đến y có cạnh co trọng số 2 hay không.

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

+ Dòng đầu là số nguyên N (N <= 10^4) - số đỉnh của đồ thị và M  – số truy vấn.

+ Từ dòng 2 đến dòng N: dòng thứ i chứa 2 số nguyên dương  x (x < i) và k (k <= 2) nghĩa là có cạnh nối giữa i và x và được đánh số là k.

+ M dòng sau: mỗi dòng chứa 2 số x và y (Biểu thị cho truy vấn (x,y)).

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

Với mỗi truy vấn, xuất ra “YES” nếu tồn tại đường đi có ít nhất 1 cạnh có trọng số 2, ngược lại xuất ra “NO”.

 Ví dụ:

C11BC2.INP	C11BC2.OUT
6 7 1 1 1 2 3 1 1 2 5 2 1 3 5 1 2 1 2 1 1 2 2 4 1 2	YES YES NO NO NO YES NO

CHÚ BÒ HƯ HỎNG

 Nguồn: http://www.spoj.com/PTIT/problems/BCDAISY/

Nông dân John có N (1<=N<=250) con bò đánh số từ 1..N chơi trên bãi cỏ.

Để tránh bị lạc mất các con bò, mỗi con bò có thể được nối với một số con bò khác bằng dây thừng.
Có tất cả M (1 <= M <= N*(N-1)/2) dây thừng nối các con bò. Tất nhiên, không có 2 con bò mà có nhiều hơn 1 dây thừng nối giữa chúng. Dữ liệu cho biết mỗi cặp con bò c1 và c2 là nối với nhau (1 <= c1 <= N; 1 <= c2 <= N; c1≠c2).

Nông dân John buộc cố định con bò 1 bằng sợi dây xích. Các con bò khác phải nối với con bò 1 bằng một số sợi dây thừng. Tuy nhiên, một số con bò hư hỏng không như vậy. Hãy giúp nông dân John tìm các con bò hư hỏng đó (không kết nối tới bò 1). Dĩ nhiên, con bò thứ 1 luôn nối tới chính nó.

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

+ Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N and M

+ Dòng 2..M+1: Dòng i+1 cho biết 2 con bò nối với nhau bằng sợi dây thứ i là c1 và c2 cách nhau bởi dấu cách.

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

+ Nếu không có con bò hư hỏng, in ra 0.

+ Ngược lại, in ra trên mỗi dòng 1 số nguyên là thứ tự con bò hư hỏng theo thứ tự tăng dần.

Ví dụ:

BCDAISY.INP	BCDAISY.INP
6 4 1 3 2 3 1 2 4 5	4 5 6

QUẢNG CÁO

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

Nhân dịp Tết sắp đến công ty Jelly-for-Kids quyết định tăng cường việc quảng bá sản phẩm đến người tiêu dùng. Vì thế giám đốc marketing, ông Fruit-Jelly muốn gửi đi số lượng nhân viên tối đa có thể, làm nhiệm vụ tiếp thị tại đại lý trong thành phố

Trong thành phố có m con đường, n đại lý bán kẹo (đánh số từ 1 đến n). Mỗi con đường chỉ nối trực tiếp giữa 2 đại lý, và được ký hiệu bằng chỉ số của 2 đại lý mà nó nối. Đồng thời, giữa 2 đại lý bất kỳ có không quá 1 con đường nối chúng

Ông Fruit-Jelly nghĩ rằng, ông ta sẽ quản lý nhân viên dễ hơn nếu xếp mỗi người tiếp thị trên những hành trình có tính chất thứ tự. Tức là những đại lý bán kẹo trên hành trình đó thỏa các điều kiện sau:

+ Có đường nối trực tiếp giữa 2 đại lý liên tiếp nhau trên hành trình

+ Từ một đại lý bất kỳ trong hành trình có thể đi qua tất cả các đoạn đường trong hành trình đó rồi trở về nơi xuất phát mà không đi qua đoạn đường nào quá một lần

+ Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị.

Mỗi nhân viên chỉ di chuyển trên hành trình mà anh ta được phân công. Hãy tính số lượng nhân viên tối đa mà ông Fruit-Jelly có thể xếp việc, và hành trình cụ thể mà mỗi người được xếp.

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

Dòng đầu là 2 số tự nhiên N và M (N<=2000) (M<=5000)

Trong M dòng tiếp theo, mỗi dòng ghi 2 số nguyên mô tả một đoạn đường, mỗi đoạn đường được mô tả bởi chỉ số của 2 đại lý mà nó nối.

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

Dòng đầu tiên ghi Q là số lượng nhân viên tối đa tìm được

Ví dụ:

ADS.INP	ADS.OUT
5 6 1 2 2 4 4 5 3 5 1 3 2 3	2

FIND THE COW!

Cô bò Bessie đã trốn thoát và đang trốn ở một đồi núi với những đồng cỏ cao. Nông dân John (FJ), người đang muốn tìm kiếm Bessie, đã quyết định bò trên đồng cỏ bằng tay và đầu gối để tìm ra dấu vết của Bessie. Không may thay, ông ta có một chút vấn đề với việc tìm kiếm Bessie: Dãy cỏ ở trước mặt FJ trông như một chuỗi ngoặc đơn có độ dài N (1≤ N≤ 50,000); ví dụ: )((()())()) FJ biết rằng chân sau của Bessie giống như một cặp dấu mở ngoặc đơn ((, và chân trước của cô ta giống như một cặp dấu đóng ngoặc đơn )). Vị trí của Bessie có thể được diễn tả bởi một cặp x < y , trong đó (( được tìm ở vị trí x, và )) được tìm ở vị trí y. Hãy đếm có bao nhiêu vị trí mà Bessie có thể đang đứng.

Dữ liệu vào: ghi từ tệp COWFIND.INP

+ Dòng 1: Một chuỗi ngoặc đơn có độ dài là N

Dữ liệu ra: ghi vào tệp văn bản COWFIND.OUT một số nguyên cho biết vị trí Bessise đang đứng

Ví dụ:

COWFIND.INP	COWFIND.OUT
)((()())())	4

Giải thích: Các vị trí Bessise có thể đứng là

1. )((()())())

2. )((()())())

3. )((()())())

4. )((()())())

TEST

DÃY SỐ

Steve không tập trung tư tưởng trong giờ toán vì vậy thầy giáo cho thêm bài tập về nhà rèn luyện khả năng tập trung tư tưởng và tính cẩn thận chu đáo.

Nội dung bài tập là cho n xâu chỉ bao gồm các ký tự la tinh thường và chữ số. Đoạn các ký tự số liên tục tạo thành một số nguyên. Ở mỗi đoạn ký tự số liên tục Steve phải trích ra số lớn nhất có thể, sắp xếp các số nhận được từ các xâu đã cho và đưa ra theo thứ tự không giảm, mỗi số được đưa ra dưới dạng không có các số 0 không có nghĩa.

Ví dụ, với n = 1 và xâu là 01a2b3456cde478 dãy số cần đưa ra là 1, 2, 478, 3456.

Yêu cầu: Cho số nguyên n (1 ≤ n ≤ 100) và n xâu, mỗi xâu có độ dài không quá 100. Hãy đưa ra dãy số nhận được đã sắp xếp theo thứ tự không giảm, mỗi số trên một dòng.

Dữ liệu: Vào từ file văn bản NUMBERS.INP:

+ Dòng đầu tiên chứa số nguyên n,

+ Mỗi dòng trong n dòng sau chứa một xâu chỉ gồm các ký tự la tinh thường và số.

Dữ liệu đảm bảo có không quá 500 số được tách ra.

Kết quả: Đưa ra file văn bản NUMBERS.OUT dãy số nhận được đã sắp xếp theo thứ tự không giảm, mỗi số trên một dòng.

Ví dụ:

NUMBERS.INP	NUMBERS.OUT
4 43silos0 zita002 le2sim 231233	0 2 2 43 231233

TEST - CODE