| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 6 | 5 | 5 | 83.333% |
Biolodzy zajmujący się genetyką porównawczą poszukują sekwencji genów zachowanych w pewnym zbiorze gatunków.
Niech zbiór liczb {1,2,…,n} oznacza geny - każdej liczbie odpowiada jeden gen. Każdy z gatunków określony jest permutacją liczb (1,2,…,n}, która oznacza uporządkowanie jego genów. Ciąg genów x1,x2,…,xk jest zachowaną sekwencją genów w zbiorze gatunków, jeśli jest on podciągiem (niekoniecznie spójnym) uporządkowania genów każdego z tych gatunków.
Zadanie
Napisz program, który:
W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite n i m oddzielone pojedynczym odstępem, przy czym 1 ≤ n ≤ 500 oraz 1 ≤ m ≤ 20. Liczba n oznacza liczbę genów, a m liczbę gatunków. Każda z następnych m linii zawiera genom kolejnego gatunku zapisany jako permutacja liczb 1,2,…,n pooddzielanych pojedynczymi odstępami.
Na wyjściu powinna zostać wypisana dokładnie jedna liczba całkowita równa długości najdłuższej zachowanej sekwencji genów.
5 3 5 3 4 1 2 2 5 4 3 1 5 2 3 1 4
3
Camp > POI Training Camp > ONTAK 2008 1-1번