Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-09

SRM 358 Div1 Easy BrokenButtons

21:40 | SRM 358 Div1 Easy BrokenButtons - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 358 Div1 Easy BrokenButtons - chokudaiの日記 SRM 358 Div1 Easy BrokenButtons - chokudaiの日記 のブックマークコメント

問題

省略 各自読んでね!

方針

pageが50万以下なので、まぁ100万以下まで調べれば十分 ということで全探査

ソースコード

    public int minPresses(int page, int[] broken)
    {
        int res = Math.Abs(100 - page);
        int i;
        bool[] b = new bool[10];
        for (i = 0; i < broken.Length; i++) b[broken[i]] = true;
        if (!b[0]) res = Math.Min(res,page + 1);
        for (i = 1; i <= 1000000; i++)
        {
            int temp = Math.Abs(page - i) + i.ToString().Length;
            if (res <= temp) continue;
            int t = i;
            while (t != 0)
            {
                if (b[t%10]) break;
                t /= 10;
            }
            if (t == 0)
            {
                //Console.WriteLine(i + " " + temp);
                res = temp;
            }
        }
        return res;
    }

SRM 466 Div1 Medium LotteryPyaterochka

21:19 | SRM 466 Div1 Medium LotteryPyaterochka - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 466 Div1 Medium LotteryPyaterochka - chokudaiの日記 SRM 466 Div1 Medium LotteryPyaterochka - chokudaiの日記 のブックマークコメント

問題

たて5、横nの5n個のマスがあります。このうち5個があたりです。同じ行に3つあたりがあると嬉しいです。nが与えられるとき、この確率を求めなさい。n<100

方針

まぁ適当にDPすればおしまい

ソースコード

    public double chanceToWin(int N)
    {
        int i, j, k, l, m, n;
        double[,,] dp = new double[6, 6, 2]; //nokori retu flag
        for (i = 0; i < 6; i++) for (j = 0; j < 6; j++) for (k = 0; k < 2; k++) dp[i, j, k] = 0;
        dp[0, 0, 0] = 1;
        double res = 0;
        for (i = 0; i < N; i++)
        {
            for (j = 0; j < 5; j++)
            {
                double[, ,] nextdp = new double[6, 6, 2];
                double nokori = 5 * N - 5 * i - j;
                for (l = 0; l < 6; l++)
                {
                    for (m = 0; m < 6; m++)
                    {
                        for (n = 0; n < 2; n++)
                        {
                            if (dp[l, m, n] == 0) continue;
                            if (l!=5)
                            {
                                double get = (5 - l) / nokori;
                                int nextm = m + 1;
                                int nextn = n;
                                if (nextm >= 3) nextn = 1;
                                nextdp[l + 1, nextm, nextn] += dp[l, m, n] * get;
                            }
                            if (true)
                            {
                                double get = 1 - (5 - l) / nokori;
                                int nextm = m;
                                int nextn = n;
                                nextdp[l, nextm, nextn] += dp[l, m, n] * get;
                            }
                        }
                    }
                }
                dp = (double[, ,])nextdp.Clone();
            }
            for (l = 0; l < 6; l++)
            {
                for (m = 1; m < 6; m++)
                {
                    for (n = 0; n < 2; n++)
                    {
                        dp[l, 0, n] += dp[l, m, n];
                        dp[l, m, n] = 0;
                    }
                }
            }
        }
        for (l = 0; l < 6; l++)
        {
            for (m = 0; m < 6; m++)
            {
                res += dp[l, m, 1];
            }
        }
        return res;
    }

SRM 466 Div1 Easy LotteryCheating

20:52 | SRM 466 Div1 Easy LotteryCheating - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 466 Div1 Easy LotteryCheating - chokudaiの日記 SRM 466 Div1 Easy LotteryCheating - chokudaiの日記 のブックマークコメント

問題

10文字以下の数字の文字列が与えられる。文字をいくつか変更して、約数の個数が奇数な番号を作りたい。変更する必要のある文字数の最小数を求めなさい。

方針

約数が個数=平方数なので、i<100000までループを回してすべての平方数に対して試せばOK

ソースコード

    public int minimalChange(string ID)
    {
        long num = 1;
        int res = 1000;
        for (num = 0;num<=100000;num++)
        {
            res = Math.Min(getdiff(ID, (num*num).ToString()), res);
        }
        return res;
    }

    int getdiff(string a, string b)
    {
        int i;
        int res = 0;
        while (a.Length > b.Length) b = "0" + b;
        while (a.Length < b.Length) return 100;
        for (i = 0; i < a.Length; i++) if (a[i] != b[i]) res++;
        return res;
    }

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/chokudai/20101109
 |