Hatena::Grouptopcoder

blu_rayの日記

2011-10-28

Codeforces Beta Round #91 Div2

| 02:15

ooox-

A. Lucky Division / Accepted / 484

与えられたnがlukcy numberで割り切れるか判定する。事前に求めておけばもちろんO(1)で判定できる。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const int MAX_N = 1002;
int n;
set<int> s;

void make_lucky(int a) {
  if (a > MAX_N) return;
  if (a > 0) s.insert(a);
  a *= 10;
  make_lucky(a + 4);
  make_lucky(a + 7);
}

bool check[MAX_N];

int main() {
  make_lucky(0);
  fill(check, check + MAX_N, false);
  foreach(s,i) {
    for (int j = *i; j < MAX_N; j += *i) {
      check[j] = true;
    }
  }
  
  while (cin >> n) {
    cout << ((check[n]) ? "YES" : "NO") << endl;
  }
  return 0;
}

B. Lucky Substring / Accepted / 932

”もっとも出現回数の多い”という条件があるため、結局'4'か'7'になるので、ただ数え上げるだけ。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

string in;

int solve() {
  int sz = in.size();
  int cnt_4 = 0, cnt_7 = 0;
  rep (i,sz) {
    if (in[i] == '4') cnt_4++;
    else if (in[i] == '7') cnt_7++;
  }
  if (cnt_4 > cnt_7) {
    return 4;
  } else if (cnt_4 < cnt_7) {
    return 7;
  } else {
    if (cnt_4 && cnt_7) return 4;
  }
  return -1;
}

int main() {
  while (cin >> in) {
    cout << solve() << endl;
  }
  return 0;
}

C. Lucky Sum / Accepted / 1076

いろいろ試行錯誤しましたが、lukcy numberの配列をまわしていって足してく感じに落ち着いた。

最初、next(x)のx > 777777777以降は4444444444になるのを忘れてた。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
typedef long long ll;

const ll MAX_N = 1000000002;
int l, r;
set<ll> s;
ll list[2000];

ll solve() {
  ll ans = 0;
  ll cur = l;
  rep (i,s.size()+1) {
    if (list[i] >= cur) {
      if (list[i] < r) {
        ans += (list[i] - cur + 1) * list[i];
        cur = list[i] + 1;
      } else {
        ans += (r - cur + 1) * list[i];
        break;
      }
    }
  }
  return ans;
}

void make_lucky(ll a) {
  if (a > 0) s.insert(a);
  a *= 10;
  if (a > MAX_N) return;
  make_lucky(a + 4);
  make_lucky(a + 7);
}

int main() {
  make_lucky(0L);
  int ptr = 0;
  foreach(s,i) {
    list[ptr] = *i;
    ptr++;
  }
  list[ptr] = 4444444444LL;
  while (cin >> l >> r) {
    cout << solve() << endl;
  }
  return 0;
}

D. Lucky Transformation / TLE on 9

ほかの方のを参考にしたところ、ループの処理が大事だったみたいだ。。

447, 477のループになるのは気づいたけど別にいいやって思ってた。

修正済み。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int n, k;
string in;

string solve() {
  string ret = in;
  int prev = -1;
  rep (i,n-1) {
    if (in[i] == '4' && in[i+1] == '7') {
      prev = i; break;
    }
  }
  
  if (prev == -1) return ret;

  for (int i = k - 1; i >= 0; --i) {
    if (prev >= n) break;
    bool ok = false;
    // loop check
    if (prev + 2 <= n - 1) {
      if (!(prev % 2)) {
        if ((ret[prev] == '4' && ret[prev+1] == '4' && ret[prev+2] == '7') ||
           (ret[prev] == '4' && ret[prev+1] == '7' && ret[prev+2] == '7') ) {
           i %= 2;
        }
      }
    }
    if (ret[prev] == '4' && ret[prev+1] == '7') ok = true;
    if (!ok) {
      for (int j=prev; j<n; ++j) if (ret[j] == '4' && ret[j+1] == '7') {
        ret[j] = ret[j+1] = (j%2) ? '7' : '4';
        if (j > 0 && ret[j-1] == '4' && ret[j] == '7') {
          prev = j-1;
        } else if (j+2 <= n-1 && ret[j+1] == '4' && ret[j+2] == '7') {
          prev = j+1;
        } else {
          prev = j+2;
        }
        ok = true;
        break;
      }
      if (!ok) break;
    } else {
      ret[prev] = ret[prev+1] = (prev%2) ? '7' : '4';
      if (prev > 0 && ret[prev-1] == '4' && ret[prev] == '7') {
        prev = prev-1;
      } else if (prev+2 <= n-1 && ret[prev+1] == '4' && ret[prev+2] == '7') {
        prev = prev+1;
      } else {
        prev = prev+2;
      }
    }
  }
  return ret;
}

int main() {
  while (cin >> n >> k >> in) {
    cout << solve() << endl;
  }
  return 0;
}

rate := 1445 (+149)