2013年8月7日

UVa 613 - Numbers That Count

#include <cstdio>
#include <string>
#include <map>
using namespace std;

map<string, int> rec;
bool loop;

int inv(string s, int l) {
  if (l >= 15) {
    return l;
  }
  int cnt[10] = {};
  for (int i = 0; s[i]; i++) {
    cnt[s[i] - '0']++;
  }
  string invs;
  char temp[99];
  for (int i = 0; i < 10; i++) {
    if (cnt[i]) {
      sprintf(temp, "%d%d", cnt[i], i);
      invs += temp;
    }
  }
  loop = rec.count(invs);
  rec[s] = l;
  if (loop) {
    return l - rec[invs] + 1;
  }
  return (invs == s) ? l : inv(invs, l + 1);
}

int main() {
  char s[99];
  while (gets(s) && s[0] != '-') {
    rec.clear();
    loop = false;
    int len = inv(s, 0);
    if (len >= 15) {
      printf("%s can not be classified after 15 iterations\n", s);
    } else if (len && loop) {
      printf("%s enters an inventory loop of length %d\n", s, len);
    } else if (len) {
      printf("%s is self-inventorying after %d steps\n", s, len);
    } else {
      printf("%s is self-inventorying\n", s);
    }
  }
  return 0;
}

沒有留言:

張貼留言