Đề thi chọn HSG tin

Kỳ thi chọn học sinh giỏi quốc gia


Hãy lập trình giải các bài toán sau: Bài1: Lắp ráp- Tên chương trình MATCH.PAS Một nhà máy sản xuất động cơ xe máy sản xuất được N pitông và N xilanh. Các pitông được đánh số chỉ từ 1 đến N, các xilanh cũng được đánh số từ 1 đến N. Mỗi pitông và mỗi xilanh đều được gắn với một chỉ số chất lượng là một số nguyên. Gọi chỉ số chất lượng của pitông i là ai, i:=1,2,3.. ,N, còn chỉ số chất lượng của xilanh j là bj, j=1,2,.. N. Nếu lắp ráp pitông i với xilanh j thì ta được một bộ pitông -xilanh hoàn chỉnh có đánh giá chất lượng là ai x bj. Yêu cầu: Hãy giúp nhà máy lắp giáp k bộ pitông-xilanh hoàn chỉnh với tổng đánh giá chất lượng là lớn nhất. Dữ liệu: Vào từ file văn bản MATCH.INP: -Dòng đầu tiên ghi hai số nguyên dương N và K (N<107, K

Bài 2- Nhà tù Tên chương trình PRISON.PAS Khu vực nhà giam dành cho tù binh Taliban và Al Qacda ở đảo Guantanamo có dạng một hình chữ nhật được chia thành một lưới M*N ô vuông cạnh 1 đơn vị độ dài (0Ta nói một ô được một Camera quan sát đầy đủ, nếu từ Camera đó có thể nhìn thấy mọi điểm trong của ô mà không bị một phòng giam nào che lấp. Yêu cầu: Hãy chỉ ra một phương án lắp một số ít nhất các camera có toạ độ nguyên ở trên biên để mọi ô ở sân đều được quan sát đầy đủ bởi ít nhất một Camera. Dữ liệu: Vào từ file văn bản PRISON.INP: Dòng đầu tiên chứa 3 số nguyên M,N,C lần lượt là số hàng, số cột của lưới và số phòng giam, 0

Bài 3: Đọc đĩa −Tên chương trình: DISK.PAS Các kỹ sư của một công ty Tin học đang thử nghiệm chế tạo đĩa từ có dung lượng thông tin cực lớn. Đĩa có nhiều đường ghi và khoảng cách giữa 2 đường ghi liên tiếp nhau là rất nhỏ. Các đường ghi được đánh số từ 0 đến N, từ ngoài vào trong. Đối với loại đĩa này, việc dịch chuyển đầu đọc từ một đường ghi sang đường ghi kế tiếp là rất khó vì khó đảm bảo độ chính xác cao cho các chuyển động cơ học trên khoảng cách quá bé do không có đủ thời gian để khởi động và phanh đầu đọc: Người ta thiết kế mạch điều khiển với 2 lệnh: Lệnh T và lệnh L. Lệnh T-đưa đầu đọc tiến lên phía trước P đường ghi (P<0). Ví dụ đầu đọc đang ở đường ghi K. Sau khi thực hiện lệnh T thì nó chuyển tới đường ghi số K+P. Lệnh T không áp dụng được khi K+P >N. Lệnh L đưa đầu đọc lùi Q đường ghi (Q> 0). Nếu đầu đọc đang ở đường ghi K, sau khi thực hiện lệnh L, đầu đọc sẽ chuyển tới đường ghi K-Q. Lệnh L không áp dụng được khi K-Q<0. Để di chuyển đầu đọc từ đường ghi U tới đường ghi V có thể phải áp dụng một dãy các lệnh T,L. Dãy m lệnh T(L) liên tiếp nhau được viết gọn dưới dạng Tm (Lm), trong đó m là số nguyên dương, m≥1 Yêu cầu: Với N, P và Q cho trước (0

Trước khi gấp hoặc sau khi mở, bản đồ được đặt để hướng Bắc chỉ lên trên. Khi mở bản đồ, các đường gấp để lại trên bản đồ có hai loại: Loại 1- vết gấp hằn lên trên, loại 0- vết gấp hằn xuống dưới. Các đường gấp theo hàng được đánh số từ 1 trở đi, từ trên xuống dưới, các đường gấp theo cột được đánh số từ trái sang phải từ 1 trở đi. Các mép trên và trái được coi là hàng 0 và cột 0. Một cách gấp bản đồ sẽ ứng với một xâu các ký tự A,B, C,D. Ví dụ, các cách gấp BAADC, sau khi mở bản đồ ta được bức tranh nêu ở hình 5 gồm một lưới các ô hình chữ nhật. Cạch của các ô trên các vết gấp được gọi là một đoạn và cũng chia thành 2 loại 0 và 1 tuỳ theo vết gấp là thuộc loại 0 hay 1. Các đoạn loại 1 được thể hiện bằng đoạn thẳng nét liền. Các đoạn loại 0 được thể hiện bằng đoạn thẳng đứt nét. Yêu cầu: Biết cách gấp, hãy xác định số đoạn loại 0 và số đoạn loại 1. Dữ liệu: Vào từ file văn bản MAP.INP gồm một dòng chứa xâu S xác định cách gấp, S không quá 50 ký tụ, Kết quả: Đưa ra file văn bản MAP.OUT số lượng đoạn loại 0 và số lượng đoạn loại 1. Ví dụ: MAP.INP BAADC MAP.OUT 24 28