Najdłuższy podciąg rosnący

25.11.2009 - Karol Konaszyński
TrudnośćTrudność

Zamek

Limit czasowy: 8s, Limit pamięciowy: 32MB.

Grasz w grę Zamek. W każdej turze możesz awansować swój zamek na pewien poziom i za każdy awans (nieważne o ile poziomów, ważne, że o co najmniej 1) dostajesz 1 punkt zwycięstwa. Udało ci się jednak podejrzeć pliki konfiguracyjne gry i wiesz, jakie będą kolejne poziomy, na które, w kolejnych turach, będzie można awansować zamek. Ponadto wiesz, że w $ k $-tej turze wykorzystanie możliwości awansu kosztuje $ 2^{k} $ dukatów. Policz więc, ile punktów zwycięstwa uda ci się zdobyć. Jeśli masz więcej możliwości, wybierz tę o najmniejszym koszcie. (Zauważ, że im wcześniej się zdecydujesz na awans, tym lepiej!). Zaczynasz od poziomu 0.

Wejście

W pierwszej linii wejścia znajdziesz ilość gier, które chcesz rozegrać. W każdej następnej znajduje się ilość tur $ n $ $ (n \leq 5*10^{5}) $, a następnie $ n $ liczb $ a_{i} $ $ (1\ \leq a_{i}\ \leq 10^{9}) $ określające na jaki poziom możesz awansować zamek w $ i $-tej turze.

Wyjście

Dla każdej gry wypisz jedną linię: niech zaczyna się od liczby $ m $ oznaczającej ilość punktów zwycięstwa, które możesz uzyskać, a następnie $ m $ liczb oznaczających kolejne poziomy (bez zerowego), które będziesz uzyskiwać, grając optymalnie.

Przykład

Dla danych wejściowych:

3
6 1 5 2 7 7 10
3 3 2 1
4 1 2 3 4

Poprawną odpowiedzią jest:

4 1 5 7 10
1 3
4 1 2 3 4

Wyjaśnienie:
W pierwszym teście awansujemy kolejno: 0 -> 1 -> 5 -> 7 -> 10. Koszt takiego przedsięwzięcia to 2+4+16+64 = 86.
W drugim możemy tylko raz awansować, więc robimy to najniższym kosztem = 2.
W trzecim uda nam się zdobyć pełen komplet punktów.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.


 

Badanie DNA

Limit czasowy: 8s, Limit pamięciowy: 32MB.

Jesteś biologiem (biolożką) i badasz łańcuchy DNA. Twój zespół postanowił zająć się porównywaniem sekwencji DNA różnych gatunków małp oraz człowieka. Każda sekwencja DNA składa się, według was, z niewielkiej (kilka miliardów) ilości fragmentów, które często powtarzają się w DNA ssaków. Najprościej rzecz ujmując, DNA to ciąg fragmentów, z których każdy ma pewien numer. Ponadto te fragmenty są tak ustalone, że, jakimś cudem, genom człowieka składa się z różnych fragmentów (tzn. żaden się nie powtarza). Napisz program, który dla zadanych sekwencji DNA będzie porównywał je z DNA człowieka i wypisze, jaki jest ich najdłuższy wspólny podciąg fragmentów.

Wejście

W pierwszej linii wejścia znajdują się liczby $ n $ i $ s $ $ (n \leq 10^{5}, s \leq 10) $ oznaczające odpowiednio: ilość fragmentów w DNA człowieka i ilość gatunków małp, których sekwencje chcesz rozpatrzyć. W następnej linii znajduje się $ n $ różnych liczb całkowitych dodatnich mniejszych od $ 10^{9} $, czyli numerów fragmentów, które składają się na DNA człowieka. W każdej z $ s $ następnych linii znajdziesz liczbę $ m $ $ (m \leq 10^{5}) $ będącą długością kolejnej sekwencji i $ m $ liczb oznaczających numery kolejnych fragmentów w tej sekwencji.

Wyjście

Wypisz, w pojedynczej linii, $ s $ liczb całkowitych, z których $ i $-ta określa długość najdłuższego wspólnego podciągu fragmentów sekwencji człowieka i $ i $-tego gatunku małpy.

Przykład

Dla danych wejściowych:

5 3
5 4 3 2 1
3 3 1 2
2 6 1
3 2 2 2

Poprawną odpowiedzią jest:

2 1 1

Wyjaśnienie do przykładu: Dla pierwszej sekwencji najdłuższy wspólny podciąg to, na przykład, 3 1, dla drugiej jednoelementowy 1, dla trzeciej tylko 2.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.


 

Klocki

Limit czasowy: 8s, Limit pamięciowy: 32MB.

Bajtuś ma dwa hobby - układanie wież z klocków i bawienie się liczbami. Ostatnio na gwiazdkę dostał zestaw klocków, na których były napisane liczby. Tych klocków było sporo, więc ułożenie wieży z nich złożonej wymagało dużo czasu i koncentracji. Gdy mu się to w końcu udało, paradoksalnie poczuł się dość smutny - bo cóż innego mógł jeszcze z nimi zrobić? Ale w pewnym momencie, gdy patrzył na liczby napisane na klockach, przyszedł mu do głowy pomysł. Postanowił ostrożnie usunąć niektóre klocki z wieży tak, żeby jak najwięcej spośród pozostałych klocków było "fajnych", czyli znajdowało się na takiej wysokości, na jaką wskazuje liczba napisana na klocku (klocek leżący bezpośrednio na ziemi jest na wysokości 1, następny na wysokości 2 i tak dalej). Sprawdź, ile, w danej wieży, najwięcej klocków może być fajnych.

Wejście

W pierwszej linii znajduje się liczba $ n $ $ (1 \leq n \leq 2*10^{5}) $, ilość klocków w wieży. W kolejnej linii znajduje się $ n $ liczb $ a_{i} $ $ (1 \leq a_{i} \leq n+1) $ określających liczbę napisaną na i-tym klocku.

Wyjście

Wypisz jedną liczbę całkowitą F określającycą maksymalną ilość fajnych klocków w wieży po usunięciu niektórych klocków.

Przykład:


Dla wejścia:

7
1 4 2 2 4 8 7

Poprawnym wyjściem jest:

3

Wyjaśnienie:

Po usunięciu klocka drugiego wieża będzie wyglądała tak: $ 1\ 2\ 2\ 4\ 8\ 7 $, czyli klocki o numerach 1, 2 i 4 będą na fajnych miejscach. Równie dobrze można też usunąć klocki 8 i 7. Gdybyśmy nic nie usuwali, byłyby dwa fajne klocki: 1 i 7.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

3.666665
Twoja ocena: Brak Ocena: 3.7 (15 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com