어제 새벽에 열린 매치..~ 이번 매치는 아주 기억에 남는 매치였다..

- 내가 처음으로 Petr를 이겨본 매치이고..
- 무려 14개월만에 yellow를 탈환했다..
- Div1 / Div2 이렇게 많이 fail 한게 언제인지.. 완전 crazy match 였다..~

우리방 결과.. 와우.. 정말 아름다운 매치였다..~

Petr가 Fail/Fail/Fail 을 기록한건 최대 이변이닷..~





Level1 - BestApproximationDiv1

더보기


0.xxxxxx 꼴의 number 가 들어올때, 이 값을 A / B 로 최대한 근사화하고싶다..
가장 적절한 A, B 구하기..

모든 가능한 A, B 에 대해서 다 시도하였다..
이 문제는 precision error 로 fail 한 사람이 무수히 많다..
포럼에 있는 글도 읽어보자..(링크)

  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 class BestApproximationDiv1 {
 13 public:
 14
 15 string findFraction(int maxDen, string number)
 16 {
 17     int max_len, max_no, max_den;
 18     int i, j, k;
 19     char buf[100];
 20     string res;
 21     max_len = 0;
 22     max_no = max_den = 1000000;
 23     for (i = 1; i <= maxDen; i++) {
 24         for (j = 0; j < i; j++) {
 25             sprintf(buf, "%.12lf", (double)j / (double)i);
 26             buf[8] = 0;
 27             for (k = 0; k < 8; k++) {
 28                 if (number[k] != buf[k])
 29                     break;
 30             }
 31             if (k > max_len) {
 32                 max_len = k;
 33                 max_den = i;
 34                 max_no = j;
 35             }
 36             else if (k == max_len) {
 37                 if (i < max_den) {
 38                     max_den = i;
 39                     max_no = j;
 40                 }
 41                 else if (i == max_den) {
 42                     if (j < max_no) {
 43                         max_no = j;
 44                     }
 45                 }
 46             }
 47         }
 48     }
 49     sprintf(buf, "%d/%d has %d exact digits", max_no, max_den, max_len-1);
 50     res = buf;
 51     return res;
 52 }
 53
 54 };



Level2 - Bribes

더보기



to be upated..


Level3 - Sheep

더보기


numSheep 만큼의 sheep 이 있는데 얘네들을 전부 배에 태워서 반대편 강변에 내려야 한다..
최대 maxRun 만큼만 왔다갔다 하고싶을때 배의 크기가 얼마나 되야할까..?
배에 sheep 을 태울때는 무조건 가능한 무거운애부터 태운다..~


to be updated..


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

SRM 501  (0) 2011.04.01
SRM 498 - WTF!!  (0) 2011.02.27
SRM 496  (2) 2011.02.02
SRM 491 - Blue 복귀..  (0) 2010.12.21
SRM 490 - Yellow 1차 방어전 성공..  (0) 2010.12.09
SRM 483 - 처음으로 Petr 이겨본 매치..~  (0) 2010.09.26
SRM 482  (0) 2010.09.16
SRM 479 - 광복절 새벽에 삽질..  (0) 2010.08.16
SRM 478  (2) 2010.08.08
SRM 477  (0) 2010.07.29
SRM 476 - GOOD  (0) 2010.07.20

Leave a Comment


to Top