어제 새벽 1시에 열린 매치..~
이번에도 중국애들이 너무 많이 참여해서.. 1850 limit이 다 차버렸다..~
덕분에 채팅방에서는 limit 좀 늘려달라고 원성이 자자했다..~
나는 저번에 한번 당했기때문에 이번에는 3시간 전에 미리 등록..;;
이번 매치에서는 250을 비교적 빨리 풀어서 다시 yellow로 복귀했다..~
250을 풀고나서 550을 열었는데.. 코딩이 좀 난해해서 정확히 코딩할 자신이 없었다..
그래서 남은시간엔 그냥 놀았다.. -_-;;
흠.. 앞으로 550-950 set 이 나오면 950부터 열어야겠다..~
[250] Underprimes
더보기
Problem Statement
The prime factorization of a number X is the list of prime numbers that multiply together to form X. For example, the prime factorization of 12 is 2 * 2 * 3. Note that 1 is not a prime number.
An underprime is a number whose prime factorization contains a prime number of elements. For example, 12 is an underprime because its prime factorization contains 3 elements, and 3 is a prime number. Given ints A and B, return the number of underprimes between A and B, inclusive.
Definition
Class:
Underprimes
Method:
howMany
Parameters:
int, int
Returns:
int
Method signature:
int howMany(int A, int B)
(be sure your method is public)
Notes
-
A positive integer number is called prime if it has exactly two divisors - 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, and 4, 6, 8 and 9 are not prime. By convention, 1 is not considered to be a prime number.
-
All prime factorizations of the same integer always contain the same prime numbers and can only differ by the order of primes within them.
Constraints
-
A will be between 2 and 100000, inclusive.
-
B will be between A and 100000, inclusive.
Examples
0)
2
10
Returns: 5
The underprimes in this interval are: 4, 6, 8, 9, 10.
1)
100
105
Returns: 2
The underprimes in this interval are 102 = 2 * 3 * 17 and 105 = 3 * 5 * 7.
2)
17
17
Returns: 0
17 is a prime number, so its prime factorization contains one element. 1 is not a prime, so 17 is not an underprime.
3)
123
456
Returns: 217
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.
어떤 수 X를 factorization했을때, prime factor의 개수가 prime이면 underprime이라고 한다.. 예를들어 12 = 2*2*3 이므로, prime factor의 개수는 3이고 3은 prime이므로 12는 underprime이다..
A~B 사이에 underprime이 몇개있는지 구하기..
그냥 문제에서 시키는대로 factoring하고 prime 체크하면 된다..
나는 이전에 짜둔 코드가 있어서 그냥 복.붙 했다.. -_- 사실 sieve는 한번만 써도 되는데..
생각하기 귀찮아서.. 그냥 뒀다.. ㅋㅋ 비슷한 코드가 두벌 있으니 좀 이상하네..;;
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
11 int n_fact[100010];
12 char is_prime[1000001];
13 int prime[100000];
14 int prime_cnt;
15
16 void fact_sieve()
17 {
18 int i, j;
19 memset(n_fact, 0, sizeof(n_fact));
20 for (i = 2; i <= 100000; i++) {
21 if (n_fact[i] == 0) {
22 n_fact[i] = 1;
23 for (j = 2; i*j <= 100000; j++) {
24 n_fact[i*j] = n_fact[i] + n_fact[j];
25 }
26 }
27 }
28 }
29
30 void sieve()
31 {
32 int i, j;
33 memset(is_prime, -1, sizeof(is_prime));
34 prime_cnt = 0;
35 is_prime[0] = is_prime[1] = 0;
36 for (i = 2; i <= 100000; i++) {
37 if (is_prime[i]) {
38 for (j = 2; i * j <= 100000; j++) {
39 is_prime[i*j] = 0;
40 }
41 prime[prime_cnt++] = i;
42 }
43 }
44 }
45
46 class Underprimes {
47 public:
48
49 int howMany(int A, int B)
50 {
51 int i, res;
52 sieve();
53 fact_sieve();
54 res = 0;
55 for (i = A; i <= B; i++) {
56 if (is_prime[n_fact[i]])
57 res++;
58 }
59 return res;
60 }
61
62 };
[550] BedroomFloor
더보기
Problem Statement
You have decided to put new floor tiles on your bedroom floor. Consider an infinite pattern made of 1x5 wooden panels as in the picture below. The top-left corner of the picture has coordinates (0, 0). X coordinates increase from left to right, and y coordinates increase from top to bottom.
You have chosen a rectangular area within this infinite pattern that matches the exact size of your bedroom. The top-left corner of the rectangle is at (x1, y1) and the bottom-right corner is at (x2, y2). You want to reproduce this section on your bedroom floor.
The store that sells wooden floor panels only carries 1x5 panels. You can cut panels to get smaller panels, but you can't glue panels together to get larger ones. For example, you can cut a 1x5 panel to get one 1x3 panel and one 1x2 panel, or two 1x2 panel and one 1x1 panel, etc.
The picture above shows the rectangular area (8, 5, 20, 16). You need twenty-three 1x5 panels, six 1x2 panels and five 1x1 panels. You have to buy total of 27 panels to make these.
You are given ints x1, y1, x2 and y2. Return the minimum number of panels you must buy at the store to produce the pattern in the given rectangular area.
Definition
Class:
BedroomFloor
Method:
numberOfSticks
Parameters:
int, int, int, int
Returns:
long
Method signature:
long numberOfSticks(int x1, int y1, int x2, int y2)
(be sure your method is public)
Notes
-
You can throw away any part of a panel that you don't need.
Constraints
-
x1, y1, x2 and x2 will be between 0 and 1000000, inclusive.
-
x2 will be strictly greater than x1.
-
y2 will be strictly greater than y1.
Examples
0)
0
0
5
5
Returns: 5
This rectangular area contains five 1x5 panels.
1)
0
0
10
2
Returns: 5
This rectangular area contains two 1x5 panels and five 1x2 panels. We have to buy 5 panels to make these.
2)
2
2
8
8
Returns: 12
This rectangle contains twelve 1x3 panels. We can't glue panels together, so we have to buy 12 panels.
3)
8
5
20
16
Returns: 27
The example depicted in the problem statement.
4)
0
0
1000000
1000000
Returns: 200000000000
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..
[950] NowhereLand
더보기
Problem Statement
You are the king of Nowhere Land. You've recently received some big donations, so you've decided to hire more guards to protect your country. There are k different guarding companies in Nowhere Land. Each guarding company has agencies in various cities. If a guarding company has an agency in a city, then that company is allowed to have at most one guard working in that city. Otherwise, the company is not allowed to have any guards in that city. As long as you obey this rule, you can add as many new guards as you want. However, you cannot fire or move existing guards.
There's one problem though. Some pairs of cities cooperate with each other and have certain requirements when hiring guards. If city A cooperates with city B, and a certain company has a guard working in city A but not city B, that is considered a conflict. For each pair of cooperating cities, each distinct company that breaks this rule counts as a conflict, so there may be multiple conflicts within a single pair of cities.
You are given a vector <string> cities. The number of elements in cities is equal to the number of cities in Nowhere Land. The j-th character of the i-th element of cities is '1' (one) if cities i and j cooperate, and '0' (zero) otherwise. You are also given vector <string>s guards and agencies. The i-th element of guards is a space separated list of guarding companies that already have guards working in city i. The i-th element of agencies is a space separated list of guarding companies that have an agency in city i. Each guarding company is represented as an integer between 0 and k-1, inclusive. Return the minimum possible number of conflicts that can exist after hiring additional guards.
Definition
Class:
NowhereLand
Method:
placeGuards
Parameters:
vector <string>, int, vector <string>, vector <string>
Returns:
int
Method signature:
int placeGuards(vector <string> cities, int k, vector <string> guards, vector <string> agencies)
(be sure your method is public)
Constraints
-
cities will contain between 1 and 50 elements, inclusive.
-
The number of characters in each element of cities will be equal to the number of elements in cities.
-
Each character of each element of cities will be a zero ('0') or a one ('1').
-
The i-th character of i-th element of cities will be '0'.
-
The i-th character of j-th element of cities will be the same as the j-th character of i-th element.
-
k will be between 1 and 50, inclusive.
-
cities, guards and agencies will all contain the same number of elements.
-
Each element of guards will contain between 0 and 50 characters, inclusive.
-
Each element of guards will be a single space separated list of distinct integers between 0 and k - 1, inclusive, with no extra leading zeroes, without leading or trailing spaces.
-
Each element of agencies will contain between 0 and 50 characters, inclusive.
-
Each element of agencies will be a single space separated list of distinct integers between 0 and k - 1, inclusive, with no extra leading zeroes, without leading or trailing spaces.
-
For each integer in the i-th element of guards, this integer will also be in the i-th element of agencies.
Examples
0)
{ "0111",
"1000",
"1000",
"1000" }
1
{ "0", "", "", "" }
{ "0", "0", "", "0" }
Returns: 1
There's only one guarding company in Nowhere Land. You can hire additional guards in cities 1 and 3. The best solution is to hire guards in both these cities. Then there will be just one conflict (between cities 0 and 2).
1)
{ "011",
"101",
"110" }
1
{ "0", "", "" }
{ "0", "", "" }
Returns: 2
You can't hire additional guards here. There are 2 conflicts (between cities 0 and 1 and cities 0 and 2).
2)
{ "011",
"101",
"110" }
1
{ "", "", "" }
{ "0", "0", "0" }
Returns: 0
There are two possible solutions. You can hire a guard in each of the three cities and get rid of all conflicts. Alternatively, don't hire anybody and there will also be no conflicts.
3)
{ "010100",
"101100",
"010011",
"110010",
"001100",
"001000" }
3
{ "1 2", "", "1", "", "0", "0" }
{ "0 1 2", "0 1", "0 1 2", "1 2", "0", "0" }
Returns: 7
In this example there are 3 guarding companies. A possible solution is to hire a guard from company 0 in city 2 and guards from company 1 in cities 1 and 3. As a result, there will be 7 conflicts: two between cities 3 and 4 and one between cities 0 and 1, 0 and 3, 1 and 2, 2 and 4, 2 and 5.
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.
각 city에 guard를 배치하려고 한다.. guard를 제공하는 company가 k 개 있고.. 각 company가 지원할 수 있는 city는 정해져있다.. 또한 이미 몇 city에는 임의의 company의 guard가 배치되어있다.. 각 city마다 협력하는 city가 있는데.. city i 와 j 가 협력관계라면 i에 a 회사의 guard가 배치되어있다면 j에도 a 회사의 guard가 배치되어야 한다.. 그렇지 않으면 conflct 라고 한다.. 임의의 guard를 더 추가한다고 할 때 발생하는 conflct 를 최소하하기..
문제 이해하는게 드럽게 어렵지만.. 일단 이해하고 나면 쉬운문제이다..
하나의 city에는 하나의 company의 guard만 배치될 필요는 없다.. 즉, 여러명을 한곳에 배치해도 된다는말..
그래서 각 company 끼리는 서로 무관하므로 독립적으로 생각해서 풀면 된다..
이미 guard가 배치된곳을 source쪽으로 연결하고 guard를 배치할 수 없는곳을 sink에 연결하여
min cut을 구하면 된다..
이것도 minimum vertex cover = min cut 이런 개념인것인가..??
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <queue>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 //#define max(x, y) ((x) > (y) ? (x) : (y))
10 #define INF 999999999
11 #define MAXN 201
12
13 int graph[MAXN][MAXN];
14 int n, m;
15
16 int get_augment_path(int s, int t)
17 {
18 int i, j, c;
19 int min1;
20 int path[MAXN];
21 queue<int> q;
22 q.push(s);
23 memset(path, -1, sizeof(path));
24 while (!q.empty() && path[t] == -1) {
25 c = q.front();
26 /* for (i = 0; i < n; i++) { <--- if 0-based index */
27 for (i = 0; i <= n; i++) {
28 if (path[i] == -1 && graph[c][i] > 0) {
29 path[i] = c;
30 q.push(i);
31 }
32 }
33 q.pop();
34 }
35 if (path[t] == -1)
36 return 0;
37 min1 = INF;
38 j = t;
39 for (i = path[j]; j != s; i = path[j = i]) {
40 if (min1 > graph[i][j])
41 min1 = graph[i][j];
42 }
43 j = t;
44 for (i = path[j]; j != s; i = path[j = i]) {
45 graph[i][j] -= min1;
46 graph[j][i] += min1;
47 }
48 return min1;
49 }
50
51 int ford_fulkerson(int s, int t)
52 {
53 int c, flow;
54 flow = 0;
55 while ((c = get_augment_path(s, t)) > 0) {
56 flow += c;
57 }
58 return flow;
59 }
60
61 class NowhereLand {
62 public:
63
64 int placeGuards(vector <string> cities, int k, vector <string> guards, vector <string> agencies)
65 {
66 int size;
67 int gd[200][200];
68 int ag[200][200];
69 int i, j, a, l;
70 int res;
71 char buf[200];
72 char* ptr;
73
74 size = cities.size();
75 memset(gd, 0, sizeof(gd));
76 memset(ag, 0, sizeof(ag));
77 for (i = 0; i < size; i++) {
78 strcpy(buf, guards[i].c_str());
79 ptr = strtok(buf, " ");
80 while (ptr != NULL) {
81 sscanf(ptr, "%d", &a);
82 gd[i][a] = 1;
83 ptr = strtok(NULL, " ");
84 }
85 }
86 for (i = 0; i < size; i++) {
87 strcpy(buf, agencies[i].c_str());
88 ptr = strtok(buf, " ");
89 while (ptr != NULL) {
90 sscanf(ptr, "%d", &a);
91 ag[i][a] = 1;
92 ptr = strtok(NULL, " ");
93 }
94 }
95
96 res = 0;
97 n = size+1;
98 for (i = 0; i < k; i++) {
99 memset(graph, 0, sizeof(graph));
100 for (j = 0; j < size; j++) {
101 for (l = 0; l < size; l++) {
102 if (cities[j][l] == '1') {
103 graph[j+1][l+1] = 1;
104 }
105 }
106 }
107 for (j = 0; j < size; j++) {
108 if (gd[j][i])
109 graph[0][j+1] = INF;
110 if (!ag[j][i])
111 graph[j+1][size+1] = INF;
112 }
113 res += ford_fulkerson(0, n);
114 }
115 return res;
116 }
117
118 };
일정 구간내의 소수(Prime Number)를 모두 찾아내는 에라토스테네스의 체(Sieve of Eratosthenes)와 비슷하게, 일정 구간내의 소인수 개수를 모두 찾아내는 Sieve가 있어서 기록해둔다. (즉, 12라면, 2 * 2 * 3 으로 소인수 분해가 되기때문에, 이 개수는 3이다.) 기본 원리는 다음과 같다. 어떤 수 x가 다른 두 수 a와 b의 곱으로 나타내어 진다면, 이 x가 가지는 소인수의 수는, a와 b가 가진 소인수의 개수의..
