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)) # 1
Selitys: 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$.