ROBOT

Hãng Carrel đã thiết kế một loại robot mới phục khảo sát mọi loại địa hình. Tuy vậy, robot cần nhiều nhiên liệu hơn khi di chuyển trên các địa hình gồ ghề và ít nhiên liệu khi đi trên các địa hình bằng phẳng. Điều hạn chế duy nhất là robot chỉ có thể đi từng bước theo một trong 4 hướng Đông , Tây, Nam, Bắc đối với vị trí hiện tại của mình. Robot có khả năng liên lạc với vệ tinh để nhận được bản đồ địa hình và tự tính toán đường đi tối ưu tới đích sao cho ít tốn nhiên liệu nhất. Tuy vậy, cán bộ nghiên cứu phụ trách theo dõi hoạt động của robot cần có chương trình độc lập xác định đường đi này để nạp nhiên liệu cho robot. Bình nhiên liệu của robot cho phép nó đi được 9 999 bước nếu mỗi bước cần một đơn vị nhiên liệu.
Từ vệ tinh, robot nhận được bản đồ địa hình dưới dạng lưới ô vuông kích thước m*n ô (0 < m, n ≤ 100), trên mỗi ô ghi một số nguyên dương xác định chi phí nhiên liệu đi qua ô đó, m là số dòng và n là số cột của lưới. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Robot cũng đã được biết trước toạ độ điểm xuất phát và điểm đích cần tới.

Yêu cầu: Cho biết bản đồ địa hình và toạ độ các điểm đầu , cuối đường đi. Hãy tính nhiên liệu cần nạp

Dữ liệu: Vào từ file văn bản ROBOT.INP, gồm nhiều bộ dữ liệu:

+ Dòng đầu tiên chứa số nguyên t - số bộ tests trong file,

+ Mỗi test bao gồm một nhóm dòng, trong đó:

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

- m dòng tiếp theo: mỗi dòng chứa n số nguyên, mô tả một dòng của bản đồ,

- dòng cuối cùng chứa 4 số nguyên xác định toạ độ ô xuất phát và ô đích.

Kết quả: Đưa ra file văn bản ROBOT.OUT: với mỗi test đưa ra một số nguyên trên một dòng xác định lượng nhiên liệu cần nạp.

Ví dụ:

ROBOT.INP	ROBOT.OUT
3 5 5 1 1 5 3 2 4 1 4 2 6 3 1 1 3 3  5 2 3 1 2 2 1 1 1 1 1 1 5 5  5 4 2 2 15 1 5 1 15 1 5 3 10 1 5 2 1 1  8 13 2 15 1 1 1 4  10 10 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 10 10	10 15 19

TEST - CODE

SỐ PINARY

Pinary là số nguyên chứa các số 0 và 1 thoả mãn các điều kiện:

+ Không bắt đầu bằng 0,

+ Không chứa 2 số 1 liên tiếp nhau.

Ví dụ, các số sau là số Pinary: 1, 10, 100, 101, 1000, 1001, 1010, . . . Còn các số sau không phải là Pinary: 00101, 1001101.

Các số Pinary được sắp xếp theo thứ tự từ điển.

Yêu cầu: Cho số nguyên n. Hãy xác định số Pinary thứ n.

Dữ liệu: Vào từ file văn bản PINARY.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên n (0<n≤90000000).

Kết quả: Đưa ra file văn bản PINARY.OUT các số Pinary tìm được, mỗi số trên một dòng.

Ví dụ:

PINARY.INP	PINARY.OUT
7 2000 22	1010 1001000001001000 1000001

SOLUTION - TEST - CODE

SỐ NGUỒN

Giả thiết N là số nguyên dương. Số nguyên M là tổng của N với các chữ số của nó. N được gọi là nguồn của M. Ví dụ, N = 245, khi đó M = 245 + 2 + 4 + 5 = 256. Như vậy, nguồn của 256 là 245.

Không có gì đáng ngạc nhiên nếu thấy rằng có những số không có nguồn và có số lại có nhiều nguồn.

Ví dụ, số 216 có 2 nguồn là 198 và 207.

Yêu cầu: Cho số nguyên M. hãy tìm nguồn nhỏ nhất của nó. Nếu M không có nguồn thì đưa ra số 0.

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

+ Dòng đầu tiên chứa số nguyên T – số lượng Tests,

+ T dòng sau: mỗi dòng chứa một số nguyên M. (M có tối đa 100 chữ số)

Kết quả: Đưa ra file văn bản GEN.OUT, mỗi kết quả đưa ra trên một dòng.

Ví dụ:

GEN.INP	GEN.OUT
3 216 121 2005	198 0 1979

SOLUTION - TEST - CODE

ĐIỂM SỐ

Trong kỳ thi vấn đáp học sinh phải trả lời các câu hỏi của thầy giáo. Nếu trả lời đúng, thầy giáo đánh dấu bằng ký tự ‘C’ (Correct), nếu sai thì đánh dấu ‘N’ (No Correct). Khi học sinh trả lời đúng, thầy sẽ đưa ra câu hỏi tiếp theo khó hơn câu trước, còn khi trả lời sai thầy sẽ cho câu hỏi mới dễ hơn. Sau khi thi xong, kết quả của mỗi học sinh là một xâu các ký tự ‘C’ và ‘N’. Điểm số của học sinh sẽ được tính như sau: Với các câu trả lời sai học sinh không được điểm, với mỗi câu trả lời đúng học sinh nhận được điểm bằng số lần trả lời đúng liên tiếp từ câu trả lời này trở về trước. Ví dụ, nếu kết quả là ‘CCNNCNNCCC’, thì điểm số sẽ là 1+2+0+1+0+0+1+2+3 = 10.

Yêu cầu: Cho xâu kết quả độ dài không quá 80, hãy tính điểm của học sinh.

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

+ Dòng đầu tiên chứa số nguyên T - số lượng Tests,

+ Mỗi dòng trong T dòng sau chứa một xâu kết quả thi.

Kết quả: Đưa ra file văn bản SCORE.OUT điểm số của từng kết quả, mỗi điểm số là một số nguyên và đưa ra trên một dòng.

Ví dụ:

SCORE.INP	SCORE.OUT
5 CCNNCNNCCC CCNNCCNNCC CNCNCNCNCNCNCN CCCCCCCCCC CCCCNCCCCNCCCCN	10 9 7 55 30

GHÉP SỐ

Cho n số nguyên dương a1, a2, . . .,an (1 < n ≤ 50), mỗi số không vượt quá 2 147 483 647. Từ các số này người ta tạo ra một số nguyên mới bằng cách ghép tất cả các số đã cho, tức là viết liên tiếp các số đã cho với nhau. Ví dụ, với n = 4 và các số 123, 124, 56, 90 ta có thể tạo ra các số mới – 1231245690, 1241235690, 5612312490, 9012312456, 9056124123, v. v... Có thể dễ dàng thấy rằng, với n = 4, ta có thể tạo ra 24 số mới. Trong trường hợp này, số lớn nhất có thể tạo ra là 9056124123. 

Yêu cầu: Cho n và các số a1, a2, . . .,an . Hãy xác định số lớn nhất có thể tạo ra khi ghép các số đã cho thành một số mới.

Dữ liệu: Vào từ file văn bản NUMJOIN.INP, gồm nhiều tests, mỗi test ghi trên 2 dòng:

+Dòng thứ nhất chứa số nguyên n,

+ Dòng thứ 2 chứa n số nguyên a1 a2 . . . an .

Dữ liệu kết thúc bằng dòng chứa một số 0.

Kết quả: Đưa ra file văn bản NUMJOIN.OUT, mỗi kết quả đưa ra trên một dòng dưới dạng một số nguyên.

Ví dụ:

NUMJOIN.INP	NUMJOIN.OUT
4 123 124 56 90 5 123 124 56 90 9 5 9 9 9 9 9	9056124123 99056124123 99999

SOLUTION

ĐẢO KÝ TỰ

Hai từ được gọi là đảo nhau, nếu từ một từ ta có thể nhận được từ kia bằng cách đảo vị trí các ký tự. Ví dụ, occurs và succor là hai từ đảo, còn dear và dared không phải là đảo nhau vì từ thứ nhất có một ký tự d, còn từ thứ hai có 2 ký tự d. Cặp từ đảo nhau nổi tiếng nhất trong tiếng Anh là dog và god (con chó và chúa trời).

Hai từ rỗng cũng có thể coi như cặp từ đảo nhau. Với 2 từ bất kỳ, bao giờ ta cũng có cách xoá đi k1 ký tự ở từ thứ nhất và k2 ký tự ở từ thứ 2 để chúng trở thành cặp từ đảo nhau. Khoảng cách giữa 2 từ được xác định là min{k1+k2}.

Yêu cầu: Cho 2 từ, mỗi từ có độ dài không quá 45 ký tự và chỉ chứa các chữ cái thường trong bảng chữ cái tiếng Anh. Hãy xác định khoảnh cách giữa chúng.

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

+Dòng đầu tiên chứa số nguyên n - số lượng tests, 0 < n ≤ 60 000,

+ Mỗi test cho trên 2 dòng, mỗi dòng chứa một từ.

Kết quả: Đưa ra file văn bản ANAGRAM.OUT đưa ra trên n dòng, mỗi dòng chứa một số nguyên, dòng thứ i chứa khoảng cách của cặp từ thứ i trong dữ liệu vào.

Ví dụ:

ANAGRAM.INP	ANAGRAM.OUT
3 crocus succor dares seared smell lemon	0 1 4

XẾP PHÒNG KHÁCH SẠN

Một khách sạn có n phòng đánh số từ 1 đến n, mỗi phòng có hai giường.

Khi một đoàn khách đến, họ sẽ được nhân viên lễ tân sắp xếp theo cách như sau: Trong các phòng còn trống, 1 cặp (2 khách) được xếp vào phòng có thứ tự nhỏ nhất. Nếu số khách trong một đoàn là lẻ thì người cuối cùng sẽ được xếp vào phòng trống có số thứ tự nhỏ nhất (trong các phòng còn lại). Nếu không còn đủ phòng thì mỗi khách sẽ được xếp vào phòng có 1 khách đoàn khác đang sử dụng với số thứ tự nhỏ nhất.
Lúc đầu, khách sạn không có khách (trống). Số khách của mỗi đoàn được biết trước. Viết chương trình xác định số khách trong từng phòng sau khi sắp xếp xong vị khách cuối cùng.

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

+ Dòng đầu chứa 2 số nguyên dương n, k (1 <= n <=100); n là số phòng khách sạn, k là số đoàn khách.

+ K dòng tiếp theo, dòng thứ i+1 chứa 1 số nguyên dương là số khách trong đoàn i, i=1 … k.

Tổng số khách (trong tất cả các đoàn) nhỏ hơn hoặc bằng số giường trong khách sạn.

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

Chứa n dòng, dòng thứ i là số khách xếp trong phòng đó sau khi đã xếp vị khách cuối cùng.

Ví dụ:

ROOM.INP	ROOM.OUT
5 4 3 1 1 4	2 2 2 1 2

CHUỖI NGỌC

Dọc theo con đường tơ lụa những con lạc đà cần mẫn chuyên chở tơ lụa, hương liệu và ngọc ngà đá quý của phương đông. Đá quý được phân thành 26 loại ký hiệu bằng chữ cái la tinh thường từ a đến z. Các lái buôn muốn bán được hàng với giá càng cao càng tốt. Trong chuyến đi này một lái buôn mang theo bộ đá quý gồm n viên (1 ≤ n ≤ 100 000). Ông xâu tất cả thành chuỗi và bày ra trên thảm trước một lãnh chúa hùng mạnh. Vị lãnh chúa cân nhắc đánh giá chất lượng bộ đá quý để quyết định có nên mua hay không. Theo quy tắc truyền thống của địa phương, giá trị của chuỗi ngọc phụ thuộc vào sự xuất hiện các cặp ngọc (ai, bi), tức là phải có ngọc loại ai đi trước loại bi (i = 1÷ k, 1 ≤ k ≤ 676).

Nếu giá trị chuỗi ngọc đủ lớn, lãnh chúa sẽ mua toàn bộ chuỗi ngọc.

Yêu cầu: Cho biết n và xâu S thể hiện các loại ngọc trong chuỗi, cách định giá trị chuỗi ngọc của địa phương. Hãy xác định giá trị của chuỗi ngọc.

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

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

+ Dòng thứ 2 chứa xâu S,

+ Mỗi dòng trong k dòng sau chứa xâu 2 ký tự xác định cặp có giá trị.

Kết quả: Đưa ra file văn bản GEMS.OUT một số nguyên – giá trị chuỗi ngọc.

Ví dụ:

GEMS.INP	GEMS.OUT
7 3 abacaba ab ac bb	7

SOLUTION

CÁC NỀN VĂN MINH CỔ ĐẠI

Các nền văn minh cổ đại có những ảnh hưởng qua lại tới nhau trực tiếp hoặc gián tiếp nếu có khoảng thời gian cùng tồn tại. Ảnh hưởng sẽ càng lớn nếu thời gian tồn tại đồng thời lớn. Ví dụ, nếu nền văn minh A tồn tại từ 600 năm trước công nguyên (CN) đến trước năm 400 trước CN, còn nền văn minh B xuất hiện vào năm 450 trước CN và tồn tại đến trước năm 300 trước CN, thì giữa chúng có 50 nămcùng tồn tại. Nếu nền văn minh C xuất hiện vào năm 400 trước CN và tồn tại đến trước năm 50 trước CN thì giữa A và C không có tác động qua lại, trong lúc đó giữa B và C có đến 100 năm cùng tồn tại và ảnh hưởng qua lại.
Để đánh giá mức độ ảnh hưởng theo thời gian, các nhà khảo cổ học quyết định chọn 2 nền văn minh có khoảng thời gian cùng tồn tại khác 0 nhỏ nhất trong số N nền văn minh mà tài liệu còn được ghi chép và tìm thấy ( 1 ≤ N ≤ 100 000).

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

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

+ N dòng sau mỗi dòng chứa 2 số nguyên Si và Ei, trong đó Si – năm xuất hiện, Ei – năm diệt vong, giá trị âm hoặc 0 thể hiện trước công nguyên, giá trị tuyệt đối của năm không vượt quá 109. 

Kết quả: Đưa ra file văn bản ANCIENT.OUT hai số nguyên trên một dòng xác định các nền văn minh có thời gian cùng tồn tại khác 0 nhỏ nhất. Nếu không tìm thấy 2 nền văn minh nào cùng tồn tại thì đưa ra một số 0.

Ví dụ:

ANCIENT.INP	ANCIENT.OUT
3 -10 80 -80 10 60 90	1 3

CẶP SỐ 0

Xuất phát từ xâu S ban đầu chỉ chứa một ký tự ‘1’, người ta biến đổi n lần theo quy tắc sau:

+ Tạo xâu T bằng cách đảo các ký tự trong S: ‘1’ thành ‘0’ và ngược lại,

+ Tính S mới: S := T + S.

Với cách biến đổi đó, ta có:

n	S
1	01
2	1001
3	01101001

Yêu cầu: Cho biết n (0 < n ≤ 1 000). Hãy xác định cặp số 0 trong xâu S sau n lần biến đổi.

Dữ liệu: Vào từ file văn bản PAIR.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên n.

Kết quả: Đưa ra file văn bản PAIR.OUT, mỗi kết quả đưa ra trên một dòng dưới dạng số nguyên.

Ví dụ: 

PAIR.INP	PAIR.OUT
2 3	1 1

SOLUTION - TEST -  CODE