Take It or Leave It: A Game Show for Computers
CJam, $87,143 $700,424 $720,327 $727,580 $770,272

{0:T:M;1e4:E,:)mr{RM&gt;{RR(*MM)*-E0.032*220+R*&lt;{ERM--:E;R:MT+:T;}{E(:E;}?}&amp;}fRT}
[easi*]$easi2/=N


This program simulates the entire game multiple times and calculates the median.

How to run

I've scored my submission by doing 100,001 test runs:

$ time java -jar cjam-0.6.5.jar take-it-or-leave-it.cjam 100001
770272

real    5m7.721s
user    5m15.334s
sys     0m0.570s


Approach

For each envelope, we do the following:


Estimate the amount of money that will inevitably be lost by taking the envelope.

If R is the content and M is the maximum that has been taken, the amount can be estimated as R(R-1)/2 - M(M+1)/2, which gives the money all envelopes with contents X in the interval (M,R) contain.

If no envelopes had been passed yet, the estimation would be perfect.
Calculate the amount of money that will inevitably be lost by passing the envelope.

This is simply the money the envelope contains.
Check if the quotient of both is less than 110 + 0.016E, where E is the number of remaining envelopes (not counting envelopes that cannot be taken anymore).

If so, take. Otherwise, pass.