Programowanie zachłanne i dynamiczne (Część 1)
Materiały
Dla nauczyciela
Dla ucznia
Programowanie dynamiczne (MAIN2) Programowanie zachłanne (MAIN2)
Zadania
Zadanie 1. Pszczółki
Pszczoły rozmnażają się w specyficzny sposób: z niezapłodnionych jaj rodzą się samce (trutnie), a z zapłodnionych – samice (pszczoły). Rodzina pszczoły jest więc nietypowa – ma ona co prawda i ojca, i matkę, ale już tylko jednego dziadka i dwie babki. Janek dogłębnie bada ten temat i zastanawia się, ile męskich przodków żyło w rodzinie pszczoły w \(n\)-tym pokoleniu. Pomóż Jankowi dokonać obliczeń!
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą \(n\) (\(0 < n ≤ 10^5\)) – numer pokolenia pszczoły, dla którego szukamy liczby trutni.
Wyjście
Jedna liczba całkowita – liczba trutni w \(n\)-tym pokoleniu. Ponieważ liczba trutni bardzo szybko rośnie, wystarczy, że wypiszesz wynik mod \(10^9 + 7\).
Przykład
| Wejście | Wyjście |
|---|---|
| 5 | 5 |
Wskazówka
Liczba trutni w n-tym pokoleniu to n-ty wyraz ciągu Fibonacciego.
Zadanie 2. iGruszka
Firma iGruszka wyprodukowała nowy model smartfona. Telefon ma dotykowy ekran, całkiem niezłe parametry i śliczne logo w kształcie nadgryzionej gruszki. Zarząd firmy postanowił jak najwięcej zarobić na swoim sztandarowym produkcie. Przeprowadzono więc bardzo szczegółowe badania sprawdzające, jaką kwotę są gotowi zapłacić poszczególni klienci za aparat. Sprawdzono też, jaką liczbę telefonów mogą wyprodukować firmowe fabryki. Znając koszty produkcji urządzenia, wyniki badań klientów oraz liczbę możliwych do zamówienia smartfonów, oblicz najlepszą cenę urządzenia (tzn. taką, by firma iGruszka zarobiła jak najwięcej) oraz zysk firmy.
Wejście
Pierwszy wiersz wejścia zawiera trzy liczby całkowite \(s\), \(k\) oraz \(n\) – odpowiednio liczba możliwych do wyprodukowania telefonów, koszt jednego telefonu oraz liczba potencjalnych klientów (\(0 \leq s, k, n \leq 10^6\)). W kolejnych \(n\) liniach znajdują się maksymalne kwoty \(x_i\), które \(i\)-ty klient jest gotowy zapłacić za telefon (\(0 \leq x_i \leq 10^6\)).
Wyjście
Na wyjściu w jednym wierszu wypisz jedną liczbę całkowitą – maksymalny możliwy do uzyskania zysk firmy.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 8 5 15 11 10 12 16 |
14 |
Wskazówka
Zadanie to możemy rozwiązać metodą zachłanną – będziemy próbowali sprzedać jak największą liczbę telefonów za jak największą możliwą kwotę.
Zadanie 3. Spadek
Stary Jan ma dwóch synów. Ponieważ chłopcy często się kłócą, postanowił zapobiec następnym niesnaskom i sam podzieli majątek między nich. Jan chce rozdzielić majątek na dwie części tak, aby różnica wartości pomiędzy nimi była jak najmniejsza. Jeśli nie da się podzielić po równo, starszy syn otrzyma więcej.
Wejście
W pierwszym wierszu standardowego wejścia zapisano liczbę naturalną \(p\) (\(1 \leq p \leq 150\)) – liczbę składników majątku, a następnie ich wartości \(w_i\) (\(1 \leq w_i \leq 10 000\), \(i = 1, 2, 3 \dots p\)).
Wyjście
W jednym wierszu standardowego wyjścia zapisz kwoty wartości części majątku starszego i młodszego syna, rozdzielając je spacją.
Przykład
| Wejście | Wyjście |
|---|---|
| 4 2 2 2 5 |
6 5 |
| 5 10 5 10 5 5 |
20 15 |
Wskazówka
W tym zadaniu metoda zachłanna nie zadziała!