Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-10-23

SRM 485 Div1 Easy AfraidOfEven

00:43 | SRM 485 Div1 Easy AfraidOfEven - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 485 Div1 Easy AfraidOfEven - chokudaiの日記 SRM 485 Div1 Easy AfraidOfEven - chokudaiの日記 のブックマークコメント

問題

偶数怖い人が等差数列を割りまくる。元の数列で最小のやつを返す

解き方

上2つが決まれば全部決まる。入力が4つ以上で1000以下なので、出てくる数字は2000以下だから、全通り試せる

ソースコード

public class AfraidOfEven {
    int max = (int)1e7;
    public int[] restoreProgression(int[] seq)
    {
        int i;
        int len = seq.Length;
        for (int a = 1; a * seq[0] < max; a *= 2)
        {
            int[] res = new int[len];
            res[0] = a * seq[0];
            for (int b = 1; b * seq[1] < max; b *= 2)
            {
                res[1] = b * seq[1];
                for (i = 2; i < len; i++)
                {
                    res[i] = (int)(res[1] * (long)i - res[0] * (long)(i - 1));
                    if (!make(res[i], seq[i])) break;
                }
                if (i == len) return res;
            }
        }
        return new int[0];
    }

    bool make(int a, int b)
    {
        if (a % b != 0) return false;
        int c = a / b;
        if (c == 0) return false;
        if ((c & (c - 1)) == 0) return true;
        return false;
    }
}
 |