SRM 477

Problem Solving/TopCoder logs 2010. 7. 29. 23:00
어제 밤 12시에 열린 매치..~





Level1 - Islands

그림과같이 정육각형 모양으로 생긴 지도를 input 으로 나올때, 해변의 길이 구하기..

모든 '#' 에 대해서 주위가 '.' 인지 아닌지를 검사하면 된다..~

  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 class Islands {
 13 public:
 14
 15 int beachLength(vector <string> kingdom)
 16 {
 17     int r, c;
 18     int cnt;
 19     int i, j;
 20     r = kingdom.size();
 21     c = kingdom[0].size();
 22     cnt = 0;
 23     for (i = 0; i < r; i++) {
 24         for (j = 0; j < c; j++) {
 25             if (kingdom[i][j] == '#') {
 26                 if (j-1 >= 0 && kingdom[i][j-1] == '.') {
 27                     cnt++;
 28                 }
 29                 if (j+1 < c && kingdom[i][j+1] == '.') {
 30                     cnt++;
 31                 }
 32                 if (i % 2 == 0) {
 33                     if (i+1 < r && j-1 >= 0 && kingdom[i+1][j-1] == '.') {
 34                         cnt++;
 35                     }
 36                     if (i+1 < r && j >= 0 && kingdom[i+1][j] == '.') {
 37                         cnt++;
 38                     }
 39                     if (i-1 >= 0 && j-1 >= 0 && kingdom[i-1][j-1] == '.') {
 40                         cnt++;
 41                     }
 42                     if (i-1 >= 0 && j >= 0 && kingdom[i-1][j] == '.') {
 43                         cnt++;
 44                     }
 45                 }
 46                 else {
 47                     if (i+1 < r && j+1 < c && kingdom[i+1][j+1] == '.') {
 48                         cnt++;
 49                     }
 50                     if (i+1 < r && j < c && kingdom[i+1][j] == '.') {
 51                         cnt++;
 52                     }
 53                     if (i-1 >= 0 && j+1 < c && kingdom[i-1][j+1] == '.') {
 54                         cnt++;
 55                     }
 56                     if (i-1 >= 0 && j < c && kingdom[i-1][j] == '.') {
 57                         cnt++;
 58                     }
 59                 }
 60             }
 61         }
 62     }
 63 printf("cnt = %d\n", cnt);
 64     return cnt;
 65 }
 66
 67 };



Level2 - PythTriplets

주어진 input 에서 x^2 + y^2 = z^2  을 만족하는 (x, y) pair 를 최대한 많이 찾기..~

쉬운 문제였는데.. 뭔가 색다른 시도를 해보다 틀렸다.. -_-;;
이 문제는 다음 두가지를 해결하면 풀 수 있다..~

1. 모든 pair (a, b) 에 대해서 a*a+b*b 가 어떤수의 제곱꼴인지 판단
2. Bipartite Matching

  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 #define MAXN 251
 12
 13 int n, m;
 14
 15 char graph[MAXN][MAXN];
 16 char check[MAXN];
 17 int match_l[MAXN];
 18 int match_r[MAXN];
 19
 20 int bpm(int u)
 21 {
 22     int i;
 23     for (i = 1; i <= m; i++) {
 24         if (graph[u][i]) {
 25             if (check[i])
 26                 continue;
 27             check[i] = 1;
 28             if (match_r[i] < 0 || bpm(match_r[i])) {
 29                 match_l[u] = i;
 30                 match_r[i] = u;
 31                 return 1;
 32             }
 33         }
 34     }
 35     return 0;
 36 }
 37
 38 int gcd(int a, int b)
 39 {
 40     if (b == 0)
 41         return a;
 42     return gcd(b, a % b);
 43 }
 44
 45 int is_sq(long long a, long long b)
 46 {
 47     long long l, r, mid;
 48     l = 1;
 49     r = 2000000;
 50     while (l <= r) {
 51         mid = (l+r) / 2;
 52         if (a*a+b*b == mid*mid) {
 53             return 1;
 54         }
 55         if (a*a+b*b < mid*mid) {
 56             r = mid-1;
 57         }
 58         else {
 59             l = mid+1;
 60         }
 61     }
 62     return 0;
 63 }
 64
 65 class PythTriplets {
 66 public:
 67
 68 int findMax(vector <string> stick)
 69 {
 70     int i, j, temp;
 71     int cnt;
 72     int num[300];
 73     char buf[100000];
 74     char* ptr;
 75     string str;
 76     str = "";
 77     for (i = 0; i < stick.size(); i++) {
 78         str += stick[i];
 79     }
 80     strcpy(buf, str.c_str());
 81     n = 1;
 82     ptr = strtok(buf, " ");
 83     while (ptr != NULL) {
 84         num[n++] = atoi(ptr);
 85         ptr = strtok(NULL, " ");
 86     }
 87     n--;
 88     m = n;
 89     memset(graph, 0, sizeof(graph));
 90     for (i = 1; i <= n; i++) {
 91         for (j = 1; j <= m; j++) {
 92             temp = gcd(num[i], num[j]);
 93             if (temp != 1)
 94                 continue;
 95             if (is_sq(num[i], num[j])) {
 96                 graph[i][j] = 1;
 97             }
 98         }
 99     }
100
101     memset(match_l, -1, sizeof(match_l));
102     memset(match_r, -1, sizeof(match_r));
103     cnt = 0;
104     for (i = 1; i <= n; i++) {
105         memset(check, 0, sizeof(check));
106         if (bpm(i))
107             cnt++;
108     }
109
110     return cnt / 2;
111 }
112
113 };




Level3 - KingdomTour


to be updated..


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

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 476 - GOOD  (0) 2010.07.20
SRM 472 - 현충일 새벽에 삽질..  (0) 2010.06.07
SRM 470  (0) 2010.05.28
TCO10 Qual3 - 이런 젠장  (0) 2010.05.25
TCO10 Qaul2  (2) 2010.05.13
  • By helloneo

to Top

티스토리툴바