TopCoder SRM 457 Div 1

Problem Solving/TopCoder logs 2010. 1. 6. 00:18

월요일 저녁 9시에 열린 매치.. 2010 년 첫 SRM 이다..
250 점 문제에서 딱 하나의 케이스를 생각 못해서 챌 당했다.. 젠장
이번엔 시간대가 좋아서 한국사람이 많이 참가했다..
이제 앞으로는 다 새벽시간인데.. 흠.. 이거 연초부터 하기 싫어지는데..





Level1 - TheTriangleBothDivs

? 위치에 임의의 숫자가 들어올 수 있을때.. GMT+0 으로 고쳤을때 가장 빠른시간으로 가능한 시간 구하기..

너무 우습게 보다가 틀린 문제이다..
마땅히 좋은 방법이 생각이 안나서 그냥 backtracking 으로 모든 숫자를 다 넣어보았다..

문제가 되는 경우가.. "12:00 GMT-?" 같은 경우 문제 조건에 따라서 답은 13:00 이 된다..
이 경우를 놓쳐서 나를 비롯하여 많은 사람이 챌 당하였음.. 젠장

  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 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 #define INF 999999999
 10 //#define EPS 1e-14
 11
 12 char buf[100];
 13 char path[100];
 14 int len;
 15 string sol;
 16 int min1;
 17
 18 void dfs(int u)
 19 {
 20     int i;
 21     int hh, mm, tz;
 22     int sum;
 23     char temp[100];
 24     if (u == len) {
 25         path[u] = 0;
 26         sscanf(path, "%02d:%02d GMT%d", &hh, &mm, &tz);
 27         if (hh >= 24)
 28             return ;
 29         if (mm >= 60)
 30             return ;
 31         if (tz > 9 || tz < -9)
 32             return ;
 33         if (path[9] == '-' && path[10] == '0')
 34             return ;
 35         hh -= tz;
 36         hh = ((hh % 24) + 24) % 24;
 37         sum = hh * 60 + mm;
 38         if (sum < min1) {
 39             min1 = sum;
 40             sprintf(temp, "%02d:%02d", hh, mm);
 41             sol = temp;
 42         }
 43         return ;
 44     }
 45
 46     if (buf[u] != '?') {
 47         path[u] = buf[u];
 48         dfs(u+1);
 49         return ;
 50     }
 51
 52     if (u == 9) {
 53         path[u] = '+';
 54         dfs(u+1);
 55         path[u] = '-';
 56         dfs(u+1);
 57         return ;
 58     }
 59     else {
 60         for (i = '0'; i <= '9'; i++) {
 61             path[u] = i;
 62             dfs(u+1);
 63         }
 64     }
 65 }
 66
 67 class TheTriangleBothDivs {
 68 public:
 69
 70 string fix(string time)
 71 {
 72     strcpy(buf, time.c_str());
 73     len = time.size();
 74     min1 = INF;
 75     dfs(0);
 76     return sol;
 77 }
 78
 79 };




Level2 - TheHexagonsDivOne




to be updated..



Level3 - TheSquareDivOne




to be updated..


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

TopCoder Open 2010 일정..  (0) 2010.03.31
SRM 464  (0) 2010.03.18
TopCoder SRM 463  (2) 2010.03.06
TopCoder SRM 459 Div 1  (0) 2010.01.20
TopCoder SRM 458 Div 1  (0) 2010.01.17
[SRM 456] 2009년 마지막 SRM  (0) 2009.12.23
TopCoder SRM 455 Div 1  (0) 2009.12.19
TopCoder SRM 454 Div 1  (0) 2009.12.07
TopCoder SRM 453.5 (??) Div 1  (0) 2009.11.26
[SRM 453] 탑코더 아레나 폭발 -> unrated event  (4) 2009.11.18
  • By helloneo

to Top

티스토리툴바