DRŽAVNO NATJECANJE 2015. – Drugi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 1. zadatak

Svaka DNA molekula je lanac takozvanih nukleotida, a svaki nukleotid može biti jedan od četiri vrste: adenin (A), citozin (C), gvanin (G) i timin (T).

Dakle jedan DNA lanac možemo predstaviti nizom znakova gdje je svaki znak veliko slovo A, C, G ili T.

Sekvenciranje DNA je postupak određivanja redoslijeda nukleotida u nepoznatoj molekuli DNA, a sekvenciranje dugačkih lanaca DNA je vrlo zahtjevan postupak.

Jedna metoda sekvenciranja dugačkih molekula najprije napravi puno jednakih kopija te nepoznate molekule, zatim izloži sve te molekule zračenju koje ih sve nasumce razbije na kraće lance.

Neki od tih kraćih lanaca se sekvenciraju te se pokušava donekle odrediti originalna molekula ‘slaganjem’ kraćih lanaca – takozvanih blokova.

Pritom se često koristi informacija o nizovima za koje znamo da ih originalna DNA sigurno sadrži – takozvanim uzorcima.

Podzadatak A: Zadani su DNA lanci A1, A2,… An, koje nazivamo blokovi. Zadani su DNA lanci U1, U2, … Um, koji nazivamo uzorci.

Potrebno je za svaki uzorak odrediti da li ga je moguće dobiti spajanjem blokova. P

rilikom gradnje uzorka možemo blokove spajati proizvoljnim redoslijedom, te svaki od blokova Ak možemo koristiti nula, jednom ili više puta.

Dozvoljeno je da se blokovi prilikom spajanja preklapaju (ako imaju ista slova na pozicijama na kojima se preklapaju).

Napišite program koji će, za svaki zadani uzorak, odrediti da li ga je moguće na ovaj način dobiti spajanjem zadanih blokova.

Podzadatak B: Zadani su novi blokovi B1, B2,…, Bn. Zadan je jedan uzorak X.

Potrebno je spajajući što je moguće manje blokova Bk napraviti DNA lanac Y koji sadrži (kao niz uzastopnih znakova) uzorak X.

Prilikom gradnje lanca Y možemo blokove spajati proizvoljnim redoslijedom, te svaki od blokova Bk možemo koristiti nula, jednom ili više puta.

Nije dozvoljeno da se blokovi prilikom gradnje lanca preklapaju.

Napišite program koji će odrediti koliko je najmanje blokova potrebno da se napravi takav lanac te također određuje jedan način izgradnje lanca.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj N (1 ≤ N ≤ 100 ) - broj zadanih blokova u svakom od podzadataka.

Sljedećih N redova sadrže blokove koji se koriste u podzadatku A. U K-tom od tih redova nalazi se blok Ak

- niz od najviše 100 velikih slova.

U sljedećem redu nalazi se prirodni broj M (1 ≤ M ≤ 20 ) – broj zadanih uzoraka u podzadatku A. U K- tom od sljedećih M redova nalazi se uzorak Uk - niz od najviše 100 velikih slova.

Sljedećih N redova sadrže blokove koji se koriste u podzadatku B. U K-tom od tih redova nalazi se blok Bk

- niz od najviše 100 velikih slova.

U sljedećem redu nalazi se uzorak X – zadani uzorak u podzadatku B, također niz od najviše 100 velikih slova. Svi nizovi se sastoje od barem jednog slova, te se u njima pojavljuju se samo slova A, C, G ili T.

Izlazni podaci

U prvi red ispišite rješenje podzadatka A – niz od točno M znakova ‘0’ ili ‘1’. -ti po redu znak u nizu treba biti ‘1’ ' ako je moguće dobiti točno uzorak Uk spajanjem blokova uz dozvoljena preklapanja, a ‘0’ inače.

U sljedeća dva reda ispišite rješenje podzadatka B.

U drugi red potrebno je ispisati traženi najmanji mogući broj blokova S potrebnih da se od blokova (bez preklapanja) izgradi neki lanac Y koji sadrži uzorak .

U treći red potrebno je ispisati na koji način se Y može dobiti spajanjem S blokova. Točnije potrebno je ispisati M blokova redom kojim čine Y, odvojene s točno jednim znakom ‘|’ (vertikalna crta, ASCII 124) bez razmaka. Svaki od blokova mora biti jedan od blokova Ak iz ulaza.

Napomena: Rješenje podzadatka B će uvijek postojati, ali ne mora biti jedinstveno.

Primjeri test​ podataka

Ulaz

4
ACTG
CTGGG
TGG
GA
3
ACTGGGGACTG
GACTGG
TGGC
CCACTG
GG
CTACG
TTCA
ACTGGGGGCT

Izlaz

110
4
CCACTG|GG|GG|CTACG

Ulaz

1
ACCTG
4
ACCTG
AACCTG
ACCT
ACCTGACCTG
GGGTCCGTAAAAAAAAAGTC
AAAAA

Izlaz

1001
1
GGGTCCGTAAAAAAAAAGTC