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

Giám đốc một công ty trách nhiệm hữu hạn muốn xin chữ ký của ông Kiến trúc sư trưởng thành phố phê duyệt dự án xây dựng trụ sở làm việc của công ty. Ông kiến trúc sư trưởng chỉ ký vào giấy phép khi bà thư ký của ông ta đã ký duyệt vào giấy phép. Bà thư ký làm việc tại tầng thứ M của toà nhà trụ sở làm việc gồm M
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 2 012. XIN CH KÝ Giám đốc một công ty trách nhiệm hữu hạn muốn xin chữ ký của ông Kiến trúc sư trưởng thành phố phê duyệt dự án xây dựng trụ sở làm việc của công ty. Ông kiến trúc sư trưởng chỉ ký vào giấy phép khi bà thư ký của ông ta đã ký duyệt vào giấy phép. Bà thư ký làm việc tại tầng thứ M của toà nhà trụ sở làm việc gồm M tầng của Văn phòng Kiến trúc sư trưởng thành phố. Các tầng của toà nhà được đánh số từ 1 đến M, từ thấp đến cao. Mỗi tầng của toà nhà có N phòng được đánh số từ 1 đến N từ trái qua phải. Trong mỗi phòng chỉ có một nhân viên làm việc. Giấy phép chỉ được bà thư ký ký duyệt khi đã có ít nhất một nhân viên ở tầng M đã ký xác nhận. Ngoài bà thư ký, một nhân viên bất kỳ chỉ ký xác nhận vào giấy phép khi có ít nhất một trong các điều kiện sau được thoả mãn: a) Nhân viên đó làm việc ở tầng 1 b) Giấy phép đã được ký xác nhận bởi nhân viên làm việc ở cùng số phòng trong tầng sát dưới c) Giấy phép đã được ký xác nhận bởi nhân viên làm việc ở cùng số phòng trong tầng sát trên d) Giấy phép đã được ký xác nhận bởi nhân viên làm việc ở phòng bên cạnh Mỗi một nhân viên (kể cả bà thư ký) khi ký xác nhận đều đòi một khoản lệ phí. Hãy chỉ ra cách xin được chữ ký của Kiến trúc sư trưởng đòi hỏi tổng lệ phí phải trả là nhỏ nhất (giả thiết rằng riêng chữ ký của Kiến trúc sư trưởng không mất lệ phí). Dữ liệu vào từ file văn bản SIGN.INP • Dòng đầu tiên chứa ba số M, N, P (1 ≤ M ≤ 50; 1 ≤ N ≤ 100; 1 ≤ P ≤ N) ở đây P là số phòng bà thư ký. • Dòng thứ i trong số M dòng tiếp theo chứa N số nguyên dương theo thứ tự là lệ phí phải trả cho các nhân viên ở các phòng 1, 2, ..., N trên tầng i. Các số này không vượt quá 109 và giả thiết rằng tổng chi phí cần trả cũng không vượt quá 109. Kết quả: Ghi ra file văn bản SIGN.OUT Dòng đầu tiên ghi 2 số F, K theo thứ tự là chi phí cần trả và số lượng phòng cần đi qua. K dòng tiếp theo, mỗi dòng ghi số tầng và số phòng của một phòng theo thứ tự cần đi qua. (Các số trên 1 dòng của input/output file cách nhau ít nhất 1 dấu trống) Ví dụ: SIGN.INP SIGN.OUT 344 96 10 10 1 10 13 2 2 2 10 23 1 10 10 1 22 21 31 34 21 013. L C N M KIM CƯƠNG Lắc là một đồ trang sức rất được các cô gái ưa chuộng. Chính vì vậy mà chúng phải được chế tạo thật đẹp và đa dạng. Xét việc chế tạo lắc có m mắt xích, mỗi mắt được nạp một viên kim cương. Có n loại viên kim cương khác nhau, n ≤ 7; 2 ≤ m ≤ 27-n + 19. Hai lắc được gọi là khác nhau nếu ta không thể tìm cách đặt sao cho các mắt tương ứng có kim cương cùng loại. Lưu ý rằng lắc có hình vòng. Với m và n cho trước, hãy xác định xem có thể tồn tại bao nhiêu loại lắc khác nhau. Các loại kim cương được ký hiệu là A, B, C, ... Một cấu hình lắc được xác định bởi một xâu m ký tự A, B, C, ... và bắt đầu bằng ký tự nhỏ nhất. Cho số thứ tự l, hãy xác định cấu hình tương ứng (Các cấu hình được sắp xếp theo thứ tự từ điển). Dữ liệu: Vào từ file BRASLET.INP có dạng mn l1 l2 ... Kết quả: Đưa ra file BRASLET.OUT K - Số lượng lắc khác nhau s1 s2 ... (si xác định cấu hình lắc tương ứng với li) Ví dụ: BRASLET.INP BRASLET.OUT 43 21 2 AAAB 21 CCCC 22 014. R I S I Xét trò chơi rải sỏi với một người chơi như sau: Cho cây T và một đống sỏi gồm K viên ở mỗi bước người ta lấy 1 viên sỏi từ đống sỏi và đặt vào một nút lá tuỳ chọn Nếu nút p có r nút lá và tất cả và tất cả các nút lá đều có sỏi thì người ta gom tất cả các viên sỏi ở lá lại, đặt 1 viên ở nút p, xoá các nút lá của nó và hoàn trả r - 1 viên sỏi còn lại vào đống sỏi. Trò chơi kết thúc khi đã đặt được 1 viên sỏi vào nút gốc Nhiệm vụ đặt ra là theo cấu trúc của cây T, xác định số viên sỏi tối thiểu ban đầu để trò chơi có thể kết thúc bình thường. Cây có n nút ( N ≤ 400), nút gốc được đánh số là 1. Dữ liệu: vào từ file văn bản STONE.INP • Dòng đầu: số n • Dòng thứ i trong số n dòng tiếp theo có dạng: i m i1 i2 ... im. Trong đó m là số nút con của nút i; i1, i2, ..., im: Các nút con của nút i. Kết quả: đưa ra file STONE.OUT ...