TopCoder SRM 434 Div 1
Problem Solving/TopCoder logs 2009. 2. 10. 22:38
지난 주 토->일 넘어가는 새벽 2시에 열린 매치..~
오랜만에 밤새면서 탑코더 한판 했다.. 밤새 문제 푸는거.. 정말 오랜만인듯..~~
근데 매치는 또 망쳤다.. ㅠ_ㅠ 챌린지에서 75점이나 깎인게 뼈아팠다.. ㅠ_ㅠ
그래도 사람들이 250을 의외로 많이 fail해주는 바람에 rating은 많이 안떨어졌다.. ㅎ
매치 중간에 잠깐 순위를 봤는데.. 이거 멍미.??
블루들이 전체 2 3등을 달리면 열라 선전하는 것이었다..
근데 자세히보니.. 1000점짜리 점수가 999 -_-;; 관심좀 받고싶었나..? ㅎㅎ
근데 1000점짜리를 열자마자 서밋했는데도 페트르를 못앞서다니..
역시.. 페트르를 신이라고하는 이유가 있군..~
Level1 - FindingSquareInTable
2차원 table이 주어지고 각 cell에는 숫자가 적혀있다.. 임의의 위치에서 시작해서 row와 column이 등차수열로 증가하는 방향으로 이동할때 각 이동하는 cell의 숫자를 붙여서 그 숫자가 sqaure (n^2 꼴의 수)가 되는 수를 찾는다.. 이렇게 만들 수 있는 square 수 중 가장 큰 수 구하기.. arithmatic progression (등차수열) 에서 당연히 공차는 음수도 될 수 있다..
문제를 이해하는데도 좀 오래걸리고.. 코딩하는데도 좀 걸렸다.. 근데 문제 자체가 좀 명확하지 못하게 설명한 부분이 있다.. 처음 시작이 아무 위치에서나 시작할 수 있다는거.. 그리고 마지막 위치도 그냥 중간에 멈출 수 있다는게 설명되어있지않아서.. 그걸 찾아보느라 시간을 많이 낭비했다.. 젠장.. 담부터는 그냥 무작정 코딩부터해야겠다..~~
해결방법은 그냥 brute force.. -_- 이게 도대체 몇중 루프여..;;
아.. 지금보니.. reverse한 string은 체크할 필요가 없네.. 저걸 왜만들었지..;;
to be updated..
Level2 - HexatridecimalSum
1, 2, 3, ... , 9, A, B, C, ... Z 로 이루어진 36진수 수체계에서.. 몇개의 수가 들어오고 K종류의 digit을 모두 Z로 바꿀때.. 입력받은 수들의 합을 최대화하기..
to be updated..
Level3 - IncreasingLists
to be updated..
오랜만에 밤새면서 탑코더 한판 했다.. 밤새 문제 푸는거.. 정말 오랜만인듯..~~
근데 매치는 또 망쳤다.. ㅠ_ㅠ 챌린지에서 75점이나 깎인게 뼈아팠다.. ㅠ_ㅠ
그래도 사람들이 250을 의외로 많이 fail해주는 바람에 rating은 많이 안떨어졌다.. ㅎ
매치 중간에 잠깐 순위를 봤는데.. 이거 멍미.??
블루들이 전체 2 3등을 달리면 열라 선전하는 것이었다..
근데 자세히보니.. 1000점짜리 점수가 999 -_-;; 관심좀 받고싶었나..? ㅎㅎ
근데 1000점짜리를 열자마자 서밋했는데도 페트르를 못앞서다니..
역시.. 페트르를 신이라고하는 이유가 있군..~
Level1 - FindingSquareInTable
2차원 table이 주어지고 각 cell에는 숫자가 적혀있다.. 임의의 위치에서 시작해서 row와 column이 등차수열로 증가하는 방향으로 이동할때 각 이동하는 cell의 숫자를 붙여서 그 숫자가 sqaure (n^2 꼴의 수)가 되는 수를 찾는다.. 이렇게 만들 수 있는 square 수 중 가장 큰 수 구하기.. arithmatic progression (등차수열) 에서 당연히 공차는 음수도 될 수 있다..
문제를 이해하는데도 좀 오래걸리고.. 코딩하는데도 좀 걸렸다.. 근데 문제 자체가 좀 명확하지 못하게 설명한 부분이 있다.. 처음 시작이 아무 위치에서나 시작할 수 있다는거.. 그리고 마지막 위치도 그냥 중간에 멈출 수 있다는게 설명되어있지않아서.. 그걸 찾아보느라 시간을 많이 낭비했다.. 젠장.. 담부터는 그냥 무작정 코딩부터해야겠다..~~
해결방법은 그냥 brute force.. -_- 이게 도대체 몇중 루프여..;;
아.. 지금보니.. reverse한 string은 체크할 필요가 없네.. 저걸 왜만들었지..;;
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <cmath>
7 using namespace std;
8 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 void get_rev(char* buf, int len, char* rev)
11 {
12 int i, j;
13 for (i = 0, j = len-1; i < len; i++, j--) {
14 rev[i] = buf[j];
15 }
16 rev[i] = 0;
17 }
18
19 int is_sq(int a)
20 {
21 int s;
22 s = (int)(sqrt((double)a) + 0.000000001);
23 if (s*s == a) {
24 return 1;
25 }
26 return 0;
27 }
28
29 class FindingSquareInTable {
30 public:
31
32 int findMaximalSquare(vector <string> table)
33 {
34 int r, c;
35 int i, j;
36 int d1, d2;
37 int x, y, a;
38 char map[20][20];
39 char buf[100], rev[100];
40 int len, max1;
41 r = table.size();
42 c = table[0].size();
43 for (i = 0; i < r; i++) {
44 strcpy(map[i], table[i].c_str());
45 }
46 max1 = -1;
47 for (i = 0; i < r; i++) {
48 for (j = 0; j < c; j++) {
49 for (d1 = -r; d1 < r; d1++) {
50 for (d2 = -c; d2 < c; d2++) {
51 if (d1 == 0 && d2 == 0)
52 continue;
53 len = 0;
54 x = i;
55 y = j;
56 while (x < r && x >= 0 && y < c && y >= 0) {
57 buf[len++] = map[x][y];
58 buf[len] = 0;
59 get_rev(buf, len, rev);
60 a = atoi(buf);
61 if (is_sq(a)) {
62 max1 = max(a, max1);
63 }
64 a = atoi(rev);
65 if (is_sq(a)) {
66 max1 = max(a, max1);
67 }
68 x += d1;
69 y += d2;
70 }
71 }
72 }
73 }
74 }
75 printf("max1 = %d\n", max1);
76 return max1;
77 }
78
79 };
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <cmath>
7 using namespace std;
8 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 void get_rev(char* buf, int len, char* rev)
11 {
12 int i, j;
13 for (i = 0, j = len-1; i < len; i++, j--) {
14 rev[i] = buf[j];
15 }
16 rev[i] = 0;
17 }
18
19 int is_sq(int a)
20 {
21 int s;
22 s = (int)(sqrt((double)a) + 0.000000001);
23 if (s*s == a) {
24 return 1;
25 }
26 return 0;
27 }
28
29 class FindingSquareInTable {
30 public:
31
32 int findMaximalSquare(vector <string> table)
33 {
34 int r, c;
35 int i, j;
36 int d1, d2;
37 int x, y, a;
38 char map[20][20];
39 char buf[100], rev[100];
40 int len, max1;
41 r = table.size();
42 c = table[0].size();
43 for (i = 0; i < r; i++) {
44 strcpy(map[i], table[i].c_str());
45 }
46 max1 = -1;
47 for (i = 0; i < r; i++) {
48 for (j = 0; j < c; j++) {
49 for (d1 = -r; d1 < r; d1++) {
50 for (d2 = -c; d2 < c; d2++) {
51 if (d1 == 0 && d2 == 0)
52 continue;
53 len = 0;
54 x = i;
55 y = j;
56 while (x < r && x >= 0 && y < c && y >= 0) {
57 buf[len++] = map[x][y];
58 buf[len] = 0;
59 get_rev(buf, len, rev);
60 a = atoi(buf);
61 if (is_sq(a)) {
62 max1 = max(a, max1);
63 }
64 a = atoi(rev);
65 if (is_sq(a)) {
66 max1 = max(a, max1);
67 }
68 x += d1;
69 y += d2;
70 }
71 }
72 }
73 }
74 }
75 printf("max1 = %d\n", max1);
76 return max1;
77 }
78
79 };
to be updated..
Level2 - HexatridecimalSum
1, 2, 3, ... , 9, A, B, C, ... Z 로 이루어진 36진수 수체계에서.. 몇개의 수가 들어오고 K종류의 digit을 모두 Z로 바꿀때.. 입력받은 수들의 합을 최대화하기..
to be updated..
Level3 - IncreasingLists
to be updated..
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| TopCoder SRM 437 Div 1 (0) | 2009.03.25 |
|---|---|
| TCO09 Round 1 (0) | 2009.03.08 |
| TCO09 Qual 3 (완료) (0) | 2009.03.05 |
| TCO09 Qual 2 (0) | 2009.03.01 |
| TCO09 Qual 1 (0) | 2009.02.25 |
| TopCoder SRM 432 Div 1 (0) | 2009.01.07 |
| TopCoder SRM 428 Div 1 (0) | 2008.12.03 |
| 탑코더 스름 426 디비젼 1 (0) | 2008.11.25 |
| TopCoder SRM 425 Div 2 (완료) (0) | 2008.11.13 |
| TopCoder SRM 422 Div 1 (4) | 2008.10.19 |