TopCoder SRM 388 Div1

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

방 17등 전체 474등..

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



[250] SmoothNumbers

Problem Statement
     
A positive integer is said to be k-smooth if its largest prime factor is no greater than k. Compute how many positive integers less than or equal to N are k-smooth.
Definition
   
Class:
SmoothNumbers
Method:
countSmoothNumbers
Parameters:
int, int
Returns:
int
Method signature:
int countSmoothNumbers(int N, int k)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 100,000, inclusive.
-
k will be between 1 and 100, inclusive.
Examples
0)
 
   
10
3
Returns: 7
Of the first ten integers, only 5, 7 and 10 have prime factors greater than 3.
1)
 
   
10
4
Returns: 7
4 is not prime, so 4-smooth numbers are the same as 3-smooth numbers.
2)
 
   
15
3
Returns: 8
 
3)
 
   
5
20
Returns: 5
 
4)
 
   
100000
100
Returns: 17442
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

소인수분해를 했을 때 모든 소인수가 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

Problem Statement
     
You wish to share as many facts as possible with a group of N people, but you only have time to tell one fact to each person in the group. When you tell someone a fact, you also instruct them to tell all their friends. However, the friends do not tell their friends: if A and B are friends, B and C are friends, but A and C are not friends, then after telling the fact to A it will be passed on to B but not to C. You must tell each fact to enough people so that every person either hears the fact from you, or is a friend of someone who heard it from you.
friends contains N strings of N characters, each of which is either 'Y' or 'N'. The jth character of the ith element is 'Y' if members i and j are friends, and 'N' otherwise. Determine the maximum number of facts that can be shared with every person in the group.
Definition
   
Class:
InformFriends
Method:
maximumGroups
Parameters:
vector <string>
Returns:
int
Method signature:
int maximumGroups(vector <string> friends)
(be sure your method is public)
     
 
Constraints
-
friends will contain exactly N elements, where N is between 1 and 15, inclusive.
-
Each element of friends will contain exactly N characters.
-
Each character in friends will be either 'Y' or 'N'.
-
For i and j between 0 and N - 1, inclusive, character j of element i of friends will be the same as character i of element j.
-
For i between 0 and N - 1, inclusive, character i of element i of friends will be 'N'.
Examples
0)
 
   
{"NYYN",
 "YNYY",
 "YYNY",
 "NYYN"}
Returns: 3
Tell one fact to people 0 and 3, one fact to 1, and one fact to 2.
1)
 
   
{"NYYN",
 "YNYN",
 "YYNN",
 "NNNN"}
Returns: 1
Person 3 has no friends, and so can learn only one fact directly from you.
2)
 
   
{"NYNNNY",
 "YNYNNN",
 "NYNYNN",
 "NNYNYN",
 "NNNYNY",
 "YNNNYN"}
Returns: 3
Provide facts A, B, C, A, B, C to the six people in order. Each will receive one fact directly and one from each neighbor.
3)
 
   
{"NYNY",
 "YNYN",
 "NYNY",
 "YNYN"}
Returns: 2
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

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

Problem Statement
     
Your company has received the contract to implement the new telephone system on the moon, where all telephone numbers will have 7 hexadecimal digits (see notes). The distance between two telephone numbers is the number of corresponding digits that differ. For example, the distance between 1b100fa and 11b0ffa is 3, because the 2nd, 3rd, and 5th digits (counting from the left) are different. In order to avoid wrong numbers, every pair of telephone numbers will have a distance of at least separation between them. Your policy for allocating telephone numbers is simple: each time a new number is required, the smallest possible number is assigned such that these conditions are preserved.
Your company is going to award a special prize to the person who is assigned the kth telephone number (k is 1-based). Return this number as a string of exactly 7 hexadecimal digits: '0' - '9' and lowercase 'a' - 'f'. The constraints guarantee that k is small enough for the prize to be awarded before it becomes impossible to allocate new numbers.
Definition
   
Class:
TelephoneNumbers
Method:
kthNumber
Parameters:
int, int
Returns:
string
Method signature:
string kthNumber(int separation, int k)
(be sure your method is public)
   
 
Notes
-
Hexadecimal is base 16 (compared to "normal" numbers, which are base 10). The lowercase letters 'a' - 'f' are used to represent the digits with values 10 - 15. For example, the hexadecimal number 'af' is the same as the decimal number 10 * 16 + 15 = 175.
Constraints
-
separation will be between 1 and 3, inclusive.
-
k will be between 1 and 300,000, inclusive.
Examples
0)
 
   
1
5
Returns: "0000004"
The first five phone numbers are simply 0000000, 0000001, 0000002, 0000003 and 0000004.
1)
 
   
2
17
Returns: "0000101"
The first sixteen phone numbers are 00000?? for ? = 0, 1, ..., f.
2)
 
   
3
33
Returns: "0002023"
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

to be updated..