Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Najmniejszy leksykograficznie LIS (najmniejszy-lis) Memory limit: 64 MB Time limit: 1.00 s Napisz program, który dla danego ciągu liczb a1, a2, …, aN wyznaczy jego podciąg rosnący o największej długości. Ponieważ tak sprecyzowany problem ma niejednoznaczną odpowiedź, więc program Twój powinien wypisać taki podciąg, który jest dodatkowo najmniejszy leksykograficznie. Wejście W pierwszym wierszu podana jest długość ciągu N. W drugim wierszu zapisanych jest N liczb naturalnych a1, a2, …, aN, oddzielonych pojedynczym odstępem. Wyjście W pierwszym wierszu wyjścia powinna się znaleźć długość najdłuższego podciągu rosnącego. Natomiast w drugim wierszu najmniejszy leksykograficznie podciąg o takiej długości. Ograniczenia 1 ≤ N ≤ 106, 1 ≤ ai ≤ 106. Przykład Input Output Explanation 13 16 5 8 6 1 10 5 2 15 3 2 4 1 4 1 2 3 4 Istnieją trzy rosnące podciągi o długości 4, mianowicie: (5,8,10,15), (5,6,10,15) oraz (1,2,3,4). Ten trzeci jest oczywiście najmniejszy leksykograficznie.

Input	Output	Explanation
`13 16 5 8 6 1 10 5 2 15 3 2 4 1`	`4 1 2 3 4`	Istnieją trzy rosnące podciągi o długości 4, mianowicie: (5,8,10,15), (5,6,10,15) oraz (1,2,3,4). Ten trzeci jest oczywiście najmniejszy leksykograficznie.