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

Xét tập chữ cái A = {I, W, N}. Một từ là một dãy liên tiếp không quá 6 ký tự của A. Cho một danh sách L gồm m từ phân biệt. Mỗi từ trong danh sách được gán một trọng số dương ≤ 60000. Những từ không có trong danh sách mang trọng số 0. Xét một xâu S chỉ gồm các ký tự trong A. Trọng số của xâu S được tính bằng tổng trọng số các từ trong S.
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 5 064. TR NG S XÂUXét tập chữ cái A = {I, W, N}. Một từ là một dãy liên tiếp không quá 6 ký tự của A.Cho một danh sách L gồm m từ phân biệt.• Mỗi từ trong danh sách được gán một trọng số dương ≤ 60000.• Những từ không có trong danh sách mang trọng số 0.Xét một xâu S chỉ gồm các ký tự trong A. Trọng số của xâu S được tính bằng tổng trọng số các từtrong S. (Các từ trong S được liệt kê dưới dạng các đoạn ký tự liên tiếp của S tính cả việc giao nhauvà chứa nhau)Yêu cầu: Cho trước danh sách L và độ dài n ≤ 100. Hãy tìm xâu S = S1S2...Sn có trọng số nhỏnhất. Nếu có nhiều xâu S đều có trọng số nhỏ nhất thì chỉ cần chỉ ra một xâu.Dữ liệu: Vào từ file văn bản STR.INP• Dòng 1: Ghi hai số n, m cách nhau một dấu cách.• m cặp dòng tiếp theo, cặp dòng thứ i gồm 2 dòng: ♦ Dòng thứ nhất ghi từ thứ i trong danh sách L ♦ Dòng thứ hai ghi trọng số của từ đóKết quả: Ghi ra file văn bản STR.OUT gồm 2 dòng:• Dòng 1: Ghi trọng số của từ S tìm được• Dòng 2: Ghi xâu ký tự SVí dụ: STR.INP STR.OUT STR.INP STR.OUT 8 10 62 88 98 I WWIWWIWW W IWIWIWIW 13 10 W I 6 10 N N 12 30 II WI 6 1 NI WW 6 10 IIN II 13 11 WWW WIW 7 2 WNN IWI 23 3 NWW 18 NWN 0 74 065. PH MAY M NNgười dân thành phố Byteland có rất nhiều điều kiêng kỵ trong cuộc sống. Theo quan điểm của họ,các số 2, 6, 13 và nhiều số khác không mang lại điều may mắn. Trong khi đó, các số 3, 5, 7 lại rấtđược ưa chuộng. Những ngôi nhà có số mà khi phân tích ra thừa số nguyên tố chỉ chứa các thừa số3, 5, 7 được coi là may mắn và được mua rất nhanh.Sau một thời gian dài thảo luận, Hội đồng thành phố quyết định đánh số tất cả các ngôi nhà trên mộtđường phố mới mở bằng các số may mắn liên tiếp nhau, biến phố đó thành một phố may mắn. Kýhiệu dãy các số may mắn là X1, X2, X3, X4, ... Khi đó các nhà bên trái sẽ mang số X1, X3, X5. Còndãy nhà bên phải sẽ mang số X2, X4, X6, ... Toàn bộ đường phố có không quá 4000 nhà.Hãy xác định xem một số cho trước có phải là một số nhà ở phố may mắn không. Nếu đúng thìcho biết nhà đó nằm ở bên phải hay bên trái của phố.Dữ liệu: Vào từ file văn bản STREET.INP gồm không quá 100000 dòng, mỗi dòng chứa một sốnguyên dương không quá 18 chữ số.Kết quả: Ghi ra file văn bản STREET.OUT, gồm nhiều dòng, mỗi dòng tương ứng với một số ởfile dữ liệu vào và chứa một trong ba chữ cái L, R, N tương ứng với nhà bên trái, bên phải haykhông phải số nhà ở phố may mắn.Lưu ý: Dãy số may mắn được tính bắt đầu từ X1=3.Ví dụ: STREET.INP STREET.OUT 5 R 3 L 4 N 98415 R 12814453125 L 75 066. TÍN HI U GIAO THÔNGTrong một thành phố có:• m đường phố (hai chiều) song song chạy thẳng dọc theo hướng Tây↔Đông, để tiện, ta gọi các đường phố đó là H1, H2,..., Hm theo thứ tự từ Bắc xuống Nam.• n đường phố (hai chiều) song song chạy thẳng theo hướng Bắc↔Nam, ta gọi các đường phố đó là V1, V2, ..., Vn theo thứ tự từ Tây sang ĐôngHai đường phố vuông góc bất kỳ cắt nhau tạo thành một nút giao thông. Ngoại trừ hai nút giaothông nằm ở vị trí góc Đông-Nam và góc Tây-Bắc những nút giao thông khác có thể gắn đèn tínhiệu giao thông hai trạng thái:0. Trạng thái EW: Xanh hướng Đông và Tây, Đỏ hướng Bắc và Nam.1. Trạng thái NS: Xanh hướng Bắc và Nam, Đỏ hướng Đông và Tây.Mỗi đèn tín hiệu có một chu kỳ thời gian riêng, cứ sau mỗi chu kỳ thời gian ...