## SRM 483 - 처음으로 Petr 이겨본 매치..~

Problem Solving/TopCoder logs 2010. 9. 26. 22:21

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

- 내가 처음으로 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 한 사람이 무수히 많다..

포럼에 있는 글도 읽어보자..(링크)

Level2 - Bribes

to be upated..

Level3 - Sheep

numSheep 만큼의 sheep 이 있는데 얘네들을 전부 배에 태워서 반대편 강변에 내려야 한다..

최대 maxRun 만큼만 왔다갔다 하고싶을때 배의 크기가 얼마나 되야할까..?

배에 sheep 을 태울때는 무조건 가능한 무거운애부터 태운다..~

to be updated..

- 내가 처음으로 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 };

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

## Comments