TopCoder SRM 420 Div 2

Problem Solving/TopCoder logs 2008. 10. 3. 00:40
오늘 저녁 8시에 열린 매치.. 오늘은 문제가 쉬웠는지.. 내가 컨디션을 회복중인지(?).. 성적이 괜찮았다..~
내침김에 1000점까지 도전해보았는데.. 아쉽게도 시간이 조금 모자랐다..;;
500점짜리는 나름 괜찮았는데.. 250은 코딩속도가 남들보다 확실히 떨어지는게 보이는군..
흠.. 가뜩이나 어려운문제도 잘 못푸는데.. 쉬운문제를 코딩하는데 너무 오래걸려서.. 항상 고전한다..

방 1등 전체 15등..~ 이렇게해서 3전4기만에 다시 div1으로 복귀..~


사용자 삽입 이미지



Level1 - DeckRearranging
B와 R 두가지 종류의 카드가 섞여있다.. 이 카드를 다시 새롭게 섞는데 그 규칙은 top부터 bottom 방향으로 하나씩 보면서 i번째 카드를 다시 새로운 deck에 insert할때 above[i]개 만큼의 카드가 그 위에 오도록 한다. new deck을 출력하기.

그냥 설명하는데로 simulation 했다.. 나는 배열을 써서 insert할때마다 한칸씩 다 밀었는데.. list 같은 자료구조를 쓰면 중간에 삽입이 가능하다보다. 음.. 쉬운문제 푸는데 왜이리 오래걸리지..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class DeckRearranging {
  9 public:
 10
 11 string rearrange(string deck, vector <int> above)
 12 {
 13     int n, cnt, a;
 14     int i, j;
 15     char buf[100];
 16     char ndeck[100];
 17     string res;
 18     n = above.size();
 19     strcpy(buf, deck.c_str());
 20     cnt = 0;
 21     for (i = 0; i < n; i++) {
 22         a = above[i];
 23         for (j = cnt-1; j >= a; j--) {
 24             ndeck[j+1] = ndeck[j];
 25         }
 26         ndeck[a] = buf[i];
 27         cnt++;
 28     }
 29     ndeck[cnt] = 0;
 30 printf("ndeck = %s\n", ndeck);
 31     return res = ndeck;
 32 }
 33
 34 };



Level2 - YearProgressbar
1년중에 날짜와 시간이 주어지고 그 시점이 1년중 정확히 몇 percent가 지났는지 구하는 문제..

1년이 총 몇분인지 구하고 현재까지 몇분이 지났는지 계산해서 비율을 구했다.. 단순 날짜 계산 노가다 문제.. 이런문제는 너무 싫다.. ㅠ_ㅠ

챌린지 타임때 혹시 month 스펠링 틀린사람 없나 뚤어지게 봤는데.. 스펠링 틀린사람은 없었다..;; 그대신 윤년을 구하는걸 틀린사람 하나 발견.. 챌 하나 성공했다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int DAY[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  9
 10 int get_mon(char* str)
 11 {
 12     if (!strcmp(str, "January"))
 13         return 1;
 14     if (!strcmp(str, "February"))
 15         return 2;
 16     if (!strcmp(str, "March"))
 17         return 3;
 18     if (!strcmp(str, "April"))
 19         return 4;
 20     if (!strcmp(str, "May"))
 21         return 5;
 22     if (!strcmp(str, "June"))
 23         return 6;
 24     if (!strcmp(str, "July"))
 25         return 7;
 26     if (!strcmp(str, "August"))
 27         return 8;
 28     if (!strcmp(str, "September"))
 29         return 9;
 30     if (!strcmp(str, "October"))
 31         return 10;
 32     if (!strcmp(str, "November"))
 33         return 11;
 34     return 12;
 35 }
 36
 37 class YearProgressbar {
 38 public:
 39
 40 double percentage(string currentDate)
 41 {
 42     char buf[100];
 43     char* ptr;
 44     int year, mon, day, mm, hh;
 45     int is_leap, i;
 46     int day_sum;
 47     double tot, cur;
 48     strcpy(buf, currentDate.c_str());
 49     ptr = strtok(buf, " ");
 50     mon = get_mon(ptr);
 51     ptr = strtok(NULL, " ");
 52     day = atoi(ptr);
 53     ptr = strtok(NULL, " ");
 54     year = atoi(ptr);
 55     ptr = strtok(NULL, " ");
 56     sscanf(ptr, "%02d:%02d", &hh, &mm);
 57
 58     is_leap = 0;
 59     if (year % 400 == 0) {
 60         is_leap = 1;
 61     }
 62     else if (year % 4 == 0 && year % 100 != 0) {
 63         is_leap = 1;
 64     }
 65     if (is_leap) {
 66         tot = 366.0 * 1440.0;
 67     }
 68     else {
 69         tot = 365.0 * 1440.0;
 70     }
 71     day_sum = 0;
 72     for (i = 1; i < mon; i++) {
 73         day_sum += DAY[i];
 74         if (i == 2 && is_leap == 1) {
 75             day_sum++;
 76         }
 77     }
 78     day_sum += day-1;
 79     cur = day_sum * 1440.0;
 80     cur += hh * 60.0 + mm;
 81
 82 printf("%lf / %lf\n", cur, tot);
 83
 84     return cur / tot * 100.0;
 85 }
 86
 87 };



Level3 - PrettyPrintingProduct
A와 B가 주어질때, C = A * (A+1) * (A+2) * ... * (B-1) * B 일때 C = D * 10^E 꼴로 나타낼때 C, D, E를 구하기.. C가 10자리가 넘어가면 앞에 5자리와 뒤의 5자리 구하기..

매치때 삽질하다가 결국 서밋을 못했다.. E는 min(getpow(2), getpow(5)) 일듯 싶고, 앞의 5자리는 logarithm, 뒤의 5자리는 modulo로 풀려고 했는데.. 시간이 모자랐다..

우리방에서 2명이 이 문제를 submit 했는데.. log를 안쓰고 풀었길래.. 그냥 챌 해보았다.. 근데 둘다 성공..;; 사실 pass 한사람들도 log를 안썼던데.. 어떻게 푼거지..;;

to be updated..


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

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
TopCoder SRM 421 Div 1  (0) 2008.10.12
TopCoder SRM 418 Div 2  (0) 2008.09.21
TopCoder SRM 417 Div 2  (0) 2008.09.13
TopCoder SRM 416 Div2  (0) 2008.09.07
TopCoder SRM 414 Div 1  (0) 2008.08.17
TopCoder SRM 413 Div 1  (0) 2008.08.08
  • By helloneo

to Top

티스토리툴바