TopCoder SRM 400 DIV 2

C++ TopCoder
Problem Check Points
250 o 205.19
500 x -
1000 - -

TopCoder Statistics

@uwitenpen

Problem 250 GrabbingTaxi

You are walking in the city on a holiday. Suddenly, you are told to go to your office as soon as possible by your boss via cell phone. The city is infinite in size, with vertical streets located at every integer X value and horizontal streets located at every Y value. You are currently located at (0, 0) and your office is located at (gX, gY). There are some taxi stands in the city and their locations are (tXs[i], tYs[i]). You can either go to the office by foot or go to some taxi stand, get a taxi there and go to the office by taxi. It takes walkTime seconds to go along the street to proceed to a horizontally or vertically adjacent intersection by foot and it takes taxiTime seconds by a taxi.

Return the least amount of time that it will take you to go to your office.

歩きだけで行った場合と、どれか1台タクシーを使った場合を全部計算して、最小のものを返す。

class GrabbingTaxi {
public:
  int minTime(vector <int> tXs, vector <int> tYs, int gX, int gY, int walkTime, int taxiTime) {

	  int minnum = 200000000;
	  for(int i=0 ; i<(signed)tXs.size() ; i++){
		  int tmp = (abs(tXs[i]) + abs(tYs[i]))*walkTime + ( abs(gX-tXs[i])+ abs(gY-tYs[i]) )*taxiTime;

		  minnum = min(minnum, tmp);
	  }

	  return min(minnum,  (abs(gX)+abs(gY))*walkTime);

  }
};

Problem 500 StrongPrimePower

A number which can be represented as pq, where p is a prime number and q is an integer greater than 0, is called a prime power. If q is larger than 1, we call the number a strong prime power. You are given an integer n. If n is a strong prime power, return an int containing exactly two elements. The first element is p and the second element is q. If n is not a strong prime power, return an empty int.

pow関数でn乗根が計算できるのをすっかり失念していた。
ll next = (ll)(aa+EPS);
の行はdoubleによる誤差を矯正するためにEPSを足している。0.5でもOKみたい

bool isPrime(ll a){
	if(a<2) return false;
	ll i;
	for(i=2 ; i*i<=a ; i++) if(a%i==0) return false;
	return true;
}

class StrongPrimePower {
public:
  vector <int> baseAndExponent(string n) {
	
	  istrstream istr(n.data());
	  ll a;
	  istr >> a;

	  for(int i=2 ; ; i++){
		  long double aa = powl((long double)a, 1.0/i);

		  ll next = (ll)(aa+EPS);
		  if(next < 2) return vector<int>();
		  ll res = 1;
		  for(int j=0 ; j<i ; j++) res *= next;

		  if(res==a && isPrime(next)){
			  vector<int> ans;
			  ans.push_back(next);
			  ans.push_back(i);
			  return ans;
		  }
	  }
  }
};

Problem 1000 LightedPanels

You are given a rectangular board consisting of several light panels. Character j of element i of board represents the panel in row i, column j. '*' means the panel is on, and '.' means it's off. When you touch a panel, its state will be toggled. In other words, if you touch a panel that's on, it will turn off, and if you touch a panel that's off, it will turn on. Because the panels are so sensitive, when you touch a panel, all of its horizontally, vertically, and diagonally adjacent panels will also toggle their states.

Your goal is to have all the light panels in the board be on at the same time. Return the minimum number of touches required to achieve this goal, or return -1 if it is impossible.

やってない