chromosome

Cerința

Î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 termină 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!

Date de intrare

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$.

Date de ieșire

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:

• pe prima linie a succesiunii $i$ se vor afișa două valori: $c_i$ – costul succesiunii $i$ și $p_i$ – numărul de cromozomi implicați în succesiunea $i$;
• pe a doua linie a setului $i$ se vor afișa cei $p_i$ cromozomi în ordinea în care aceștia apar în succesiunea $i$.

Restricții și precizări

• Se garantează pentru fiecare test că există cel puțin o succesiune de recombinări între cromozomii $u$ și $v$;
• Succesiunile se vor afișa în ordine crescătoare a costurilor, iar la costuri egale în ordine colexicografică a cromozomilor implicați;
• În cazul în care nu există $k$ succesiuni se vor afișa doar cele găsite;
• $1 \leq n \leq 1 \ 000$;
• $1 \leq m \leq 8 \ 000$;
• $1 \leq c \leq 10 \ 000$;
• $1 \leq k \leq 500$;
• $1 \leq u, v, x, y \leq n$.

Exemplu

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