TopCoder SRM 425 DIV 2

Problem	Check	Points
250	×	-
500	-	-
1000	-	-

絶　望

Problem 250 InverseFactoring

問題

A positive integer a is a proper factor of n if and only if n is a multiple of a and a does not equal 1 or n. You are given a int[] factors containing all the proper factors of some integer n. Return n.

http://www.topcoder.com/stat?c=problem_statement&pm=10118&rd=13516

解説

If you'll look at the list of all factors of some number N, you'll recognise that you can find there many pairs of numbers f1 and f2 such that f1 * f2 = N (no surprise here, if f1 is a factor of N, then N/f1 will also be a factor). Therefore, to find N we need to select two factors such that their product is N and multiply them.

How to do that? The easiest way is to sort the array of factors, take the smallest and the biggest factors of N, and return their product. Proving that the product of those factors will be equal to N is simple: if (f1 * f2) == N and (a1 * a2) == N, and f1 < a1, then (a2 < f2). So, if f1 is the smallest factor of N (f1 < f for any factor f), then f2 will be the biggest factor.

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm425

My code

class InverseFactoring {
public:
  int getTheNumber(vector <int> factors) {
	if(factors.size()==1) return factors[0]*factors[0];
	sort(factors.begin() , factors.end() );
	return factors[0] * factors[factors.size()-1];
  }
};

Problem 500 CrazyBot

問題

An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.

The robot's path is considered simple if it never visits the same point more than once. (The robot's starting point is always the first visited point.) Return a double containing the probability that the robot's path is simple. For example, "EENE" and "ENW" are simple, but "ENWS" and "WWWWSNE" are not ('E', 'W', 'N' and 'S' represent east, west, north and south, respectively).

http://www.topcoder.com/stat?c=problem_statement&pm=10095&rd=13516

My code

int m[100][100];
double ans;

int E;
int W;
int S;
int N;

void dfs(int n, int x, int y, double p){
	if(m[x+50][y+50]) return;
	if(n==0){
		ans += p;
		return;
	}

	m[x+50][y+50]=1;

	dfs(n-1, x-1, y, p*(double)W/100 );
	dfs(n-1, x+1, y, p*(double)E/100 );
	dfs(n-1, x, y-1, p*(double)S/100 );
	dfs(n-1, x, y+1, p*(double)N/100 );

	m[x+50][y+50]=0;
}

class CrazyBot {
public:
  double getProbability(int n, int east, int west, int south, int north) {
	  E = east;
	  W = west;
	  S = south;
	  N = north;
	  ans = 0.0;

	  dfs(n, 0, 0, 1);

	  return ans;
  }
};