Phục hồi tin nhắn
Câu 1: Phục hồi tin nhắn Tên file chương trình: MESS.PAS
Mạng viễn thông ALPTEL vừa bị nhiễm virus WUB. Các tin nhắn của mạng này bị chèn từ “WUB” theo nguyên tắc sau:
• Đầu tin nhắn có thể không được chèn lần nào;
• Cuối tin nhắn có thể không được chèn lần nào;
• Giữa các từ của tin nhắn chèn ít nhất một lần.
Ví dụ nội dung tin nhắn là “I AM NAM” có thể bị chuyển thành “WUBWUBIWUBAMWUBNAM” nhưng không thể “WUBIWUBAM NAMWUB”.
Em hãy viết chương trình giúp nhà mạng khôi phục lại nội dung tin nhắn ban đầu từ tin nhắn đã bị virus phá hoại.
Dữ liệu vào: Cho ở file MESS.INP gồm một dòng duy nhất ghi nội dung tin nhắn đã bị virus phá hoại dài không quá 255 kí tự chỉ gồm các chữ cái thuộc tập [‘A’ .. ‘Z’].
Kết quả: ghi ra file MESS.OUT gồm một dòng duy nhất ghi nội dung tin nhắn ban đầu.
Các từ trong tin nhắn cách nhau một dấu cách.
Ví dụ:
MESS.INP MESS.OUT
WUBWUBABCWUB ABC
WUBWEWUBAREWUBWUBTHEWUBCHAMPIONS WE ARE THE CHAMPIONS
Câu 2: Kiểm tra
Một biểu thức số học chứa dấu mở ngoặc ‘(‘ và đóng ngoặc ‘)’ xác định một cách đặt ngoặc đúng, nếu thỏa mãn các điều kiện sau:
- Tổng số ngoặc đóng = tổng số ngoặc mở
- Đi từ trái qua phải, ở bất cứ vị trí nào số ngoặc đóng phải nhỏ hơn hoặc bằng số ngoặc mở
Yêu cầu: Em hãy xác định một biểu thức số học có phải là một cách đặt ngoặc đúng không?
Dữ liệu : vào từ tệp kiemtra.inp có cấu trúc như sau:
- Dòng đầu là số test n (0<n<100).
- N dòng tiếp theo, mỗi dòng là một dãy các biểu thức số học.
Kết quả: ghi ra tệp kiemtra.out gồm n dòng, mỗi dòng là kết quả của một test tương ứng, xuất “YES” nếu cách đặt ngoặc đúng, ngược lại xuất “NO”
Ví dụ:
KIEMTRA.INP KIEMTRA.OUT
3
2(3+5)
(2x+1)(4y+2)
(2x-1))(3y-2) YES
YES
NO
Câu 3 đường đi ngắn nhất
Cho một bảng vuông kích thước N*N (với 2 < N < 100). Mỗi ô trong bảng ghi một số nguyên a (a< ). Một robot di chuyển từ ô [1,1] xuống ô [n,n], mỗi bước robot chỉ có thể di chuyển sang ô cạnh bên phải hoặc bên dưới so với ô nó đang đứng.
Yêu cầu: Tìm đường đi của robot sao cho tổng đường đi là ngắn nhất.
Dữ liệu vào: Cho trong tệp robot.inp
- Dòng đầu ghi giá trị số n.
- Dòng thứ i trong n dòng tiếp theo ghi n số trên dòng i của bảng theo thứ tự từ trái qua phải.
Dữ liệu ra: Ghi ra tệp robot.out một số nguyên là tổng đường đi ngắn nhất tìm được.
Ví dụ:
robot.inp robot.out (Giải thích: đường đi có tổng bé nhất:
(1,1) => (2,1) => (2,2) => (2,3) => (3,3)
có tổng: 1 + 5 + 4 + 2 + 2 = 14)
3
1 8 5
5 4 2
1 25 2 14
Mạng viễn thông ALPTEL vừa bị nhiễm virus WUB. Các tin nhắn của mạng này bị chèn từ “WUB” theo nguyên tắc sau:
• Đầu tin nhắn có thể không được chèn lần nào;
• Cuối tin nhắn có thể không được chèn lần nào;
• Giữa các từ của tin nhắn chèn ít nhất một lần.
Ví dụ nội dung tin nhắn là “I AM NAM” có thể bị chuyển thành “WUBWUBIWUBAMWUBNAM” nhưng không thể “WUBIWUBAM NAMWUB”.
Em hãy viết chương trình giúp nhà mạng khôi phục lại nội dung tin nhắn ban đầu từ tin nhắn đã bị virus phá hoại.
Dữ liệu vào: Cho ở file MESS.INP gồm một dòng duy nhất ghi nội dung tin nhắn đã bị virus phá hoại dài không quá 255 kí tự chỉ gồm các chữ cái thuộc tập [‘A’ .. ‘Z’].
Kết quả: ghi ra file MESS.OUT gồm một dòng duy nhất ghi nội dung tin nhắn ban đầu.
Các từ trong tin nhắn cách nhau một dấu cách.
Ví dụ:
MESS.INP MESS.OUT
WUBWUBABCWUB ABC
WUBWEWUBAREWUBWUBTHEWUBCHAMPIONS WE ARE THE CHAMPIONS
Câu 2: Kiểm tra
Một biểu thức số học chứa dấu mở ngoặc ‘(‘ và đóng ngoặc ‘)’ xác định một cách đặt ngoặc đúng, nếu thỏa mãn các điều kiện sau:
- Tổng số ngoặc đóng = tổng số ngoặc mở
- Đi từ trái qua phải, ở bất cứ vị trí nào số ngoặc đóng phải nhỏ hơn hoặc bằng số ngoặc mở
Yêu cầu: Em hãy xác định một biểu thức số học có phải là một cách đặt ngoặc đúng không?
Dữ liệu : vào từ tệp kiemtra.inp có cấu trúc như sau:
- Dòng đầu là số test n (0<n<100).
- N dòng tiếp theo, mỗi dòng là một dãy các biểu thức số học.
Kết quả: ghi ra tệp kiemtra.out gồm n dòng, mỗi dòng là kết quả của một test tương ứng, xuất “YES” nếu cách đặt ngoặc đúng, ngược lại xuất “NO”
Ví dụ:
KIEMTRA.INP KIEMTRA.OUT
3
2(3+5)
(2x+1)(4y+2)
(2x-1))(3y-2) YES
YES
NO
Câu 3 đường đi ngắn nhất
Cho một bảng vuông kích thước N*N (với 2 < N < 100). Mỗi ô trong bảng ghi một số nguyên a (a< ). Một robot di chuyển từ ô [1,1] xuống ô [n,n], mỗi bước robot chỉ có thể di chuyển sang ô cạnh bên phải hoặc bên dưới so với ô nó đang đứng.
Yêu cầu: Tìm đường đi của robot sao cho tổng đường đi là ngắn nhất.
Dữ liệu vào: Cho trong tệp robot.inp
- Dòng đầu ghi giá trị số n.
- Dòng thứ i trong n dòng tiếp theo ghi n số trên dòng i của bảng theo thứ tự từ trái qua phải.
Dữ liệu ra: Ghi ra tệp robot.out một số nguyên là tổng đường đi ngắn nhất tìm được.
Ví dụ:
robot.inp robot.out (Giải thích: đường đi có tổng bé nhất:
(1,1) => (2,1) => (2,2) => (2,3) => (3,3)
có tổng: 1 + 5 + 4 + 2 + 2 = 14)
3
1 8 5
5 4 2
1 25 2 14