chromosome
În cadrul unui experiment de inginerie genetică, un grup de cercetători desfășoară seturi de analize ample asupra unei secțiuni a genomului uman. Scopul studiului este selectarea unor succesiuni optime de hibridizări dintre doi cromozomi.
Genomul analizat are în componența sa n cromozomi interconectați prin mecanisme de crossing-over unidirecțional ce permit schimburi eficiente de gene care favorizează apariția mutațiilor și evoluția per ansamblu a genomului. Fiecare mecanism de crossing-over are un coeficient specific de transfer, c, care se definește prin numărul de gene pe care le poate transmite la un moment dat de la cromozomul x la cromozomul y.
Interesul cercetătorilor se concentrează asupra unei perechi speciale de cromozomi, u și v. Se definește drept succesiune validă de cromozomi o succesiune care începe cu cromozomul u
, se termina cu cromozomul v
și nu conține de 2 ori același cromozom. Se cere identificarea primelor k
succesiuni valide din punct de vedere al sumelor coeficienților de transfer.
Succes!
Pe prima linie a fișierului de intrare chromosome.in
se află valorile: n
– numărul de cromozomi per secțiunea de genom, m
– numărul de mecanisme de crossing-over, k
– numărul maxim de succesiuni de recombinări care trebuie determinate, u
și v
– perechea de cromozomi speciali.
Pe următoarele m
linii se află câte o tripletă de forma x
, y
, c
definită astfel: există mecanism de transfer unidirecțional de la cromozomul x
la cromozomul y
având coeficientul specific c
.
Pe prima linie a fișierului de ieșire chromosome.out
se va afișa valoarea r
– numărul de succesiuni de combinări găsite (k
sau mai puține), iar pe următoarele linii descrierile succesiunilor:
i
se vor afișa două valori: \(c_i\) – costul succesiunii i
și \(p_i\) – numărul de cromozomi implicați în succesiunea i
;i
se vor afișa cei \(p_i\) cromozomi în ordinea în care aceștia apar în succesiunea i
u
și v
;k
succesiuni se vor afișa doar cele găsite;1 <= n <= 1000
;1 <= m <= 8000
;1 <= c <= 10000
;1 <= k <= 500
;1 <= u, v, x, y <= n
.chromosome.in
6 8 4 6 4
5 3 3
5 1 1
6 5 1
2 1 4
2 6 3
3 4 2
1 3 1
6 1 2
chromosome.out
3
5 5
6 5 1 3 4
5 4
6 1 3 4
6 4
6 5 3 4
ID: 3
Upload: Sami
Input: chromosome.in/chromosome.out
Memory limit: 32MB/16MB
Time limit: 1.5s