## SRM 477

어제 밤 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 2010.09.26 2010.09.16 2010.08.16 2010.08.08 2010.07.29 2010.07.20 2010.06.07 2010.05.28 2010.05.25 2010.05.13

to Top