Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-09

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;
    }
 |