SRM 466 250pt: LotteryCheating

問題概要

L(<=10)桁の数字が与えられる。最小何桁の数字を動かせば、約数の個数が奇数になるか求める問題。

考えたこと

• (当時は全く手が出なかった問題)
• 約数の個数が奇数=平方数。
• なので候補の上限10^Lのうち調べるのは10^(L/2)だけでよい。
• 後は変換するだけ。0でパディングするのが面倒なので両方桁数13に増やそう。
• サンプル通った。投げる。WA。
• 勝手に桁数増やしちゃダメじゃん。文字列に変換したとき、桁数がもとのを越えたら即アウトの判定をすれば良い。
• 修正後無事通った。

practiceで通ったコード

計算量O(10^(L/2)*L)。

#include <string>
#include <sstream>
using namespace std;

typedef long long int64;

const int INF = 1<<29;
const int MAX_LEN = 15;
const int64 MAX_N = (int64)1000*1000*1000*10;

struct LotteryCheating {

	int minimalChange(string ID) {

		//当たり=平方数を全探索
		int ret = INF;
		for(int64 x=0; x*x <= MAX_N; x++){
			ret = min(ret, get_distance(ID, to_str(x*x) ) );
		}

		return ret;
	}

	int get_distance(const string& a, string b){
		if(a.length() < b.length()){
			return INF;
		}
		if(a.length() > b.length()){
			b = string(a.length() - b.length(), '0') + b;
		}
		int ret = 0;
		for(int i=0; i<(int)a.length(); i++){
			if(a[i] != b[i]){
				ret++;
			}
		}
		return ret;
	}

	string to_str(int64 x){
		stringstream ss;
		ss << x;
		return ss.str();
	}
};