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






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
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 490 - Yellow 1차 방어전 성공..  (0) 2010.12.09
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

Leave a Comment


to Top