OLYMPIC TIN HỌC SINH VIÊN

LẦN THỨ XIII - 2004 

Khối thi: Cá nhân Chuyên 

Thời gian làm bài: 180 phút

Ngày thi: 8-5-2004

Nơi thi: Đại học Hàng Hải Hải Phòng

Dấu ??? được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài đặt chương trình.

Hình vuông la tinh cấp N là bảng vuông gồm NxN số được xếp thành N dòng và N cột sao cho mỗi dòng và mỗi cột đều là một hoán vị của các số tự nhiên 1, 2, …, N. Cho XYZ là một hình vuông la tinh cấp N. Một hình vuông la tinh cấp M ( 1 < M < N) nằm trên giao của M dòng liên tiếp và M cột liên tiếp nào đó của XYZ được gọi là hình vuông la tinh con của XYZ.

Yêu cầu: Cho XYZ là một hình vuông la tinh cấp N, hãy tính số lượng hình vuông la tinh con của nó.

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

• Dòng đầu chứa số nguyên N
• N dòng sau: mỗi dòng chứa N số nguyên trên dòng tương ứng của hình vuông la tinh.

Kết quả: ghi ra file văn bản LATIN.OUT:

• Dòng đầu tiên chứa số nguyên K - số hình vuông la tinh con tìm được.
• K dòng sau: mỗi dòng chứa 3 số nguyên I J M, trong đó I, J - tọa độ dòng, cột của phần tử ở góc trên trái của hình vuông la tinh con kích thước M. (Các dòng và cột của hình vuông la tinh đã cho được đánh số từ 1 đến N từ trên xuống dưới và từ trái qua phải)

Ví dụ:

Cuội rủ Bờm tham gia vào trò chơi sau đây. Thoạt tiên Cuội vẽ một đồ thị có hướng với N đỉnh và M cung. Sau đó Bờm phải phá hủy đồ thị này. Tại mỗi nước đi, Bờm chọn một đỉnh bất kỳ và có thể xóa các cung đi vào nó hoặc xóa các cung đi ra khỏi nó. Cuội đặt hai loại giá trị cho mỗi đỉnh i của đồ thị: W_i+ và W_i-. Nếu xóa các cung đi vào đỉnh I thì Bờm phải trả W_i+ (đồng), còn nếu xóa các cung đi ra khỏi đỉnh i thì Bờm phải trả W_i- (đồng).

Yêu cầu: Hãy giúp Bờm tìm cách xóa bỏ toàn bộ các cung của đồ thị với tổng chi phí phải trả là nhỏ nhất.

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

• Dòng đầu tiên chứa 2 số nguyên N và M (1 ≤ N ≤ 100; 1 ≤ M ≤ 5000);
• Dòng thứ 2 chứa các số W₁+, W₂+, …, W_N+.
• Dòng thứ 3 chứa các số W₁-, W₂-, …, W_N-.
• Mỗi một dòng trong số M dòng tiếp theo chứa 2 số nguyên là đỉnh đầu và đỉnh cuối của một cung tương ứng của đồ thị. Đồ thị có thể chứa khuyên (cung nối một đỉnh với chính nó) hoặc các cung lặp (các cung nối cùng một cặp đỉnh).

Hạn chế: Các số W_i+ và W_i- là các số dương không vượt quá 10⁶.

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Kết quả: ghi ra file văn bản DESTROY.OUT:

• Dòng đầu tiên ghi tổng chi phí theo cách xóa tìm được;
• Dòng thứ 2 ghi K là số nước đi theo cách xóa tìm được;
• Mỗi dòng thứ i trong K dòng tiếp theo mô tả một nước đi trong cách xóa tìm được và có dạng: ‘i +’ nếu Bờm xóa các cung đi vào đỉnh i, hoặc ‘i -’ nếu Bờm xóa các cung đi ra khỏi đỉnh i. Giữa chỉ số đỉnh i và dấu ‘+’ (hoặc ‘-’) có đúng một dấu cách.

Ví dụ:

Bộ nhớ của máy tính có dung lượng V byte được đánh số từ 0 đến V - 1. Các khối bộ nhớ đã được phân phối được xác định bởi các địa chỉ (a₁, b₁), (a₂, b₂), …, (a_N, b_N). Các khối này được sắp xếp theo địa chỉ và không giao nhau, nghĩa là 0 ≤ a_j ≤ b_j < a_j+1 < V. Hệ điều hành cần cung cấp một khối gồm M byte cho một yêu cầu mới xuất hiện. Nếu như không gian nhớ tự do với dung lượng như vậy không còn, thì hệ điều hành cần dịch chuyển một khối nào đó để giải phóng được một đoạn nhớ liên tục có độ dài đòi hỏi.

Yêu cầu: Tìm cách chọn khối bộ nhớ với dung lượng nhỏ nhất cần dịch chuyển để đáp ứng yêu cầu đặt ra. Trong trường hợp có nhiều cách lựa chọn, hãy đưa ra khối với địa chỉ đầu nhỏ nhất.

Dữ liệu: Vào từ file văn bản DEFRAG.INP: Đầu tiên là các số nguyên V N M, tiếp đến là N cặp số nguyên a₁, b₁, a₂, b₂, …, a_N, b_N. Hai số liên tiếp được ghi cách nhau ít nhất một dấu cách hoặc dấu xuống dòng.

Hạn chế: 0 ≤ N ≤ 100000, 1 ≤ V ≤ 1073741824.

Kết quả: ghi ra file văn bản DEFRAG.OUT:

• Chỉ số của khối cần di chuyển hoặc
• 0 nếu không cần di chuyển hoặc
• -1 nếu không có cách di chuyển (không thể giải phóng không gian nhớ yêu cầu).

Ví dụ: