TopCoder SRM 440 DIV 2

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

500を提出すらできないという体たらく。代わりにDFSを覚えました。

Problem 250 IncredibleMachineEasy

Problem Statement
You may remember an old computer game called "The Incredible Machine". It was a game where you could simulate simple processes like balls falling, lasers shooting, or cats pursuing mice. Moreover, you were able to perform these observations with different values for gravitational acceleration.

Imagine a system with some unknown acceleration of gravity. There are N balls, each fixed initially at some height above the ground. You are given a int[] height, where the i-th element is the height of the i-th ball above the ground. At time 0, the first ball is set loose and it starts falling. When it reaches the ground, the second ball is instantly set loose, and so on. This continues until the last ball reaches the ground at time T.

Return the acceleration of gravity in this system. Neglect air resistance and any other resisting factors. The distance d travelled by an object falling for time t with no initial velocity in a system with gravitational acceleration g and no resisting factors is equal to d = 0.5 * g * t^2.

http://www.topcoder.com/stat?c=problem_statement&pm=10309&rd=13748 
class IncredibleMachineEasy {
public:
  double gravitationalAcceleration(vector <int> height, int T) {
	double k=0;

	for(int i=0 ; i<(signed)height.size() ; i++){
		k += sqrt((double)height[i]);
	}

	k = k/(double)T*sqrt((double)2);

	return k*k;
  }
};

Problem 500 MazeWanderingEasy

Problem Statement
According to research conducted recently, listening to classical music increases one's mental abilities, while listening to metal decreases them. Now, yet another experiment is being conducted to try to prove or disprove this statement.

In this new experiment, a mouse is placed in a rectangular maze consisting of NxM squares. Each square either contains a wall or is empty. The maze is structured in such a way that for any two empty squares, there exists exactly one path between them. A path is a sequence of pairwise distinct empty squares such that every two consecutive squares are neighboring. Two squares are considered neighboring if they share a common edge.

One of the empty squares in the maze contains a piece of cheese. The mouse's goal is to reach that square without visiting the same square twice. The mouse can only move between neighboring squares. Since the mouse has been listening to classical music for a week, he is extremely intelligent and guaranteed to achieve his goal.

As the mouse moves from his starting point to the cheese, he may encounter some squares where he must choose between several neighboring squares to continue. This happens when the mouse steps into a square which has more than one neighboring empty square, excluding the square from which he came, or when he has more than one neighboring empty square at the start. These situations are called "decisions" and the mouse will always make the right choice.

You are given a String[] maze representing the maze. It contains N elements, each containing M characters. Empty squares are denoted by '.', walls are denoted by uppercase 'X', the mouse's starting point is denoted by 'M', and the square containing the cheese is denoted by '*'. Return the number of decisions the mouse will make on his way to the cheese.

http://www.topcoder.com/stat?c=problem_statement&pm=10288&rd=13748 
int m[50][50];
int sx, sy;
int target;
int res;

int vx[4] = {0,0,1,-1};
int vy[4] = {1,-1,0,0};

bool inRange(int x, int y){return x>=0 && x<sx && y >=0 && y<sy;}

// Depth-First Search
void DFS(int i, int j, int n){
	//cheese
	if(m[i][j]==99999) res = n;
	
	m[i][j]=-1;

	int tx, ty, tmp=0;
	for(int k=0 ; k<4 ; k++){
		tx = i+vx[k];
		ty = j+vy[k];
		if(inRange(tx, ty) && m[tx][ty]!=-1) tmp++;
	}
	
	if(tmp>1) n++;

	for(int k=0 ; k<4 ; k++){
		tx = i+vx[k];
		ty = j+vy[k];
		if(inRange(tx, ty) && m[tx][ty]!=-1) DFS(tx, ty, n);
	}
}

class MazeWanderingEasy {
public:
  int decisions(vector <string> maze) {
    res = 0;

	sx = maze.size();
	sy = maze[0].size();

	// -1 -> wall
	for(int i=0; i<50 ; i++){
		for(int j=0 ; j<50 ; j++){
			m[i][j] = -1;
		}
	}

	string s;
	int mi, mj;
	int ci, cj;

	for(int i=0 ; i<sx ; i++){
		for(int j=0 ; j<sy ; j++){
			if(maze[i][j]=='M'){
				m[i][j] = -99;
				mi = i;
				mj = j;
			}
			else if(maze[i][j]=='*') m[i][j] = 99999;
			else if(maze[i][j]=='.') m[i][j] = 9999;
				
		}
	}

	DFS(mi, mj, 0);
    return res;
  }
};

Problem 1000 WickedTeacher

Problem Statement
A wicked teacher is trying to fail one of his students. He gives him the following problem:

You are given a String[] numbers containing a set of distinct integers. You can concatenate some permutation of these integers to obtain one large integer. For example, the permutation {5221, 40, 1, 58, 9} can be concatenated to form 5221401589. Find a permutation of the given numbers such that its concatenation is divisible by the integer K.

The student doesn't have a clue how to solve this problem, so he just answers with some random permutation. There may be multiple correct answers, and maybe the student has chosen one of them by chance. Return the probability that the student has chosen one of the correct answers and return it as a String in the form of an irreducible fraction "p/q" (quotes for clarity), where p is the fraction's numerator and q is its denominator. Assume that each permutation has the same probability of being chosen.

http://www.topcoder.com/stat?c=problem_statement&pm=10289&rd=13748

毎回1000の問題を載せる意味がない気がした