Informatyka Podstawowa
Klasa I
Wejściówka z algorytmiki: test na testportal - Hasło: algo
Instrukcja warunkowa - ciąg dalszy
Pakowanie plecaka - ćwiczenia ZPE
ZADANIE:
Ćwiczenie / przykład
Bajtazar jedzie na rowerową wycieczkę krajoznawczą po Bajtocji. Zastanawia się teraz nad tym, jakie przydatne przedmioty wziąć ze sobą do plecaka w podróż. Niestety, ma przy tym bardzo mało czasu
i dlatego ustawił elementy potencjalnego ekwipunku w ciąg od najważniejszego do najmniej ważnego. Teraz jego metoda postępowania jest bardzo prosta: analizuje przedmioty po kolei i każdy przedmiot jest zabierany na wycieczkę, o ile tylko nie przekroczy udźwigu plecaka (oczywiście, licząc już razem
z poprzednio włożonymi przedmiotami). Pozostaje do ustalenia kluczowa sprawa: jaki plecak zabrać ze sobą na wycieczkę? Bajtazar podejrzewa, że jakoś sobie poradzi w podróży, jeśli tylko zabierze ze sobą co najmniej k przedmiotów. Niestety nasz bohater nie jest jeszcze pewien, ile dokładnie wynosi parametr k. Ile w takiej sytuacji co najmniej powinien wynosić udźwig jego plecaka, w zależności od parametru k?
Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna n (1 ≤ n ≤ 500 000) określająca liczbę potencjalnych przedmiotów, których zabranie na wycieczkę rozważa Bajtazar.
W drugim wierszu wejścia znajduje się ciąg n liczb naturalnych w1, w2, . . . , wn (1 ≤ wi ≤ 109 ) pooddzielanych pojedynczymi odstępami. Są to masy przedmiotów zgodnie z kolejnością ich rozważania przez Bajtazara.
Wynik: W pierwszym i jedynym wierszu wyjścia należy wypisać n liczb całkowitych pooddzielanych pojedynczymi odstępami: k-ta liczba powinna oznaczać minimalny udźwig plecaka, który gwarantuje, że Bajtazar zabierze ze sobą co najmniej k przedmiotów.
Podaj odpowiedź dla danych wejściowych:
6 (ilość przedmiotów)
10 8 3 30 5 10 (waga przedmiotu)
Test szyfry i wydawanie reszty hasło to: lekcja24