SRM466 Div1 Easy

250

#define ALL(c) (c).begin(), (c).end()

typedef long long lli;

string ltoa(lli n) {
  char buff[20];
  sprintf(buff, "%lld", n);
  return string(buff);
}

class LotteryCheating {
public:
  int minimalChange(string ID) {

    int ret = (int)ID.size() - count(ALL(ID), '0');

    for (lli i = 0; i*i <= 10000000000LL; ++i) {
      string s = ltoa(i * i);
      int cnt = 0;
      if (ID.size() < s.size()) break;
      while (s.size() < ID.size()) s = "0" + s;
      for (int j = 0; j < ID.size(); ++j) {
        cnt += ID[j] != s[j];
      }
      ret = min(ret, cnt);
    }

    return ret;
  }
};