Biznes#517

Biznes (Omówienie)

Zauważ, że po dniach liczba gotówki w automatach będzie się powtarzać, dlatego należy znaleźć maksimum wśród pierwszych dni.

Dla podzadania 1 maksymalna suma będzie albo po pierwszym, albo po drugim dniu, więc możemy po prostu wydobyć maksimum między a n-sum(a).

Dla podzadania 2 wystarczy symulować proces przez pierwsze dni i aktualizować maksimum. Złożoność: O(n \cdot x).

Dla podzadania 3 zauważ, że jeśli żaden z automatów nie zostanie opróżniony, gotówka rośnie liniowo. Automaty będą opróżniane nie więcej niż razy, więc możemy określić te momenty czasowe i symulować proces tylko dla tych momentów. Złożoność: O(n^2).

Dla podzadania 4 możemy symulować proces dla każdego z dni, jednak możemy utrzymywać całkowitą sumę gotówki po każdym dniu, używając formuł i liczby każdego a_i. W tym celu, przechodząc z dnia do dnia i+1, najpierw dodajemy do całkowitej sumy gotówki, a następnie odejmujemy dla każdego automatu, który teraz zawiera dolarów.

Dla ostatniego podzadania musimy połączyć rozwiązania z podzadań 3 i 4.