## SRM 490 - Yellow 1차 방어전 성공..

두달 반만에 참가한 매치..~
너무 오랜만에 참가한데다가.. 옐로우를 지켜야한다는 부담감 백배였는데..
리서밋으로 망했다가 챌 하나로 겨우 살아났다..~  Level1 - Starport

teleport 는 0, N, 2*N, 3*N, ... 순으로 들어오고 startport 는 0, M, 2*M, 3*M, ... 순으로 들어온다..
startport 가 들어와서 다시 teleport 를 타기위해 평균 얼마나 기다려야 할까..?

이 문제는 규칙을 찾아보면.. LCM(N, M) 을 주기로 같은 값이 반복되는 걸 알 수 있다..
그래서 두 수의 LCM 구하고 simulation 해서 답 나오길래 submit~
그런데 좀 미심쩍어서 N = 1000000000, M = 1 을 넣어보니 TLE !!!
잘 고민해보니 lcm 개수만큼 loop 를 돌 필요 없고 등차수열의 합공식을 이용하여 한방에 구할 수 있다..

다행이 내가 처음 생각했던 방법 비스무리하게 시도한 사람이 몇 있어서.. 챌 먹이감이 되었다..
다들 챌이 너무 빨라서 1개밖에 성공 못했다..

다른 사람들 코드를 보니.. 다들 너무 짧아서 황당..
식을 정리해보면 결국 나랑 같은 식이기는 한데.. 뭔가 접근방법이 다른듯..

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 long long gcd(long long a, long long b)
13 {
14     if (b == 0)
15         return a;
16     return gcd(b, a % b);
17 }
18
19
20 class Starport {
21 public:
22
23 double getExpectedTime(int N, int M)
24 {
25     long long L;
26     long long G;
27     long long cnt;
28     long long dif, n;
29     double sum;
30     G = gcd(N, M);
31     L = (long long)N * (long long)M / G;
32     cnt = L / M;
33     sum = 0.0;
34     dif = N / cnt;
35     n = cnt;
36     sum = (double)(n * (n-1) * dif / 2LL);
37     sum /= (double)cnt;
38 /*
39     for (i = 0; i < cnt; i++) {
40         a = i * M;
41         b = a % N;
42         if (b == 0)
43             c = a;
44         else
45         c = a + (N - b);
46         sum = sum + (double)(c - a);
47     }
48     sum /= (double)cnt;
49 */
50 printf("sum = %lf\n", sum);
51     return sum;
52 }
53
54 };

Level2 - QuickT9

어떻게 풀라는거임?

Level3 - InfiniteLab

어떻게 풀라는거임?

#### 'Problem Solving > TopCoder logs' 카테고리의 다른 글

 SRM 503 흑흑 ㅠ_ㅠ;;  (0) 2011.04.18 2011.04.01 2011.02.27 2011.02.02 2010.12.21 2010.12.09 2010.09.26 2010.09.16 2010.08.16 2010.08.08 2010.07.29