Tiêu đề HSG-Lop-12-Quang-Ninh - 2023-2024.pdf ✅

Trang 3/4 Bài 3. Biến đổi gen (7 điểm) Nghiên cứu về ngoại hình sinh vật Z, các nhà khoa học quan tâm tới gen màu sắc và gen kích thước. Gen màu sắc có n1 trạng thái được đánh số thứ tự từ 1 tới n1, gen kích thước có n2 trạng thái được đánh số thứ tự từ 1 tới n2. Các nhà khoa học nhận thấy điều kì lạ là cứ sau mỗi giây thì sinh vật Z lại biến đổi cả về gen màu sắc lẫn gen kích thước, cụ thể: - Có m1 khả năng về biến đổi gen màu sắc, mỗi khả năng ứng với 2 số nguyên u, v (1 ≤ u, v ≤ n1 ) (u, v không nhất thiết phân biệt) nếu sinh vật đang ở trạng thái gen màu sắc u sau 1 giây có thể chuyển sang trạng thái gen màu sắc v hoặc ngược lại đang ở trạng thái v có thể chuyển sang trạng thái u. Giữa hai trạng thái gen màu sắc bất kì có thể biến đổi được sang nhau sau một thời gian nhất định. - Có m2 khả năng về biến đổi gen kích thước, mỗi khả năng ứng với 2 số nguyên u, v (1 ≤ u, v ≤ n2 ) (u, v không nhất thiết phân biệt) nếu sinh vật đang ở trạng thái gen kích thước u sau 1 giây có thể chuyển sang trạng thái gen kích thước v hoặc ngược lại đang ở trạng thái v có thể chuyển sang trạng thái u. Giữa hai trạng thái gen kích thước bất kì có thể biến đổi được sang nhau sau một thời gian nhất định. Khi sinh vật Z đang ở trạng thái gen màu sắc x (1 ≤ x ≤ n1 ) và trạng thái gen kích thước y (1 ≤ y ≤ n2 ) thì gọi là ở trạng thái ngoại hình (x, y). Khi sinh vật Z đang ở trạng thái ngoại hình (a, b), sau 1 giây có thể chuyển sang trạng thái ngoại hình (c, d) nếu và chỉ nếu sau 1 giây có thể đồng thời chuyển từ trạng thái màu sắc a sang c và trạng thái kích thước b sang d. Yêu cầu: Với mỗi trạng thái ngoại hình có thể đạt được nếu xuất phát ban đầu là trạng thái (1,1), xác định lượng thời gian tối thiểu (giây) để đạt được trạng thái đó. Sau đó tính tổng của tất cả lượng thời gian tối thiểu xác định được. Dữ liệu: Vào từ file văn bản GEN.INP • Dòng đầu chứa số nguyên n1, m1 (1 ≤ n1 ≤ 40000; 1 ≤ m1 ≤ 100000) là số trạng thái gen màu sắc và số khả năng biến đổi gen màu sắc; • m1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v (1 ≤ u, v ≤ n1 ) mô tả về một khả năng biến đổi trạng thái gen màu sắc; • Dòng tiếp theo chứa số nguyên n2, m2 (1 ≤ n2 ≤ 40000; 1 ≤ m2 ≤ 100000) là số trạng thái gen kích thước và số khả năng biến đổi gen kích thước; • m2 dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v (1 ≤ u, v ≤ n2 ) mô tả về một khả năng biến đổi trạng thái gen kích thước; Kết quả: Đưa ra file văn bản GEN.OUT một số nguyên là tổng của tất cả lượng thời gian tối thiểu xác định được chia dư cho 109 + 7. TECHACADEMY.EDU.VN