지난 수요일 8시에 열린 매치..~
방배정 운도 없어서.. 5번방 -_- 타겟 두명이 있더라..~
그래도 250 이 좀 어려웠는지 낮은 점수를 맞고도 rating 이 상승했다..~





Level1 - CarrotJumping

더보기


현재 위치가 x 라면 4 * x + 3 또는 8 * x + 7 의 위치로 갈 수 있다.. x = 0 (mod 100000007) 의 위치로 가위해한 최소 jump 구하기..

상태공간이 최대 1000000007 개 나올 수 있을거같아서 한참 고민하다가.. 잘 생각해보니 상태가 겹치는게 많아서 그냥 fail 을 각오하고 BFS 로 풀었다.. 근데 그냥 pass 해버렸다.. ㅋㅋ

우리방에서 저렇게 푼 사람은 나밖에 없었다.. -_-;;
다른 풀이법은 잘 모르겠음.. -_-;; 참고

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 #include <set>
  8 #include <map>
  9 using namespace std;
 10 //#define min(x, y) ((x) > (y) ? (y) : (x))
 11 //#define max(x, y) ((x) > (y) ? (x) : (y))
 12 //#define INF 999999999
 13 //#define EPS 1e-14
 14
 15 class CarrotJumping {
 16 public:
 17
 18 int theJump(int init)
 19 {
 20     int i;
 21     long long x, y, temp;
 22     int c;
 23     queue<long long> q;
 24     map<long long, int> mm;
 25
 26     q.push(init);
 27     mm[init] = 0;
 28
 29     while (!q.empty()) {
 30         temp = q.front();
 31         q.pop();
 32         c = mm[temp];
 33         if (c > 100000)
 34             break;
 35         if (temp == 0)
 36             break;
 37         x = (4 * temp + 3) % 1000000007;
 38         y = (8 * temp + 7) % 1000000007;
 39         if (mm.find(x) == mm.end()) {
 40             mm[x] = c+1;
 41             q.push(x);
 42         }
 43         if (mm.find(y) == mm.end()) {
 44             mm[y] = c+1;
 45             q.push(y);
 46         }
 47     }
 48 printf("temp = %lld, c = %d\n", temp, c);
 49     if (temp == 0 && c <= 100000)
 50         return c;
 51     return -1;
 52 }
 53
 54 };




Level2 - KiwiJuice

더보기



to be updated..



Level3 - RandomApple

더보기



to be updated..






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

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
SRM 472 - 현충일 새벽에 삽질..  (0) 2010.06.07
SRM 470  (0) 2010.05.28
TCO10 Qual3 - 이런 젠장  (0) 2010.05.25

Comments

  1. mynotepad 2010.08.16 01:07 신고 Permalink Modify/Delete Reply

    250 ACRush 가 푼 방법이랑 같네... ;)

Leave a Comment


to Top