새벽 1시에 열린 매치.. 상금매치인것같다.. 미리 예고도없이 갑자기 상금매치라니.. rating관리도 못했는데.. 게다가 방배정도 이상하다.. red와 yellow로 가득한 방에서 멀 어쩌라는거야.. -_-++
완전 케막장 매치를 치뤘는데.. 놀라운건 그래도 rating이 올랐다.. -_-;;; 신기하네..;

방 17등 전체 474등..



사용자 삽입 이미지
저렇게 red와 yellow사이에 나를 집어넣으면 어쩌라는거야!!! 거의 최악의 등수를 기록했는데도불구하고 rating이 올랐다.. 신기하다..;



[250] SmoothNumbers

소인수분해를 했을 때 모든 소인수가 k보다 작거나 같은수를 k-smooth라고 한다.. input으로 n과 k가 들어올때 n보다 작거나같은 수 중에서 k-smooth number의 개수 구하기..

brute force로 풀었다.. 1부터 n까지의 모든수에대해서 factoring하고.. 모든 prime factor가 k보다 작거나 같은수에 대해서 count하면 된다..

단순한 문제임에도 불구하고.. 두개의 솔루션이 동시에 생각나는바람에.. (사실 뭐로하든 관계없는데..) 어떤방법으로 푸는게 간단할까.. 고민하다가 늦게 푼 문제.. ㅠ_ㅠ; 다들 ㅈㄴ빨리푼다.. 역시 div1은 다르군.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8
  9 int is_prime[1000000];
 10 int prime[100000];
 11 int prime_cnt;
 12
 13 void sieve()
 14 {
 15     int i, j;
 16     memset(is_prime,-1,sizeof(is_prime));
 17     prime_cnt = 0;
 18     is_prime[1] = is_prime[0] = 0;
 19     for(i=2;i<=100000;i++) {
 20         if (is_prime[i]) {
 21             for(j=2;i*j<=100000;j++) {
 22                 is_prime[i*j]=0;
 23             }
 24             prime[prime_cnt++] = i;
 25         }
 26     }
 27 }
 28
 29 class SmoothNumbers {
 30 public:
 31
 32 int countSmoothNumbers(int N, int k)
 33 {
 34     int i, j;
 35     int temp, cnt, fl;
 36     sieve();
 37     cnt = 0;
 38     for (i = 1; i <= N; i++) {
 39         temp = i;
 40         fl = 1;
 41         for (j = 0; j < prime_cnt && prime[j] <= temp; j++) {
 42             if (temp % prime[j] == 0) {
 43                 if (prime[j] > k) {
 44                     fl = 0;
 45                     break;
 46                 }
 47                 while (temp % prime[j] == 0)
 48                     temp /= prime[j];
 49             }
 50         }
 51         if (fl)
 52             cnt++;
 53     }
 54     return cnt;
 55 }
 56
 57 };





[500] InformFriends

i와 j가 친구이고 i와 k가 친구이면, i가 j에게 메세지를 전달 할 경우 j는 k에게 전달한다.. 그러나 i와 k가 친구가 아니면, j는 k에게 메세지를 전달하지 않는다.. 한번에 한사람에게 메세지를 전달할 때, 최대한 몇개의 메세지를 모든 사람이 전달받을 수 있는지 구하는문제..

매치 에디토리얼에 따르면, 위 조건을 만족하는 set을 dominating set이라고 하고, 위의 문제는 maximum number of independent dominating set을 구하는 문제.. 즉, domatic number를 구하는 문제..


to be updated..




[1000] TelephoneNumbers




to be updated..



 

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

TopCoder TCO08 Online Round 1  (2) 2008.02.17
TopCoder TCO08 Qualification Round 3(3A)  (0) 2008.02.15
TopCoder TCO08 Qualification Round 1  (4) 2008.02.06
TopCoder SRM 390 Div1  (2) 2008.02.03
TopCoder SRM 389 Div1  (0) 2008.01.25
TopCoder SRM 387 Div1  (4) 2008.01.10
TopCoder SRM 386 Div 2  (4) 2008.01.06
TopCoder SRM 385 Div2 (완료)  (4) 2007.12.30
TopCoder SRM 384 Div2 (완료)  (2) 2007.12.20
TopCoder SRM 383 Div 2 (완료)  (0) 2007.12.14

to Top