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; } Ciąg bardzo rosnący (ciag-bardzo-rosnacy) Limit pamięci: 3 MB Limit czasu: 1.50 s Ciąg nazywamy bardzo rosnącym jeśli każdy następny jego wyraz jest co najmniej dwa razy większy od poprzedniego. Na przykład ciąg (1,3,6,20) jest bardzo rosnący, ale (1,3,5,20) nie. Jasio zainteresował się ciągami bardzo rosnącymi, ale obawia się, że jego ulubiony ciąg taki nie jest. Ile najmniej elementów musi z niego usunąć, aby stał się bardzo rosnący? Pomóż mu! Napisz program, który: wczyta ciąg, wyznaczy najmniejszą liczbę elementów jakie należy z niego usunąć, aby stał się bardzo rosnący i wypisze wynik na standardowe wyjście. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu Jasia. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych pooddzielanych pojedynczymi odstępami Ai – są to kolejne elementy ciągu Jasia. Wyjście W pierwszym (jedynym) wierszu wyjścia należy wypisać najmniejszą liczbę elementów, które należy wyrzucić z ciągu Jasia, aby stał się on bardzo rosnący. Ograniczenia 1 ≤ N ≤ 1 000 000, 1 ≤ Ai ≤ 1018. Przykład Wejście Wyjście Wyjaśnienie 8 1 3 5 6 1 4 20 8 4 Po wyrzuceniu z ciągu elementów 5, drugiej 1, 4 oraz 8 otrzymujemy ciąg bardzo rosnący (1,3,6,20).

Wejście	Wyjście	Wyjaśnienie
`8 1 3 5 6 1 4 20 8`	`4`	Po wyrzuceniu z ciągu elementów 5, drugiej 1, 4 oraz 8 otrzymujemy ciąg bardzo rosnący (1,3,6,20).