This is the third in a series of puzzles that I will be posting every Monday at Midnight PST, and the final variant of "Take It or Leave It".
The first puzzle is located Here
The second puzzle is located Here
A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!
This week's game:
The host provides you with API access to a stack of 15,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $15,000 (no two envelopes contain the same dollar value).
You have 5 commands at your disposal:
Read(): Read the dollar figure in the envelope at the top of the stack.
Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.
Pass(): Pop off the envelope on the top of the stack.
Oracle(M): Returns the mean value of the next M envelopes in the stack, not including the one you can currently Read().
End(): Stop the game, and walk away the money currently in your wallet (your final score).
If you use Pass() on an envelope, the money within is lost forever.
If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing < $X. Take() on one of these envelopes will add $0 to your wallet.
If you use Oracle(M) on turn T, envelopes T+1 through T+M's mean will be returned. Oracle() is disabled until turn T+M.
If you use Take() or Pass() on turn T, $T is removed from your wallet.
Write an algorithm that finishes the game with the maximal amount of money.
Note 1: "Maximal" in this case means the median value in your wallet after N >= 1000 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.
Note 2: This puzzle has a significant difference from the first two iterations (namely, needing to pay for each envelope you take). Feel free to use any strategies from the first puzzles as a base, but be warned: They will probably (read: definitely) get a negative score without some kind of modification.
Edit: The prize condition has been removed, in light of this post on meta.