Project Euler 267

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/o8qu
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=267
    public class Euler267 extends Sprite {
        private var _tf : TextField;
  
        // コインが投げられる確率は一定なので、
        // 1000回後の確率分布で10^9をこえる確率を最大化するようなものを探し、
        // そのときの境界の勝ち数(A)を求める。
        // あとはパスカルの三角形を使って10^9をこえる確率を計算する。
        public function Euler267() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve());
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        private function solve() : Number
        {
            // Alog(1+2f)+(1000-A)log(1-f)>=log(10^9)
            // をみたす最大のAを求める。
            var s : Number = 0.0001;
            var g : Number = 0.9999;
            // 0:-, 1:+
            do{
                var m : Number = (s + g) * 0.5;
                if(dA(m) < 0){
                    s = m;
                }else{
                    g = m;
                }
            }while(g - s > 0.000001);
            tr("f=" + s);
            tr("A=" + A(s));
            
            // パスカルの三角形を使って10^9をこえる確率を計算する。
            var p : Array = pascal(1000);
            var ret : Number = 0;
            for(var i : int = Math.ceil(A(s));i <= 1000;i++){
                ret += p[i];
            }
            
            return ret;
        }
        
        private function A(f : Number) : Number
        {
            var l9 : Number = Math.log(1000000000);
            return (l9 - 1000 * Math.log(1 - f)) / (Math.log(1 + 2 * f) - Math.log(1 - f));
        }
        
        private function dA(f : Number) : Number
        {
            var l9 : Number = Math.log(1000000000);
            return  1000 / (1 - f) * (Math.log(1 + 2 * f) - Math.log(1 - f)) - 
                    (l9 - 1000 * Math.log(1 - f)) * (2 / (1 + 2 * f) + 1 / (1 - f));
        }
        
        private function pascal(n : int) : Array
        {
            var seed : Array = [1];
            var i : int, j : int;
            for(i = 1;i <= n;i++){
                var next : Array = new Array(i+1);
                for(j = 0;j < next.length;j++)next[j] = 0;
                for(j = 0;j < seed.length;j++){
                    next[j] += seed[j] * 0.5;
                    next[j + 1] += seed[j] * 0.5;
                }
                seed = next;
            }
            return seed;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}