Dashboard - Qualification Round 2012 - Google Code Jam
Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.
Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.
Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?
A and B have the same number of digits.
Official Analysis: https://code.google.com/codejam/contest/1460488/dashboard#s=a&a=2
http://martin-thoma.com/google-code-jam-2012-qualification-round/
Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.
Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.
Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B.Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with A ≤ n < m ≤ B.Limits
1 ≤ T ≤ 50.A and B have the same number of digits.
Small dataset
1 ≤ A ≤ B ≤ 1000.Large dataset
1 ≤ A ≤ B ≤ 2000000.Are we sure about the output to Case #4?
Yes, we're sure about the output to Case #4.
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;
}
private static int solve(int A, int B) { int count = 0; HashSet<Integer> s = new HashSet<Integer>(); for (int n = A; n < B; n++) { String i = n + ""; // Clear each time instead of re-allocating // to reduce GC and other overhead s.clear(); int t = i.length(); // Don't even bother with concatenations of // leading zeros while (i.charAt(t-1) == '0') t--; // Iterate over all possible valid concatentations for (int j = 1; j < t; j++) { // Do the swap (this is slow, but the numbers are small) int m = Integer.parseInt(i.substring(j) + i.substring(0, j)); // Is it within the range specified? if (n < m && m <= B) // Add to a set to remove duplicates s.add(m); } count += s.size(); } return count; }def line2intlist(line):
list = line.split(' ')
numbers = [ int(x) for x in list ]
return numbers
def binomialCoefficient(n, k):
if k < 0 or k > n:
return 0
if k > n - k: # take advantage of symmetry
k = n - k
c = 1
for i in range(k):
c = c * (n - (k - (i+1)))
c = c // (i+1)
return c
#return n * (n - 1) / 2
def rot(num, rot):
num = str(num)
num = num[len(num)-rot:len(num)] + num[0:len(num)-rot]
return int(num)
def getRotList(num):
""" Only return bigger rotated ones """
rotList = [num]
for i in xrange(1, len(str(num))):
tmp = rot(num, i)
if tmp not in rotList and len(str(tmp)) == len(str(num)):
rotList.append(tmp)
return sorted(rotList)
def inBorder(rotations, A, B):
count = 0
for el in rotations:
if A <= el and el <= B:
count += 1
return count
def recycled(A, B, liste):
pairs = 0
minList = range(0, B+1)
for tmpList in liste[A:B+1]:
if minList[tmpList[0]]:
nrInBorder = inBorder(tmpList, A, B)
pairs += binomialCoefficient(nrInBorder, 2)
minList[tmpList[0]] = 0
return pairs