trang chủ / đề bài / icpcwf15_e

Tiến hóa song song

Đề bài

Mô tả

Năm 2178, người ta phát hiện ra sự sống ngoài hành tinh trên một hành tinh xa xôi. Hành tinh đó dường như chỉ có đúng một loài, và loài này không sinh sản như các loài động vật trên Trái Đất. Đáng kinh ngạc hơn nữa, cấu tạo di truyền của mọi cá thể đều giống hệt nhau!

Cấu tạo di truyền của mỗi cá thể là một dãy nucleotide. Có ba loại nucleotide, kí hiệu là A (Adenine), C (Cytosine) và M (Muamine). Theo một giả thuyết, sự tiến hóa trên hành tinh này xảy ra khi một nucleotide mới được chèn vào một vị trí nào đó trong dãy di truyền của một cá thể đang tồn tại. Nếu thay đổi này có lợi cho sự tiến hóa thì các cá thể mang dãy mới nhanh chóng thay thế các cá thể mang dãy cũ.

Ban đầu người ta cho rằng loài hiện nay tiến hóa theo cách trên từ một sinh vật duy nhất rất đơn giản, có dãy di truyền chỉ gồm một nucleotide, qua các lần đột biến như mô tả. Tuy nhiên, bằng chứng hóa thạch cho thấy có thể không phải như vậy. Hiện nay nhóm nghiên cứu mà bạn đang làm việc cùng đang muốn kiểm chứng khái niệm "tiến hóa song song": có thể thực ra đã có hai con đường tiến hóa diễn ra theo cách trên, và cuối cùng cả hai con đường đều tiến hóa thành một loài duy nhất đang sống trên hành tinh ngày nay. Nhiệm vụ của bạn là kiểm tra xem giả thuyết tiến hóa song song có phù hợp với vật liệu di truyền tìm thấy trong các mẫu hóa thạch mà nhóm đã thu thập hay không.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số dãy nucleotide tìm thấy trong các hóa thạch. Dòng thứ hai là dãy nucleotide của loài đang sống trên hành tinh. Mỗi dòng trong n dòng tiếp theo là một dãy nucleotide tìm thấy trong hóa thạch.

Dữ liệu ra

Hãy đưa ra một ví dụ về cách các dãy nucleotide trong hóa thạch tham gia vào hai con đường tiến hóa. Ví dụ bắt đầu bằng một dòng chứa hai số nguyên s1 và s2, lần lượt là số dãy hóa thạch thuộc con đường thứ nhất và con đường thứ hai. Tiếp theo là s1 dòng chứa các dãy thuộc con đường thứ nhất theo thứ tự thời gian (từ sớm nhất), rồi s2 dòng chứa các dãy thuộc con đường thứ hai, cũng theo thứ tự thời gian. Nếu có nhiều ví dụ, in ra một ví dụ bất kỳ. Nếu có một dãy có thể xuất hiện trong lịch sử di truyền của cả hai con đường, ví dụ của bạn phải gán nó vào đúng một con đường.

Nếu không thể giải thích toàn bộ vật liệu hóa thạch bằng hai con đường tiến hóa, in ra từ impossible.

Ràng buộc

  • 1≤n≤4000.
  • Mỗi dãy nucleotide là một xâu dài ít nhất 1 và không quá 4000 kí tự, chỉ gồm các chữ cái in hoa A, C và M.
  • Mọi dãy nucleotide, kể cả dãy của loài đang sống, đôi một khác nhau.

Ví dụ

Input Output Giải thích
5
AACCMMAA
ACA
MM
ACMAA
AA
A
1 4
MM
A
AA
ACA
ACMAA
Con đường thứ nhất chỉ có MM. Con đường thứ hai là A, AA, ACA, ACMAA: mỗi dãy nhận được từ dãy trước bằng cách chèn thêm nucleotide, và AACCMMAA nhận được từ MM cũng như từ ACMAA theo cách đó. Có nhiều đáp án đúng khác.
3
ACMA
ACM
ACA
AMA
impossible Ba dãy ACM, ACA, AMA đều dài 3 nên không dãy nào tiến hóa thành dãy khác được, nhưng chỉ có hai con đường.
1
AM
MA
impossible Không thể chèn nucleotide vào MA để được AM.
4
AAAAAA
AA
AAA
A
AAAAA
0 4
A
AA
AAA
AAAAA
Cả bốn dãy nằm trên một con đường, con đường kia không có dãy hóa thạch nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0