/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/mDhZ
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
import flash.events.Event;
import com.bit101.components.*;
// @see http://projecteuler.net/index.php?section=problems&id=
[SWF(frameRate=1)]
// unsolvedというよりは時間がかかりすぎて答えがでない。
// Javaに移植したら正答を出したので、時間のかかる再帰を展開して
// frameごとに実行すればいけるはず
public class Euler extends Sprite {
private var _tf : TextField;
public function Euler() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
// tr(solve2(3, 100));
// tr(solve(3, 100));
solve(14, 200000);
var g : int = getTimer();
tr((g - s) + " ms");
var pb : PushButton = new PushButton(this, 350, 10, "stop", function(e : Event) : void
{
removeEventListener(Event.ENTER_FRAME, onEnterFrame);
});
pb.width = 100;
}
private var _t5 : Vector.<Array>;
private var _N : uint;
private var _M : uint;
private function solve(M : uint, N : uint) : void
{
_N = N;
_M = M;
var i : int, j : int, k : int;
_t5 = new Vector.<Array>(15);
for(i = 0;i < 15;i++)_t5[i] = [];
for(i = 0;i < 5;i++){
for(j = 0;j < 5;j++){
for(k = 0;k < 5;k++){
_t5[i + j + k].push([i, j, k]);
}
}
}
_C2 = [];
for(i = 0;i <= _N;i++){
var sum : uint = 0;
for(j = i >>> 1;j > 0;j >>>= 1)sum += j;
_C2.push(sum);
}
_ptns = srec(N, 0, [], N);
// tr(_ptns.join('\n'));
// tr(_ptns.length);
_p = 0;
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}
private var _C2 : Array;
private function onEnterFrame(e : Event) : void
{
var s : int = getTimer();
_ar = _ptns[_p];
var ret : uint = rec(_N, 0, 0, 0, 1, 0);
_sum += ret;
var g : int = getTimer();
tr(_p + "/" + _ptns.length, _ar, ret, (g - s) + "ms");
_p++;
if(_p == _ptns.length){
removeEventListener(Event.ENTER_FRAME, onEnterFrame);
tr(_sum);
}
}
private var _ptns : Array;
private var _p : uint;
private var _sum : uint = 0;
private function srec(left : int, acc : uint, _cur : Array, raw : uint) : Array
{
acc += raw - left;
if(left == 0){
return acc >= _M ? [_cur.concat()] : [];
}
var mod : int = left % 5;
var i : uint;
var ret : Array = [];
for(i = 0;mod + 5*i <= 12 && mod + 5*i <= left;i++){
ret = ret.concat(srec((left - (mod+5*i)) / 5, acc, _cur.concat(i), raw/5));
}
return ret;
}
private var _ar : Array;
private function rec(left : int, a : uint, b : uint, c : uint, base : uint, pos : uint) : Number
{
/*
if(pos == _ar.length){
return _C2[_N] - (_C2[a] + _C2[b] + _C2[c]) >= _M ? 1 : 0;
}
*/
var mod : int = left % 5;
var i : uint = _ar[pos];
var ret : Number = 0;
var abc : Array;
if(pos < _ar.length - 1){
var nb : uint = base * 5;
var nleft : uint = (left - (mod+5*i))/5;
for each(abc in _t5[mod+5*i]){
ret += rec(nleft,
a + abc[0] * base,
b + abc[1] * base,
c + abc[2] * base,
nb, pos + 1);
}
}else{
for each(abc in _t5[mod+5*i]){
if(_C2[_N] - (_C2[a + abc[0]*base] + _C2[b + abc[1] * base] + _C2[c + abc[2] * base]) >= _M){
ret++;
}
}
}
return ret;
}
private function check(a : uint, d : uint) : uint
{
var ret : uint = 0;
var i : uint;
for(i = a / d;i > 0;i /= d)ret += i;
return ret;
}
private function solve2(M : uint, N : uint) : Number
{
var n5 : uint = check(N, 5);
var n2 : uint = check(N, 2);
var ct : uint = 0;
var o : Object = {};
for(var a : uint = 0;a <= N;a++){
for(var b : uint = 0;b <= N - a;b++){
var c : uint = N - a - b;
var j5 : uint = n5 - (check(a, 5) + check(b, 5) + check(c, 5));
var j2 : uint = n2 - (check(a, 2) + check(b, 2) + check(c, 2));
if(j5 >= M && j2 >= M){
// if(j5 >= M){
var aa : uint = a;
var bb : uint = b;
var cc : uint = c;
var re : Number = 0;
for(var nn : uint = N;nn > 0;nn /= 5, aa /= 5, bb /= 5, cc /= 5){
re = re * 100 + int(nn / 5) - (int(aa / 5) + int(bb / 5) + int(cc / 5));
}
if(!o[re])o[re] = 0;
o[re]++;
// tr(a, b, c);
ct++;
}
}
}
for(var key : String in o){
tr(key, o[key]);
}
return ct;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
