TopCoder SRM 421 DIV 2

Problem	Check	Points
250	○	212.40
500	-	-
1000	-	-

500全くわからず。後で「二分探索」と聞いてかなりすぐ解けてしまったので悔しい・・・

TopCoder Statistics: SRM 421 Problem Set & Analysis

Problem 250 GymTraining

問題

You are at the gym and you want to do some training. The training process is divided into one-minute segments. During each minute, you can either train or rest.

If you choose to train during a minute, it increases your pulse by trainChange. That is, if your pulse was X, it becomes X + trainChange after a minute of training. You never want your pulse to exceed maxPulse, so you can train only if X + trainChange is less than or equal to maxPulse.

If you choose to rest during a minute, it decreases your pulse by restChange. That is, if your pulse was X, it becomes X - restChange after a minute of rest. However, your pulse never falls below minPulse, so if X - restChange is less than minPulse, your pulse becomes minPulse instead of X - restChange.

Your pulse is initially minPulse. You want to train for a total of needToTrain minutes (these minutes don't need to be consecutive). Return the minimum number of minutes your complete training process will take. If you can't train for needToTrain minutes, return -1 instead.

My code

class GymTraining {
public:
  int trainingTime(int needToTrain, int minPulse, int maxPulse, int trainChange, int restChange) {
    int result;

	if(minPulse+trainChange > maxPulse) return -1;

	int trained=0;
	int i=0, pulse = minPulse;
	while(1){
		if(pulse >= minPulse && pulse+trainChange <= maxPulse){
			pulse += trainChange;
			trained++;
		}
		else{
			pulse = max(minPulse, pulse-restChange);
		}
		i++;

		if(needToTrain==trained) break;
	}

    return i;
  }
};

Problem 500 EquilibriumPoints

問題

There are N points situated on a straight line. The i-th point is located at coordinate x[i] and has a mass of m[i]. The locat?on of each point is strongly fixed and cannot be changed by any forces. Coordinates of all points are distinct.

When another point P is added on the line and its position is not fixed, the point falls under the impact of gravitational forces from each of the given N points. Points located to the left of P force it to the left, and points located to the right of P force it to the right. When two points are located a distance of d apart and have masses m1 and m2, the value of gravitational force between them is F = G * m1 * m2 / d^2, where G is some positive constant.

Point P is said to be an equilibrium point if the vector sum of gravitational forces from all points on P equals zero. In other words, the sum of the values of gravitational forces between P and all the points located to the left of P must be the same as the sum of the values of gravitational forces between P and all the points located to the right of P.

It is known that there always exist exactly N-1 equilibrium points. Return a double[] containing their coordinates sorted in ascending order.

My code

class EquilibriumPoints {
public:
  vector <double> getPoints(vector <int> x, vector <int> m) {
	  vector<double> result;

	  for(int i=0 ; i<x.size()-1 ; i++){
		  
		  double left = (double)x[i];
		  double right = (double)x[i+1];

		  for(int cnt=0 ; cnt<130 ; cnt++){
			  double f1=0, f2=0;

			  double p = (left+right)/2;

			  for(int j=0 ; j<i+1 ; j++){
				  f1 += (double)m[j]/((p - (double)x[j])*(p - (double)x[j]));
			  }
			  for(int j=i+1 ; j<x.size() ; j++){
				  f2 += (double)m[j]/((p - (double)x[j])*(p - (double)x[j]));
			  }
			  if(f1 - f2 >=0) left = p;
			  else right = p;
		  }
		  result.push_back(left);
	  }
	  return result;
  }
};

Problem 1000 FloorIndicator

問題

Imagine a skyscraper with 10^N floors, numbered 0 to 10^N-1. The floor indicator in the elevator shows the floor number using exactly N digits, padding it with leading zeroes if necessary. Each digit is shown as a 5x3 field of small lamps, some of which are lit and some of which are unlit. Here is a representation of all the digits from 0 to 9 ('#' represents lit lamps and '.' represents unlit lamps) :

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

Here, as in the actual floor indicator, consecutive digits are separated by a single column of unlit lamps. Some of the lamps in the floor indicator are malfunctioning and always remain unlit. Imagine that you are stuck in this elevator and you want to know the current floor number. You decide to calculate it as the average value of all floor numbers that could possibly be represented by the current state of the indicator, assuming that any number of the unlit lamps might be malfunctioning. You are given the state of the indicator as a String[] where each element represents a row of lamps, and rows are given from top to bottom. Return the average that you calculate, or -1 if no valid floor number could possibly be represented by the indicator.