## TopCoder SRM 367 Div 2 (완료)

오랜만에 복귀한 DIV2.. 결과는 무척 아쉬웠다..
초반부터 객기를 부려서 1000부터 오픈했지만.. 해석이안되서 포기하고 500 250 순으로 열었다.. -_-;;
500 250은 쉽게 풀고.. 나중에 1000도 도전했지만.. 정말 아쉽게 못풀었다.. 흑.. ㅠ_ㅠ 단 한줄때문에.. ㅠ_ㅠ
방 5등 전체 114등.. 헐.. ㅠ_ㅠ 문제는 쉬웠는데 넘 아쉽다.. 이젠 DIV2에서도 밀리는구나.. ㅠ_ㅠ 아무리 그래도 넘 쪼금오른거 아니가?

 WhiteCells

input으로 chess판이 주어지고.. 흰색 칸에 놓여있는 unit의 개수를 세는 문제..
아무리 easy라지만.. 너무한거 아냐.. -_-

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 class WhiteCells {
9 public:
10
11 int countOccupied (vector<string> board)
12 {
13     char map;
14     int i, j, cnt;
15     for (i = 0; i < 8; i++) {
16         strcpy(map[i], board[i].c_str());
17     }
18     cnt =0;
19     for (i = 0; i < 8; i++) {
20     for (j = 0; j < 8; j++) {
21         if ((i+j)%2 == 0) {
22             if (map[i][j] == 'F')
23                 cnt++;
24         }
25     }
26     }
27     return cnt;
28 }
29
30 };

 ObtainingDigitK

임의의 숫자가 들어오면 덧셈을 한 결과에 K가 들어있도록 더해야하는 최소 수 구하기..
역시 별로 어렵지않지만.. 약간 tricy할수도있다..

나같은경우 귀찮은거 생각하기 싫어서.. 예전에 만들어논 big int루다가.. ㅋㅋ
물론 내가 만든 big int는 아니고.. SCCC누군가가 만든거..

1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 void add(char* a, char* b, char* c)
9 {
10     int len_a, len_b, len, i, j, k;
11
12     len_a=strlen(a), len_b=strlen(b);
13     len=len_a>len_b?len_a:len_b;
14     for(i=len_a-1, j=len_b-1, k=len-1; i>=0 || j>=0; i--, j--, k--){
15         if(i>=0 && j>=0) c[k]=a[i]+b[j]-'0';
16         else if(i>=0) c[k]=a[i];
17         else c[k]=b[j];
18     }
19     for(i=len-1; i>0; i--) if(c[i]>9+'0') c[i-1]++, c[i]-=10;
20     c[len]='\0';
21     if(c>9+'0'){
22         for(i=len+1; i>0; i--)
23             c[i]=c[i-1];
24         c='1', c-=10;
25     }
26 }
27
28 int check(char* buf, int len, char ch)
29 {
30     int i;
31     for (i = 0; i < len; i++) {
32         if (buf[i] == ch)
33             return 1;
34     }
35     return 0;
36 }
37
38 class ObtainingDigitK {
39 public:
40
41 int minNumberToAdd(string originalNumber, int k)
42 {
43     int i, fl;
44     char str1, str2, str3;
45     fl = 0;
46     strcpy(str1, originalNumber.c_str());
47     for (i = 0; ; i++) {
48         sprintf(str2, "%d", i);
50         if (check(str3, strlen(str3), k+'0'))
51             break;
52     }
53     return i;
54 }
55
56 };

 ProgramingDevice

훔.. 이거는 문제를 설명하기가 힘들다.. -_-;;
offset과 size가 각각 배열로 들어오고(각각이 쌍이다).. 최대 packet 크기가 들어온다..
각각 메모리 offset이 시작 주소이고 size만큼 data를 써야하는데..
그러게 하기 위해서 전송해야하는 최대 packet수를 구하는 문제..
메모리 중간에 생기는 구멍에는 data를 쓰던지 말던지 상관없다.
그리고 메모리 주소가 overlap되는 input은 안들어온다.

아.. 젤 아쉬웠던 문제이다.. 종료 1분전에 submit했는데.. sysfail..  나중에알고보니.. 한줄만 고치니 AC나왔다.. 아.. 250 500 잽싸게 풀고.. 좀 여유롭게 생각하면서 풀면 풀었을텐데.. 젠장.. 어이없이 1000점 놓쳤다.. ㅠ

솔루션은 n^3 DP(MCM)로 풀었다.. 다른 사람 코드를 보니.. 나와 비슷하게 푼사람이 별로 없다.. 훔.. 다들 어떻게 푼거지..?

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
9 class ProgrammingDevice {
10 public:
11
12 int minPackets(vector <int> offset, vector <int> size, int maxData)
13 {
14     int n, min1;
15     int dp;
16     int i, j, k;
17     n = offset.size();
18     for (i = n-1; i >= 0; i--) {
19     for (j = 0; j < i; j++) {
20         if (offset[j] > offset[j+1]) {
21             k = offset[j];
22             offset[j] = offset[j+1];
23             offset[j+1] = k;
24             k = size[j];
25             size[j] = size[j+1];
26             size[j+1] = k;
27         }
28     }
29     }
30     for (i = 0; i < n; i++) {
31         if (size[i] % maxData == 0)
32             dp[i][i] = size[i] / maxData;
33         else
34             dp[i][i] = size[i] / maxData + 1;
35     }
36     for (i = 2; i <= n; i++) {
37         for (j = 0; i+j-1 < n; j++) {
38             min1 = offset[i+j-1]+size[i+j-1]-offset[j];
39             if (min1 % maxData == 0)
40                 min1 = min1 / maxData;
41             else
42                 min1 = min1 / maxData + 1;
43             for (k = j; k < i+j-1; k++) {
44                 min1 = min(min1, dp[j][k] + dp[k+1][i+j-1]);
45             }
46             dp[j][i+j-1] = min1;
47         }
48     }
49     return dp[n-1];
50 }
51
52 };

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

 TopCoder SRM 372 Div 2  (8) 2007.10.18 2007.10.14 2007.10.14 2007.10.05 2007.10.03 2007.09.27 2007.09.18 2007.09.13 2007.09.09 2007.08.12 2007.08.08

아흑.. 속상해!
문제를 꼼꼼히 안읽어서 나는 gg...
ps ) Big Int 함수 어딘가에서 본듯했는데 출처가 SCCC 였군... =)

• 2007.09.27 10:59 신고

음.. 쉬운거같아도 꼼꼼히 안보면 가차없이 fail이네요.. 저도 계속 당하는중.. ㅠ_ㅠ

2. defihition 2007.09.27 22:43 신고

음 빠르네요
나도 열심히 해야하는데 ㅠㅠ

• 2007.09.27 23:58 신고

음.. 첫문제 푼걸 축하해..~!

3. 2007.09.28 13:53 신고

다음엔 꼭 참가할께요. 그런데 문제 파악이 중요한가 보네요..

• 2007.09.28 14:46 신고

어.. 한번 써밋하면 끝이기때문에.. 한번에 완벽하게 짜야해..~

4. philosup 2007.09.29 01:04

add함수를 보고 있자니 내 스타일이 많이 묻어 있긴한데;; 내꺼 아닌거 같기도 하고;;
예전에는 저렇게 하기도 했겠다 싶기도 하고;;; 하여간 새롭군~
나도 탑코더나 다시 해볼까 했지만 시간대가 영;;

• 2007.09.29 03:17 신고

형도빨리 탑코더에 동참해여..~
음.. 근데.. 형 블로그에는 새로운 포스팅이 안올라오던데요..? -_-?

5. philosup 2007.10.04 11:36

내 블로그는.... 관리를 제대로 안하니까 방문자수가 많은거 보면 아마 나보다 다른사람들이 더 많이 들어가는듯 ㅋ

• 2007.10.04 12:53 신고

음.. 추종자들이 많나보네요.. ㅎㅎ