## TopCoder SRM375 DIV2 (Complete)

The problem set was good.. and fairly easy but with my poor skills.. I lost many points.. ㅠ_ㅠ I always feel lost after each SRM.. It was 2:00 AM and I was trying to concentrate on it.. but it was hard.. and I made many mistakes during the coding phase consequently I counldn't solve 950 problem..

10th place in my room and 204th in div2

Even 204th place is the highest record in my recent matches.. Oh my..;;

Only a few points up and failed to get my green back..

[250] MixtureDensity
string이 여러개 들어오고 mass와 volume을 각각 파싱해서 총 밀도를 구하는 문제..

Simply an easy parsing problem.. but I did a crazy thing during the match..

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 class MixtureDensity {
9 public:
10
11 double getDensity (vector<string> ingredients)
12 {
13     int size;
14     int g, m;
15     int a, b, i, j;
16     char buf[1000], temp[1000];
17     g = m = 0;
18     size = ingredients.size();
19     for (i = 0; i < size; i++) {
20         strcpy(buf, ingredients[i].c_str());
21         a = atoi(buf);
22         for (j = 0; j < strlen(buf); j++) {
23             if (buf[j] == ',')
24                 break;
25         }
26         sscanf(&buf[j+1], "%s%d%s", temp, &b, temp);
27         m += a;
28         g += b;
29 //printf("m = %d ,  g= %d\n", m, g);
30     }
31     return (double)g / (double)m;
32 }
33
34 };

[550] DukeOnChessBoard
n by n 보드가 있고 시작 점이 주어질때 갈수있는 path중에 lexy-greatest를 구하는 문제.. 단 한번 밟은 지점은 다시 갈 수 없다.. 행은 1 2 3.. 열은 a b c 로 표시됨..

I found the pattern and solved it with DFS.. It's pretty much easy..

1) go to the right if possible..
2) if 1) is not possible, then go up
3) if 1) and 2) are not possible, then go down
4) if 1) and 2) and 3) are not possible, then go left
5) if all above are not possible, we got the answer..

Btw, converting string to char* (vice versa) always bothering me.. I don't know C++ ㅠ_ㅠ

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 char check[128][128];
9 char path[10000][2];
10 char str[10000];
11 int N;
12
13 void dfs(int u, int v, int cnt)
14 {
15     int i, j;
16     check[u][v] = 1;
17     path[cnt][0] = u;
18     path[cnt][1] = v;
19 //printf("(%c, %c), cnt = %d \n", u, v, cnt);
20     if (u+1 < 'a'+N && check[u+1][v] == 0) {
21         dfs(u+1, v, cnt+1);
22     }
23     else if (v+1 <= N+'0' && check[u][v+1] == 0) {
24         dfs(u, v+1, cnt+1);
25     }
26     else if (v-1 > '0' && check[u][v-1] == 0) {
27         dfs(u, v-1, cnt+1);
28     }
29     else if (u-1 >= 'a' && check[u-1][v] == 0) {
30         dfs(u-1, v, cnt+1);
31     }
32     else {
33     j = 0;
34     for (i = 0; i <= cnt; i++) {
35         str[j++] = path[i][0];
36         str[j++] = path[i][1];
37         if (i < cnt) {
38             str[j++] = '-';
39         }
40     }
41     str[j] = 0;
42     }
43 }
44
45 class DukeOnChessBoard {
46 public:
47
48 string dukePath(int n, string initPosition)
49 {
50     int i, j, k;
51     int x, y, len;
52     char buf[1000];
53     string ret;
54     N = n;
55     memset(check, 0, sizeof(check));
56     strcpy(buf, initPosition.c_str());
57     x = *buf;
58     y = buf[1];
59     dfs(x, y, 0);
60     len = strlen(str);
61     if (len <= 40) {
62         ret = str;
63         return ret;
64     }
65     for (i = j = 0; i < 20; i++, j++) {
66         buf[i] = str[j];
67     }
68     buf[i++] = '.';
69     buf[i++] = '.';
70     buf[i++] = '.';
71     j = len-20;
72     for (k = 0; k < 20; k++, j++) {
73         buf[i++] = str[j];
74     }
75     buf[i] = 0;
76     ret = buf;
77     return ret;
78 }
79
80 };

[950] DivisibleByDigits
주어진 수자로 시작하면서 처음 주어진 수의 모든 digit으로 나눠질수 있는 최소의 수 구하기..

This is a kind of easy problem.. I knew the solution but I was struggling with previous 2 problems and I didn't get enough time.. Within 10 minutes I give it a shot.. but I couldn't find my bug (which was "lld" which should be "%lld" -_-) and couldn't submit.. My condition is almost zero.. ㅠ_ㅠ

This kind of problem is well known and can be solved by BFS.. UVa-10993 is a similar problem..

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <queue>
7 #include <set>
8 using namespace std;
9
10 long long gcd(long long a, long long b)
11 {
12     if (b == 0)
13         return a;
14     return gcd(b, a % b);
15 }
16
17 long long lcm(long long a, long long b)
18 {
19     return (a*b / gcd(a, b));
20 }
21
22
23 class DivisibleByDigits {
24 public:
25
26 long long getContinuation(int n)
27 {
28     char buf[100];
29     int i, len;
30     long long l, c, p;
31     sprintf(buf, "%d", n);
32     l = 1;
33     for (i = 0; i < strlen(buf); i++) {
34         if (buf[i]-'0' == 0)
35             continue;
36         l = lcm(l, buf[i]-'0');
37     }
38     set<long long> s;
39     s.insert(n % l);
40
41     queue<long long> q;
42     q.push(n);
43     while (!q.empty()) {
44         c = q.front();
45         q.pop();
46 printf("c = %lld...\n", c);
47         if (c % l == 0) {
48             return c;
49         }
50         sprintf(buf, "%lld", c);
51         len = strlen(buf);
52         for (i = 0; i < 10; i++) {
53             buf[len] = i+'0';
54             buf[len+1] = 0;
55             sscanf(buf, "%lld", &p);
56             if (p % l == 0)
57                 return p;
58             if (s.find(p%l) == s.end()) {
59                 q.push(p);
60                 s.insert(p%l);
61             }
62         }
63     }
64     return c;
65 }
66
67 };

Or I think we can just put digits (starting at 1) after the original number in bruteforce manner.. Worst case we only have to put 4 digits.. The reason is explained here.. (the LCM of 1 through 9 is 2520 and pigeonhole principle can be applied..) But I don't get it.. ;;; What is Pigeonhole Principle ?!

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

TopCoder SRM382 DIV2  (2) 2007.12.13 2007.12.09 2007.12.08 2007.11.29 2007.11.21 2007.11.07 2007.10.24 2007.10.18 2007.10.14 2007.10.14

to Top