TopCoder SRM 490 DIV 2

Problem	Check	Points
250	o	244.19
500	o	219.04
1000	-	-
Challenge	-	50.00

Rate: 926 -> 1058

過去最高の出来。500がうまく解けた。

Login - TopCoder Wiki
@matsu4512
@aaharu

Problem 250 LuckyCounter

Suppose that we're given a moment of time written as HH:MM, where HH is the hour and MM is the minutes. Let's say that this moment is lucky if it is formatted AB:AB, AA:BB or AB:BA, where both occurrences of A stand for the same digit and both occurrences of B also stand for the same digit. It is allowed for the digits represented by A and B to be the same as well.

You are given a String[] moments, where each element represents a single moment of time. Return how many of these time moments are lucky.

スピード勝負。

class LuckyCounter {
public:
  int countLuckyMoments(vector <string> moments) {
	int cnt = 0;
	for(int i=0 ; i<moments.size() ; i++){
		if(moments[i][0]==moments[i][1] && moments[i][3]==moments[i][4]) cnt++;
		else if(moments[i][0]==moments[i][3] && moments[i][1]==moments[i][4]) cnt++;
		else if(moments[i][0]==moments[i][4] && moments[i][1]==moments[i][3]) cnt++;
	}
    return cnt;
  }

Problem 500 Starport

A new starport has just started working. Starting from some moment of time (call it minute 0), a new spaceship arrives at the starport every M minutes. In other words, spaceships arrive at the starport at minutes 0, M, 2*M, 3*M and so on.

Similarly, starting from minute 0 and repeating each N minutes, all arrived spaceships that are still placed at the port are teleported to the shed. If a spaceship arrives at the exact same minute when such a teleportation happens, it will be teleported immediately. Otherwise it will need to wait until the next teleportation happens.

Let the waiting time of a spaceship be the time between its arrival and its teleportation to the shed. Return the average waiting time of a spaceship in minutes. See notes for an exact definition.

できたプログラムが短すぎて怖かった。

ll gcd( ll m, ll n )
{
	if ((0==m) || (0==n)) return 0;
	ll tmp;
	while(m%n!=0){
		tmp = n;
		n = m%n;
		m = tmp;
	}
	return n;
}

ll lcm( ll m, ll n ){
	if ((0==m) || (0==n)) return 0;
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

class Starport {
public:
  double getExpectedTime(int N, int M) {	  
	  ll a = lcm(N,M);
	  ll k = N-(M%N) + N-((a-M)%N);
	  return (double)k/2*(double)((a/M)-1)/(double)(a/M);
  }
};