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

Problem Solving/TopCoder logs 2010. 12. 9. 23:19

두달 반만에 참가한 매치..~

너무 오랜만에 참가한데다가.. 옐로우를 지켜야한다는 부담감 백배였는데..

리서밋으로 망했다가 챌 하나로 겨우 살아났다..~

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개밖에 성공 못했다..

다른 사람들 코드를 보니.. 다들 너무 짧아서 황당..

식을 정리해보면 결국 나랑 같은 식이기는 한데.. 뭔가 접근방법이 다른듯..

Level2 - QuickT9

어떻게 풀라는거임?

Level3 - InfiniteLab

어떻게 풀라는거임?

너무 오랜만에 참가한데다가.. 옐로우를 지켜야한다는 부담감 백배였는데..

리서밋으로 망했다가 챌 하나로 겨우 살아났다..~

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 };

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 |
---|---|

SRM 501 (0) | 2011.04.01 |

SRM 498 - WTF!! (0) | 2011.02.27 |

SRM 496 (2) | 2011.02.02 |

SRM 491 - Blue 복귀.. (0) | 2010.12.21 |

SRM 483 - 처음으로 Petr 이겨본 매치..~ (0) | 2010.09.26 |

SRM 482 (0) | 2010.09.16 |

SRM 479 - 광복절 새벽에 삽질.. (0) | 2010.08.16 |

SRM 478 (2) | 2010.08.08 |

SRM 477 (0) | 2010.07.29 |