Karkkien määrä on enintään $10^5$, ja jokaisen karkin hinta ja $x$ on välillä $1 \dots 10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.
Toteuta tiedostoon
candies.py
funktio solve
, joka ilmoittaa, montako karkkia voit ostaa enintään.def solve(prices, x): # TODO if __name__ == "__main__": print(solve([1, 1, 1, 1], 2)) # 2 print(solve([2, 5, 3, 2, 8, 7], 10)) # 3 print(solve([2, 3, 4, 5], 1)) # 0 print(solve([2, 3, 4, 5], 10**9)) # 4 print(solve([10**9, 1, 10**9], 10**6)) # 1Selitys: Ensimmäisessä esimerkissä voit ostaa mitkä tahansa kaksi karkkia. Toisessa esimerkissä voit ostaa kolme karkkia, esimerkiksi listan kolme ensimmäistä karkkia, jotka maksavat yhteensä $10$. Kolmannessa esimerkissä et voi ostaa mitään karkkia, koska jokainen maksaa enemmän kuin $1$.