ĐỀ THI CHỌN ĐỘI TUYỂN
OLYMPIC 30/04
MÔN: TIN HỌC – NĂM 2007
(Thời gian làm bài: 150 PHÚT)
Su dung pascal cung ok
NỘI DUNG ĐỀ
BÀI 1. RẦY NÂU
Bằng phương pháp chụp không ảnh xác định các vùng lúa đang bị rầy nâu phá hoại, trên ảnh chụp của vùng đất lớn hình chữ nhật, những vùng đất có màu xám là những vùng đất bị rầy nâu phá hoại, những vùng có màu xanh là những vùng đất còn tốt.
Để xác định vị trí của các vùng đất bị rầy nâu phá hoại hay không bị phá hoại, người ta chia hình chữ nhất trên thành lưới các ô vuông, với mỗi ô là một đơn vị diện tích.
Yêu cầu: Hãy lập trình xác định các vùng đất bị rầy nâu phá hoại, chỉ ra các vùng đất gồm các ô nào, tổng diện tích và diện tích từng vùng.
Dữ liệu: Đọc từ trong file văn bản RAY.INP gồm:
- Dòng đầu là kích thước vùng đất cho bởi hai biến M, N với
(1≤ M, N ≤ 250);
(1≤ M, N ≤ 250);
- M dòng tiếp theo, mỗi dòng chứa N cột cho biết ô đất có rầy hay không (1 nếu có rầy, 0 nếu không có rầy).
Kết quả: Ghi ra trong file văn bản RAY.OUT gồm:
- Dòng đầu ghi tổng diện tích vùng đất có rầy;
- Các dòng tiếp theo: số đầu tiên là diện tích các ô chung cạnh có rầy, kế tiếp là vị trí các ô có rầy.
Ví dụ:
RAY.INP | RAY.OUT |
5 6 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 | 7 4 [1, 1], [1, 2], [2, 2], [2, 3] 2 [4, 3], [4, 4] 1 [5, 1] |
BÀI 2. Tổng trở của mạch điện
Một mạch điện gồm N điện trở được mắc với nhau theo kiểu song song hoặc nối tiếp hoặc hỗn hợp cả hai kiểu. Người ta biểu diễn các mạch đó bằng một biểu thức cho dưới dạng một xâu ký tự với cú pháp và ngữ nghĩa được xác định thích như sau:
· Nếu Rx, Ry là hai điện trở mắc nối tiếp với nhau thì được biểu diễn là: Rx+Ry. Khi đó, điện trở của đoạn mạch mắc nối tiếp này được tính theo công thức: R = Rx + Ry;
· Nếu Rx, Ry là hai điện trở mắc song song với nhau thì được biểu diễn là: Rx*Ry. Khi đó, điện trở của đoạn mạch mắc song song này được tính theo công thức: 1/R = 1/Rx + 1/Ry.
Ví dụ, mạch điện bên dưới sẽ được biểu diễn dưới dạng biểu thức là:
(B+((A+(C*(D+G)))*(E+F)))
Yêu cầu: Cho một mạch điện thể hiện bằng một xâu ký tự theo cú pháp đã nêu ở trên, trong đó mỗi điện trở có tên là một ký tự khác nhau, cùng với trị số điện trở tuơng ứng của chúng. Lập trình kiểm tra tính đúng đắn của biểu thức mạch, nếu đúng thì tính điện trở của mạch.
Dữ liệu vào: Đọc từ file văn bản MACH.INP có cấu trúc như sau:
- Dòng đầu tiên là số N - số các điện trở trên mạch điện;
- Dòng thứ hai cho một xâu ký tự là biểu thức mạch tuân theo cú pháp mô tả mạch điện nói trên.
- N dòng tiếp theo, mỗi dòng gồm tên của điện trở (là một ký tự trong bảng chữ cái) và giá trị tương ứng của điện trở đó, cách nhau bởi một khoảng trống.
Kết quả ra: Ghi ra file văn bản MACH.OUT chỉ gồm một dòng chứa một số duy nhất là giá trị tính được của điện trở tổng toàn mạch.
Ví dụ:
MACH.INP | MACH.OUT |
7 (B+((A+(C*(D+G)))*(E+F))) A 10 B 5 C 8 D 4 E 8 F 6 G 4 | 12 |
BÀI 3. Di chuyển trên hình tròn
Trên mặt phẳng cho n hình tròn (n < 2000). Hình tròn thứ i được xác định bởi bộ ba số thực (x[i], y[i], R[i]) lần lượt là tọa tâm và bán kính của nó. Chi phí di chuyển trên mỗi hình tròn bằng 0. Chi phí di chuyển giữa hai hình tròn bằng khoảng cách gần nhất giữa chúng (nếu hai hình tròn không có điểm chung thì khoảng cách này bằng khoảng cách giữa 2 tâm trừ bán kính, ngược lại thì bằng 0).
Yêu cầu: Hãy tìm phương án di chuyển giữa hai hình tròn cho trước với chi phí ít nhất.
Dữ liệu vào: Đọc từ file văn bản HINHTRON.INP có cấu trúc:
- Dòng đầu tiên ghi số nguyên dương N (N ≤ 100) là số hình tròn;
- Dòng thứ 2 ghi số hiệu của hình tròn xuất phát và hình tròn kết thúc;
- Trong N dòng tiếp theo, mỗi dòng ghi thông tin về hình tròn thứ i, gồm 3 số thực lần lượt là hoành độ tâm, tung độ tâm của hình tròn và bán kính của nó.
Kết quả: ghi ra file văn bản HINHTRON.OUT
- Dòng thứ nhất ghi tổng khoảng cách di chuyển (2 số lẻ);
- Dòng thứ hai ghi số hiệu của các hình tròn trên đường đi tìm được.
Ví dụ:
|
|
----- HẾT -----
No comments:
Post a Comment