TopCoder SRM 491 DIV 2

Problem	Check	Points
250	o	242.42
500	o	202.60
1000	-	-
Challenges	-	0.00

Rate: 1058 -> 1115

前回に引き続き500が解けた。本番運がいい。

@phyllo
@matsu4512

Problem 250 OneDigitDifference

We say that two integer numbers differ from each other by one digit, when in their decimal notation, possibly with leading zeros, they will differ in exactly one position. For example numbers 128 and 28 differ by one digit:
128
028
But numbers 2047 and 40 differ by two digits:
2047
0040
Given the number N, find and return the smallest possible non-negative number M, such that number N and M differ from each other by exactly one digit.

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

int fromDigits(deque<int> arr){
	int x=0;
	while(!arr.empty()){
		x *= 10;
		x += arr[0];
		arr.pop_front();
	}
	return x;
}

class OneDigitDifference {
public:
  int getSmallest(int N) {

	  if(N==0) return 1;

	  deque<int> d = integerDigits(N);
	  d.pop_front();
	  
	  return fromDigits(d);
  }
};

Problem 500 FoxMakingDiceEasy

Fox Jiro likes dice. He wants to make his own dice. Each die he wants to make is a cube. Each of the 6 faces has an integer between 1 and N, inclusive. No two faces have same number. Also the following condition must be satisfied: for all faces, the sum of the numbers on opposite faces must be equal and the sum must be greater than or equal to K.

He realized that there are many ways to make such dice. He wants to know how many ways there are. Please help Jiro to make a program that is given two integers N and K and returns the number of different dice satisfying the condition mentioned above.

Two dice are considered the same if you can rotate one to form the other.

解けたはずだけどいまいちぴんときていない。

// combination
double C(int n, int k){
  if(k==0 || k==n)
    return 1;
  static std::map<std::pair<int,int>,double> m;
  double &c=m[std::make_pair(n,k)];
  if(!c)
    c=C(n-1,k-1)+C(n-1,k);
  return c;
}

class FoxMakingDiceEasy {
public:
  int theCount(int N, int K) {
	  if(N<6) return 0;
	  ll cnt = 0;

	  for(int i=6 ; i<N ; i++){
		  if(i+1<K) continue;
		  cnt += (ll)C(i/2,3);
	  }

	  for(int i=1 ; i<=N-5 ; i++){
		  int tmp = N-i+1;
		  if(N+i<K) continue;
		  cnt+= (ll)C(tmp/2,3);
	  }
	  return (int)(cnt*2);
  }
};