Google Code Jam 2012 资格赛3

  A，B 是位数相同的两个数，给定A，B 求满足 A ≤ n < m ≤ B 的(n, m) 对的数目。
  n 左移的若干位数，补到右边得到m ，比如： 1234 可以得到的 2341，3412，4123。
--------------------------------------------------------------------------------

  题目描述相当简单，存在一个特例，1212 可以得到 2121，1212，2121。所以存在重复的(n, m)对，google给出的解决思路是左移时，如果得到原数就跳出循环。而这个聪明的break，我看的20个参赛者只有一个想到。还看到一些用移位做的代码，读不明白。

  简单的移位只要2个for循环就搞定了：

def control(content):
    result = []
    for count, line in enumerate(content):
        A, B = line.rstrip('\n').split()
        A, B = int(A), int(B)
        num = 0
        for i in range(A, B):
            if i <= 10: continue
            n = str(i)
            for j in range(1, len(n)):
                if n[j] == '0': continue
                m = int(n[j:] + n[:j])
                if m == i: break
                if m > i and m <= B:
                    num += 1
        result.append('Case #' + str(count+1) + ': ' + str(num) + '\n') # (1212, 2121) show twice

    return result

 
Tips：在跑大数据时，python3 无法在8分钟内跑完，把range改成xrange用python2.7跑，6分多就可以跑完。这就是传说中的Python3效率不及Python2。

PS：我看了别人的程序，感觉这个比赛的美妙之处就在于一万个人有一万种程序、一万种思路，但是解决一个问题的方法也就那么几种。看到有日本人用D语言开发的，大部分人是C++，还有一人写的我没看懂。大致思路是先算一遍限定范围内所有的数，每次取一段数复制出来做计算。要是有程序能实现计算一部分数，下次到这一段就不用计算，那才叫牛。
下面我展示一些参赛者的程序。
0. Google给出的方案，相当的清晰，看着相当的爽快。

int solve(int A, int B) {
    int power = 1, temp = A;
    while (temp >= 10) {
        power *= 10;
        temp /= 10;
    }
    int result = 0;
    for (int n = A; n <= B; ++n) {
        temp = n;
        while (true) {
            temp = (temp / 10) + ((temp % 10) * power);
            if (temp == n)
                break;
            if (temp > n && temp <= B)
                result++;
        }
    }
    return result;
}

 
1.不错的思路，但是test的数组做的不是很好，也许作者lxx为了快。

int tens[] = {1,10,100,1000,10000,100000,1000000,10000000};

int main() {
  int tc; scanf("%d", &tc);
  for(int tci = 0; tci < tc; tci++) {
    int a,b; scanf("%d%d", &a, &b);
    int d; for(d=0;tens[d]<=a;d++);
    int cnt = 0;
    for(int x = a; x < b; x++) {
      int vals[10];
      vals[0]=0;
      for(int i = 1; i < d; i++) {
        vals[i] = x/tens[i]+x%tens[i]*tens[d-i];
      }
      sort(vals, vals+d);
      for(int i = 1; i < d; i++) {
        if(x < vals[i] && vals[i-1]<vals[i] && vals[i] <= b) cnt++;
      }
    }
    printf("Case #%d: %d\n", tci+1, cnt);
  }
  return 0;
}

2.getPower10() 函数很好的解决上面的test不够优雅的问题。不过knownNumber 有点耗费空间，currentId也感觉会不会溢有出的可能。

const int MAX_X = 10000005;
int knownNumber[MAX_X] = {0};
int currentId = 0;

int getPow10(int x) {
    int pow10 = 1;
    for (pow10 = 1; x >= pow10; pow10 *= 10) {}
    return pow10;
}

int main() {
    int nCases;

    scanf("%d", &nCases);
    for (int iCase = 1; iCase <= nCases; iCase++) {
        int xMin, xMax;
        scanf("%d%d", &xMin, &xMax);
        int pow10 = getPow10(xMin);
        assert(pow10 == getPow10(xMax));
        int solution = 0;
        for (int x = xMin; x <= xMax; x++) {
            currentId++;
            int rotX = x;
            while (knownNumber[rotX] < currentId) {
                knownNumber[rotX] = currentId;
                solution += (x < rotX && rotX <= xMax);
                rotX = (rotX + (rotX % 10) * pow10) / 10;
            }
        }
        printf("Case #%i: %i\n", iCase, solution);
    }
    return 0;
}

3. SnapDragon的超级简练的代码：

#include <iostream>
using namespace std;

main() {
  int T, A, B, prob = 1;
  for (cin >> T; T--;) {
    cin >> A >> B;
    int p10 = 1, ret = 0;
    while (p10 * 10 <= A) p10 *= 10;
    for (int x = A; x <= B; x++) {
      int y = x;
      do {
        if (y > x && y <= B) ret++;
        y = y/10 + p10 * (y%10);
      } while (y != x);
    }
    cout << "Case #" << prob++ << ": " << ret << endl;
  }
}