TopCoder SRM 431 DIV 2

C/C++ TopCoder
Problem Check Points
250 ○ 241.69
500 × -
1000 - -

500は問題文の「previously」に泣かされた・・・

Problem 250 MegaCoolNumbersEasy

問題

A positive integer is called a mega cool number if its digits form an arithmetic progression. An arithmetic progression is a sequence of numbers in which the difference between any two consecutive numbers is the same. Return the number of mega cool numbers between 1 and N, inclusive.

http://www.topcoder.com/stat?c=problem_statement&pm=10281&rd=13522
My code
// vが階差数列かどうかを判定する。
bool isArithProg(deque<int> v){
	int dif=v[1]-v[0];

	for(int i=0 ; i<(signed)v.size()-1 ; i++){
		if(v[i+1]-v[i] != dif) return false;
	}
	return true;
}

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

bool isMegacool(int n){
	if(n<100) return true;
	return isArithProg(integerDigits(n));
}

class MegaCoolNumbersEasy {
public:
  int count(int N) {
    int result=0;

	for(int i=1 ; i<=N ; i++){
		if(isMegacool(i)) result++;
	}

    return result;
  }
};

Problem 500 FallingPoints

問題

You are given a int X containing the x-coordinates of several points. Each point starts at an infinitely high y-coordinate. Starting with the first point, each point falls down until it is either a distance of R away from a previously fallen point or it reaches y = 0. Each point (after the first point) will start falling only when the previous one stops. Return a double, where the i-th element is the final y-coordinate of the i-th point.

http://www.topcoder.com/stat?c=problem_statement&pm=10261&rd=13522
解説

Let y[i] be the final y-coordinate for the i-th falling point. We can calculate y's in sequential order. For the first point, there is no previous point, so it just falls down, i.e. y[0] = 0. Assuming we know y[i-1], let's calculate y[i]. The i-th point falls along the line x = X[i]. So we need to find the highest y when the distance between the points (X[i], y) and (X[i-1], y[i-1]) is equal to R. We can write this in form of mathematical equation and do some simple transformations:

sqrt((X[i] - X[i-1])^2 + (y - y[i-1])^2) = R
(X[i] - X[i-1])^2 + (y - y[i-1])^2 = R^2
(y - y[i-1])^2 = R^2 - (X[i] - X[i-1])^2

The last equation doesn't have solutions if R^2 - (X[i] - X[i-1])^2 < 0 or, equivalently, |X[i] - X[i-1]| > R (because the left part of the equation is always non-negative and the right part is negative). In this case i-th point will just fall down, i.e. y[i] = 0. Otherwise, we can take square root from both sides of the equation:

y - y[i-1] = +/-sqrt(R^2 - (X[i] - X[i-1])^2)
y = y[i-1] +/- sqrt(R^2 - (X[i] - X[i-1])^2)

Since we would like to know the highest possible value of y, we can deduce that y[i] = y[i-1] + sqrt(R^2 - (X[i] - X[i-1])^2).

Java implementation follows.

public class FallingPoints {
  public double[] getHeights(int[] X, int R) {
    double[] y = new double[X.length];
    y[0] = 0;
    for (int i=1; i < X.length; i++)
      if (Math.abs(X[i] - X[i-1]) > R)
        y[i] = 0;
      else
        y[i] = y[i-1] + Math.sqrt(R * R - (X[i] - X[i-1]) * (X[i] - X[i-1]));
    return y;
  }
}
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm431
My code
vector<double> result;
vector<int> XX;

double calc(int ii, double dist){
	double a = 0, tmp;

	for(int i=ii-1 ; i<ii ; i++){
		if(XX[ii]-XX[i] > dist) continue;

		tmp = sqrt(dist*dist - (XX[ii]-XX[i])*(XX[ii]-XX[i])) + result[i];
		a = max(a, tmp);
	}

	return a;
}

class FallingPoints {
public:
  vector <double> getHeights(vector <int> X, int R) {
	 XX = X;
	 result.clear();
	result.push_back((double)0);


	for(int i=1 ; i<X.size() ; i++){	
		result.push_back(calc(i, (double)R));
	}

    return result;
  }
};

Problem 1000 SumAndProduct

問題

A list of non-negative numbers is called satisfactory if the sum of the numbers in the list is equal to S and the product of the numbers is equal to P. Find a satisfactory list with the least possible number of elements, and return its size. If no such list exists, return -1 instead. Please note that the list may contain non-integer numbers.

http://www.topcoder.com/stat?c=problem_statement&pm=10257&rd=13522
My code
class SumAndProduct {
public:
  int smallestSet(int S, int P) {
	if(S==P) return 1;	

	int n=2;
	double a;
	while(1){
		if((double)S/(double)n<1){
			n = -1;
			break;
		}
		a = pow((double)S/(double)n, (double)n);
		if(a >= P) break;
		n++;
	}
	return n;
  }
};