## 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.11 2007.11.07 2007.10.24 2007.10.18 2007.10.14 2007.10.14

1. soyoja 2007.11.13 03:06

Why are you writing in English?? Did you decide to practice English writings?
In this SRM, problems were nice, but also with my poor skills.... GG

• 2007.11.13 11:02 신고

Just a practice and to remark the moment of going to USA.. I'm in Reno.. ^^

2. astein 2007.11.22 23:16

char *s 로 되어 있는 문자를 string S로 변환하기 위해서는
S = s; 를 해 주면 됩니다! 그리고 string -> char *로 해 주려면
S.c_str() 을 사용하면 되던걸로... (가물가물)

• 2007.11.22 23:39 신고

네.. 저도 그것만 알아요..;; string클래스 사용법을 배우던가해야지.. 매번 바꾸기 귀찮네요..;;;;

3. astein 2007.11.22 23:22

그리고 Pigeonhole Principle.. 우리 말로 직역하면 "비둘기 집의 원리" 라고 하는데요.
비둘기 집이 n개 있고, 비둘기가 n + 1마리 있는 경우 모든 비둘기가 비둘기 집에 들어갔다고 가정할 때
"어떤 비둘기 집에는 두 마리 이상의 비둘기가 있다" 라고 할 수 있게 되지요.
1~9의 LCM이 2520이기 때문에, 4자리 수인 0000 ~ 9999 사이에 있는 수 중에 항상 답이 존재한다. 라고 말할 수 있게 되는 것입니다. [이 경우엔, 비둘기 집이 2520개 있고, 비둘기가 10000마리 있다..고 보면 되겠지요]

• 2007.11.22 23:47 신고

음.. 비둘기집의원리가 그런것이군요.. 아직 적용이 어렵네요..