Page 32 - C:\Users\Admin\Desktop\Sach mem upweb\

100 Problems & Solutions Trang 32

b. Cho dãy b, xây dựng chương trình tìm dãy a.
Dữ liệu vào trong file NGICH.INP với nội dung:
Dòng đầu tiên là số n (1 <= n <= 10 000).
Các dòng tiếp theo là n số của dãy a, mỗi số cách nhau một dấu cách,
Các dòng tiếp theo là n số của dãy b, mỗi số cách nhau bởi một dấu cách.
Dữ liệu ra trong file NGHICH.OUT với nội dung:
n số đầu tiên là kết quả của câu a,
Tiếp đó là một dòng trống và sau đó là n số kết quả của câu b (nếu tìm được dãy a).

Bài 82/2001 - Gặp gỡ
(Dành cho học sinh THPT)
Trên một lưới ô vuông kích thước MN (M dòng, N cột) người ta đặt k rôbôt. Rôbôt thứ
i được đặt ở ô (xi,,yi). Mỗi ô của lưới có thể đặt một vật cản hay không. Tại mỗi bước,
mỗi rôbôt chỉ có thể di chuyển theo các hướng lên, xuống, trái, phải - vào các ô kề cạnh
không có vật cản. k rôbôt sẽ gặp nhau nếu chúng cùng đứng trong một ô. k rôbôt bắt
đầu di chuyển đồng thời và mỗi lượt cả k rôbôt đều phải thực hiện việc di chuyển (nghĩa
là không cho phép một rôbôt dừng lại một ô nào đó trong khi rôbôt khác thực hiện bước
di chuyển). Bài toán đặt ra là tìm số bước di chuyển ít nhất mà k rôbôt phải thực hiện để
có thể gặp nhau. Chú ý rằng, tùy trạng thái của lưới, k rôbôt có thể không khi nào gặp
được nhau.
Dữ liệu vào cho trong file văn bản MEET.INP, bao gồm:
+ Dòng đầu tiên chứa 3 số M,N và k (M,N<=50;k<=10)
+ k dòng sau, dòng thứ i gồm 2 số xi,yi là vị trí của rôbốt thứ i.
+ M dòng tiếp theo, mỗi dòng ghi N số gồm 0 và 1 mô tả trạng thái dòng tương ứng của
lưới, trong đó mỗi số mô tả một ô với quy ước: 0 - không có vật cản, 1 - có vật cản.
Các số trên cùng một dòng của file dữ liệu được ghi cách nhau ít nhất một dấu trắng.
Dữ liệu ra ghi lên file văn bản MEET.OUT: nếu k rôbôt không thể gặp nhau thì ghi một
dòng gồm một ký tự #, trái lại ghi k dòng, mỗi dòng là một dãy các ký tự viết liền nhau
mô tả các bước đi của rôbôt: U-lên trên, D-xuống dưới, L-sang trái, R-sang phải.
Ví dụ:
MEET.INP
4 6 2
1 1
4 6
0 1 1 0 0 0
0 0 0 0 0 1
0 0 1 0 0 1
0 1 0 1 0 0
MEET.OUT
DRRR
LUUL

Tin học & Nhà trường 100 Đề Toán - Tin học