지난 주 토->일 넘어가는 새벽 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은 체크할 필요가 없네.. 저걸 왜만들었지..;;

  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 };




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 434 Div 1  (0) 2009.02.10
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

Leave a Comment


to Top