150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 3

Hãy tìm vị trí ô xuất phát và một hành trình đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất. Dữ liệu: Vào từ file văn bản MAX.INP. Trong đó: Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
Nội dung trích xuất từ tài liệu:
150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 3 026. ĐƯ NG ĐI NHI U ĐI M NH TCho một bảng A kích thước m x n (1 ≤ m, n ≤ 100), trên đó ghi các số nguyên aij (aij ≤ 100). Mộtngười xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1). Xemhình vẽ: 1 2 6 7 9 7 6 5 6 7 1 2 3 4 2 4 7 8 7 6Yêu cầu: Hãy tìm vị trí ô xuất phát và một hành trình đi từ cột 1 sang cột n sao cho tổng các sốghi trên đường đi là lớn nhất.Dữ liệu: Vào từ file văn bản MAX.INP. Trong đó:• Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.• m dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải.Kết quả: Ghi ra file văn bản MAX.OUT. Trong đó:• Dòng 1: Ghi số điểm tối đa có được• n dòng tiếp theo, dòng thứ i ghi chỉ số hàng của ô thứ i trong hành trình.Các số trên 1 dòng trong Input/ Output file cách nhau ít nhất 1 dấu cáchVí dụ: 1 2 3 4 5 6 7 1 9 -2 6 2 1 3 4 2 0 -1 6 7 1 3 3 3 8 -2 8 2 5 3 2 4 1 -1 6 2 1 6 1 5 7 -2 6 2 1 3 7 MAX.INP MAX.OUT 57 41 9 -2 6 2 1 3 4 1 0 -1 6 7 1 3 3 2 8 -2 8 2 5 3 2 3 1 -1 6 2 1 6 1 2 7 -2 6 2 1 3 7 3 4 5 36 027. K HO CH THUÊ NHÂN CÔNGGiám đốc điều hành của một Công ty tin học cần xác định số lượng nhân công cần sử dụng trongmỗi tháng để thực hiện một dự án phát triển tin học. Ông giám đốc nắm được số lượng nhân côngtối thiểu cần cho mỗi tháng. Mỗi lần thuê hoặc sa thải một nhân công luôn mất thêm một khoản chiphí. Mỗi khi một thợ nào đó được thuê, anh ta luôn nhận được tiền lương ngay cả khi không làmviệc. Giám đốc nắm được chi phí để thuê một nhân công mới, chi phí sa thải một nhân công, lươngtháng của một nhân công. Vấn đề đặt ra cho giám đốc là phải xác định số lượng nhân công cần thuêhay sa thải trong mỗi tháng để cho chi phí thực hiện dự án là tối thiểu.Dữ liệu: Vào từ file văn bản PROJECT.INP.• Dòng đầu tiên ghi thời gian thực hiện dự án n (đơn vị tính: tháng, n ≤ 12)• Dòng thứ hai chứa ba số nguyên dương theo thứ tự là chi phí thuê một nhân công mới, lương tháng của một nhân công, chi phí sa thải một nhân công.• Dòng cuối cùng ghi n số nguyên dương d1, d2, ..., dn, trong đó di là số lượng nhân công cần sử dụng trong tháng i.Kết quả: Ghi ra file văn bản PROJECT.OUT• Dòng đầu tiên ghi chi phí tối thiểu tìm được• Mỗi dòng thứ i trong số n dòng tiếp theo ghi số si. Được hiểu là: ♦ Nếu si > 0 thì nó là số lượng nhân công cần thuê thêm ở tháng i. ♦ Nếu si < 0 thì si là số lượng nhân công cần sa thải ở tháng i ♦ Nếu si = 0 thì không có biến động nhân sự trong tháng i của dự ánVí dụ: PROJECT.INP PROJECT.OUT 3 199 4 56 10 10 9 11 0 1 37 028. DÃY CÁC HÌNH CH NH TGiả sử ABCD là một hình chữ nhật trên mặt phẳng toạ độ có các đỉnh: A (0, 0); B(0, 1); C(K, 1) và D(K, 0).Ta xem hình này là hình có số hiệu 1.Hình có số hiệu 2 xây dựng trên cạnh Bắc của hình 1 và cạnh kia gấp K lần. Hình có số hiệu 3 xâydựng trên cạnh tây của hình chữ nhật hợp các hình 1 và 2 và cạnh kia gấp K lần. Hình có số hiệu 4xây dựng trên cạnh nam của hợp các hình 1,2,3 và cạnh kia gấp K lần. Hình có số hiệu 5 xây dựngtrên cạ ...