chromosome

Time limit: 1.5s Memory limit: 32MB Input: chromosome.in Output: chromosome.out

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 nn 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, cc, care se definește prin numărul de gene pe care le poate transmite la un moment dat de la cromozomul xx la cromozomul yy.

Interesul cercetătorilor se concentrează asupra unei perechi speciale de cromozomi, uu și vv. Se definește drept succesiune validă de cromozomi o succesiune care începe cu cromozomul uu, se termină cu cromozomul vv și nu conține de 22 ori același cromozom. Se cere identificarea primelor kk 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: nn – numărul de cromozomi per secțiunea de genom, mm – numărul de mecanisme de crossing-over, kk – numărul maxim de succesiuni de recombinări care trebuie determinate, uu și vv – perechea de cromozomi speciali.

Pe următoarele mm linii se află câte o tripletă de forma xx, yy, cc definită astfel: există mecanism de transfer unidirecțional de la cromozomul xx la cromozomul yy având coeficientul specific cc.

Date de ieșire

Pe prima linie a fișierului de ieșire chromosome.out se va afișa valoarea rr – numărul de succesiuni de combinări găsite (kk sau mai puține), iar pe următoarele linii descrierile succesiunilor:

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

Restricții și precizări

  • Se garantează pentru fiecare test că există cel puțin o succesiune de recombinări între cromozomii uu și vv;
  • 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ă kk succesiuni se vor afișa doar cele găsite;
  • 1n1 0001 \leq n \leq 1 \ 000;
  • 1m8 0001 \leq m \leq 8 \ 000;
  • 1c10 0001 \leq c \leq 10 \ 000;
  • 1k5001 \leq k \leq 500;
  • 1u,v,x,yn1 \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 

Log in or sign up to be able to send submissions!