어제 새벽 1시에 열린 매치..~
이번에도 중국애들이 너무 많이 참여해서.. 1850 limit이 다 차버렸다..~
덕분에 채팅방에서는 limit 좀 늘려달라고 원성이 자자했다..~
나는 저번에 한번 당했기때문에 이번에는 3시간 전에 미리 등록..;;

이번 매치에서는 250을 비교적 빨리 풀어서 다시 yellow로 복귀했다..~
250을 풀고나서 550을 열었는데.. 코딩이 좀 난해해서 정확히 코딩할 자신이 없었다..
그래서 남은시간엔 그냥 놀았다.. -_-;;
흠.. 앞으로 550-950 set 이 나오면 950부터 열어야겠다..~




[250] Underprimes

더보기

어떤 수 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

더보기




to be updated..



[950] NowhereLand

더보기

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



 

Comments

  1. Chaika 2009.06.14 15:46 신고 Permalink Modify/Delete Reply

    ㅋㅋㅋ 전 문제 읽자마자 형 블로그 달려와서 에라토스테네스 복.붙. 해갔어요 ㅋㅋㅋ

  2. mynotepad 2009.06.14 17:10 신고 Permalink Modify/Delete Reply

    헉.. 나도 그렇게 할껄.. 괜히 삽질하다가 1시간이나 걸렸네... -0-

  3. Chaika 2009.06.18 11:38 신고 Permalink Modify/Delete Reply

    헐...... 형이 짠 코드 지금 침착하게 봤는데,

    전 그냥 sieve로 했는데, 형 코드에는 factorization sieve가 있네요.

    뭔가하고 따라가봤는데 진짜 멋진 코드인듯 ㅠㅠ

    (형 말마따나 그냥 sieve는 필요없고 위의 fact_sieve만 있으면 되겠는데요 ㅎㅎ)

    • helloneo 2009.06.18 13:20 신고 Permalink Modify/Delete

      어.. n_fact[i] == 1 인 i 가 곧 prime이니깐.. 다른사람코드를 보니.. sieve를 변형해서 푼 사람 꽤 있던데..~

  4. Chaika 2009.06.23 15:12 신고 Permalink Modify/Delete Reply

    트랙백 해갔어요~ ㅋㅋ

    근데 한번 수정했는데 이상하게되었네요;;;

    트랙백이 2개가 남아버렸네;;;;

  5. 안녕하세요 2016.08.26 22:41 신고 Permalink Modify/Delete Reply

    안녕하세요? nowhereland 소스코드 잘 읽었습니다. 제가 여쭤보고 싶은게 있는데요. 각 도시에서 경비를 고용한 도시는 어디이고 고용을 안한 도시는 어디인지를 출력하는 방법을 알고싶은데요. 혹시 그 방법을 알고계신가요?

    • helloneo 2016.08.28 22:23 신고 Permalink Modify/Delete

      너무 오래된 포스팅이라 무슨 문제인지도 모르겠지만,,
      ford fulkerson 으로 구했다면 residual network 상태를 보면 되지 않을까요?
      a -> b 로 1 만큼 보냈다면 graph[a][b] 가 1만큼 감소해있을 것 같네요..

    • 안녕하세요 2016.08.30 07:35 신고 Permalink Modify/Delete

      댓글 감사합니다.

      http://stackoverflow.com/questions/21471043/find-all-edges-in-min-cut

      사실 여기서 도움 얻었습니다. 수고하세용

Leave a Comment


to Top