[Google Codejam] Qualification Round 2014-Cookie Clicker Alpha


문제 link : https://code.google.com/codejam/contest/2974486/dashboard#s=p1


Magic Trick 에 이어 두번째 문제, Magic Trick 에 비하면 난이도가 있지만 쉬이 풀수 있는 문제이다.


이 문제의 결론은 X 값으로 주어진 cookie 의 개수를 가장 빠른 시간에 만들 수 있도록 하고 그 시간을 답으로 갖게 하는 것이다.


3 가지의 input 이 주어지는데,

C : farm 을 하나 만들 수 있는 cookie 의 개수

F : farm 하나 당 cookie 생산량

X : 최종으로 만들어야 하는 cookie 의 개수


문제의 link 를 보면 예제가 나와있다.

예제를 보면, 초기 cookie 생산량은 초당 "2" 이다.

가정 C = 500.0, F = 4.0, X = 2000.0


1. cookie 0개에서 부터 초당 2개씩 cookie 가 생산된다.

2. 250초 뒤에, 500개의 cookie 가 생산되고 farm 하나를 구입할 수 있다. 구입하게 되면 초당 4개의 cookie 를

생산하는 farm 을 만들 수 있다.

3. farm 을 하나 만들자. 그렇다면 보유하고 있던 cookie 의 개수는 0이 되고 초당 cookie 의 생산량은 6개가 된다.

4. 다음 farm 을 만들 수 있는 cookie 500개를 초당 6개씩 생산하였을 때, 83.3333333 초가 된다.

5. 83.333333 초 뒤에 farm 을 하나더 만들자. 그러면 다시 보유하고 있던 cookie 의 개수는 0이되고, 초당

10개의 cookie 생산량을 갖게된다.

6. 다음 farm 을 만들 수 있는 시간은 50초가 된다.

7. 3번째 farm 을 만들자. 다시 보유하고 있던 cookie 는 0이 되고, 생산량은 14개가 된다.

8. 생산량 14개에서 다음 farm 을 만들 필요는 없다. 왜냐 하면 이 이후의 생산량 증가는 2000개에 도달하는 시간이 점점 커진다. 이제 2000 개를 만들어 보자. 그러면 142.8571429 초가 걸린다.


총 시간은 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 초가 답이 된다.


앞서 쓴데로, C, F, X 가 input으로 주어지고 결과는 소수점 8자리에서 반올림하여 7자리를 만들면 된다.


중요한 점은,

farm 을 만들 것인지 만들지 않고 그냥 cookie 생산을 할 것인지 결정해야 하는 순간이 있다. 7번에서 8번으로 넘어갈때.

이것은 전 단계에서 X 까지 cookie 를 생산하여 걸린 시간과 현재 단계에서 farm 을 만들지 않고 cookie을 target 까지 생산한 값을 비교하여 전 단계에서 시간이 더 짧게 걸렸다면 farm을 만들지 않고 X 값까지 cookie 만든 시간을 return 하면 될 것이다.


코드를 보자.

def CalculateCookies(cookies, extra, target):
        cookieGen = 2 # default cookie
        if cookies > target:
                return target/cookieGen

        farmTime = 0.0
        prevEndTime = farmTime + target / cookieGen
        totalTimeFarm = 0.0

        while True:
                totalTimeFarm = totalTimeFarm + \
                                cookies / (cookieGen + extra * farmTime)
                farmTime = farmTime + 1.0
                currentEndTime = totalTimeFarm + \
                                 target / (cookieGen + extra * farmTime)

                if prevEndTime < currentEndTime:
                        break;
                prevEndTime = currentEndTime

        return prevEndTime

if __name__ == "__main__":
        testcases = input()
        for caseNr in xrange(1, testcases + 1):
                cookies, extra, target = map(float, raw_input().split())

                timeForCookies = CalculateCookies(cookies, extra, target)
                print "Case #%d: %.7f"% (caseNr, round(timeForCookies, 8))


코드가 간단하다. 계산만 잘하면 풀수 있는 문제일 것이다. 



'Algorithm' 카테고리의 다른 글

[GitHub] Algorithm 문제 풀기(TopCoder, Hackerrank)  (1) 2015.11.27
[Google Codejam] Qualification Round 2014-Magic Trick  (0) 2014.04.30
[Algorithm] Python 배우기  (0) 2013.10.09
[Alogithm Practice] CodeChef 소개  (0) 2013.05.15

[Google Codejam] Qualification Round 2014-Magic Trick


문제 link : https://code.google.com/codejam/contest/dashboard?c=2974486


Google Codejam 이 시작되었다. 참가는 하지 않았지만, 하나씩 풀어 보려고 노력중이다.

이 문제는 처음 시작하는 사람들에게 자신감을 줄 수 있는 문제가 아닌가 한다. :-)


문제의 내용을 요약하면,

마술사가 1~16까지의 수가 적힌 카드를 갖고 4X4 로 무작위(사실 마술사가 트릭을 쓴다는 내용이다. 실제 무작위가 아님)로 배열한뒤 지원자가 선택한 카드가 무엇인지 맞추는 문제이다.


Rule 과 함께 예제를 들면,

1. 마술사가 1~16 까지 숫자를 4X4로 놓는다.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16


2. 지원자가 원하는 숫자가 어느 열에 있는지 물어본다.

예를 들어 지원자는 7을 생각했고 마술사에게 "2"열이라고 답해준다.


3. 마술사가 카드를 썪어 다시 한번 놓게된다.

1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16


4. 그럼 지원자는 "3" 열이라고 마술사에게 얘길 하고, 마술사는 지원자가 생각한 숫자 7을 말해주면 된다.


이는 마술사가 1번째와 2번째 카드 배열시 "Trick"을 써 지원자의 생각한 숫자를 맞추는 것이다.

(이런걸 속을 수 있나.. 지원자도 말하면서 눈치를 챌듯..)


이렇게 정상적인 case 만 있는 것은 아니다. 지원자가 실제 위의 예제에서 마술사가 2번째로 카드를 배열했을 때

3열이라고 답해야 하지만, 2열이라고 답하게 되었다면 "Volunteer cheated!" 출력하고,

마술사가 2번째 배열에서 5,6,7,8 을 다른 열로 분리를 해야 하는데, 하나이상 같은 열에 놓게 되어 맞출수 없는 경우에는

"Bad magician!" 이라고 출력하면 이 문제는 완전히 풀수 있게 된다.


문제 link 를 가면, Sample case 가 잘 나와있다. 


일단 Google Codejam 은 input data file을 제공한다. 이 파일을 받아서 code의 input으로 사용하면된다.

input 파일의 한라인씩 읽는다고 했을때,

첫번째 배열에서 지원자가 말한 열(5, 6, 7, 8) 을 저장해놓고 다음 배열에서 말한 (9, 10, 7, 12)를 단순 비교한다


만약

1. 같은 숫자가 하나 라면, 그 값을 return 한다.

2. 같은 숫자가 2 이상 4 이하라면 "Bad magician!" 을 return 한다.

3. 같은 숫자가 하나도 없으면 "Volunteer cheated!" 를 return 한다.


끝.


파일을 첨부하는데 문제가 있어, code를 붙여 넣는다.

def checkCards(first, second):
    sameCount = 0
    sameNum = ""

    for num in range(0, len(first)):
        for snum in range(0, len(second)):
            if first[num] == second[snum]:
                sameCount = sameCount + 1
                sameNum = first[num]

    if sameCount == 1:
        return sameNum
    elif sameCount > 1 and sameCount <= 4:
        return "Bad magician!"
    elif sameCount == 0:
        return "Volunteer cheated!"

    # never reach hear with data from codejam
    return "error"

if __name__ == "__main__":
    testcases = input()
    LineOfCardsFirst = []
    LineOfCardsSeconds = []
    for caseNr in xrange(1, testcases + 1):
        for num in range(0,2):
            selectRow = raw_input()
            #print "selected Row : ", selectRow
            for row in xrange(0, 4):
                if row == int(selectRow) - 1:
                    if (num == 0):
                        LineOfCardsFirst = map(int, raw_input().split())
                        #print "LineOfCards : ", LineOfCardsFirst
                    else:
                        LineOfCardsSeconds = map(int, raw_input().split())
                        #print "LineOfCards : ", LineOfCardsSeconds
                else:
                    raw_input()
 

      print("Case #%i: %s" % (caseNr, checkCards(LineOfCardsFirst, LineOfCardsSeconds)))


'Algorithm' 카테고리의 다른 글

[GitHub] Algorithm 문제 풀기(TopCoder, Hackerrank)  (1) 2015.11.27
[Google Codejam] Qualification Round 2014-Cookie Clicker Alpha  (0) 2014.05.07
[Algorithm] Python 배우기  (0) 2013.10.09
[Alogithm Practice] CodeChef 소개  (0) 2013.05.15

Git add -p 로 수정사항 분리하기


git commit 은 하나의 수정 사항을 반영 하는 것이 Kernel 과 같은 대형 project 에 merge 될 확률이 높다. 이는 kernel에 Documentation/SumittingPatches 의 3번(Separate your changes.)의 내용을 보면 알 수 있다.


하지만 수정을 하다 보면, 하나의 commit 내부에 두 개 이상의 bug 수정이 있을 수 있다. 이런 경우 여러 개의 Commit 으로 분리하는 방법을 작성해 본다.


최근 Kernel patch 를 만드는 과정에서 Maintainer 가 두 개로 분리해달라는 요청이 있었고, 이를 위해 고민하다 검색으로 찾아낸 방법이다.


이미 하나의 commit 으로 내 local branch 에 있다. 이 commit 을 두 개로 분리했던 과정을 살펴본다.


1. 내 commit 이전으로 돌아간다.

  - 이 때, 분리하려는 commit 이 최상위에 있어야 한다. 만약 최상위가 아니라면 http://woodz.tistory.com/75 여기를 참고하시면 된다.

$ git reset HEAD^

이렇게 하면, 최상위에서 바로 전의 commit 으로 reset 이 되고 내 수정 사항은 un-stage 된다.


현재 상황은, 아래와 같다. 아래서 위쪽 code block 과 아래쪽을 분리하여 commit 할 것이다.

$ git diff

diff --git a/kernel/workqueue.c b/kernel/workqueue.c

index 0ee63af..0679854 100644

--- a/kernel/workqueue.c

+++ b/kernel/workqueue.c

@@ -4087,10 +4087,7 @@ static void wq_update_unbound_numa(struct workqueue_struct *wq, int cpu,

                if (cpumask_equal(cpumask, pwq->pool->attrs->cpumask))

                        goto out_unlock;

        } else {

-               if (pwq == wq->dfl_pwq)

-                       goto out_unlock;

-               else

-                       goto use_dfl_pwq;

+               goto use_dfl_pwq;

        }


        mutex_unlock(&wq->mutex);

@@ -4100,7 +4097,8 @@ static void wq_update_unbound_numa(struct workqueue_struct *wq, int cpu,

        if (!pwq) {

                pr_warning("workqueue: allocation failed while updating NUMA affinity of \"%s\"\n",

                           wq->name);

-               goto out_unlock;

+               mutex_lock(&wq->mutex);

+               goto use_dfl_pwq;

        }


        /*


이 상태에서 "git add -p" 를 입력하면, 

$ git add -p

diff --git a/kernel/workqueue.c b/kernel/workqueue.c

index 0ee63af..0679854 100644

--- a/kernel/workqueue.c

+++ b/kernel/workqueue.c

@@ -4087,10 +4087,7 @@ static void wq_update_unbound_numa(struct workqueue_struct *wq, int cpu,

                if (cpumask_equal(cpumask, pwq->pool->attrs->cpumask))

                        goto out_unlock;

        } else {

-               if (pwq == wq->dfl_pwq)

-                       goto out_unlock;

-               else

-                       goto use_dfl_pwq;

+               goto use_dfl_pwq;

        }


        mutex_unlock(&wq->mutex);

Stage this hunk [y,n,q,a,d,/,j,J,g,e,?]? n


알아서 한 블럭씩 분리하여 더 나눌 것인지, 아니면 이부분을 하나의 Commit 으로 만들 것인지 물어본다.

나는 아래의 block 을 먼저 commit 하고 이 부분을 나중에 commit 하려고 한다. 그래서 "n" 을 입력했다.

n 을 입력하면, 

@@ -4100,7 +4097,8 @@ static void wq_update_unbound_numa(struct workqueue_struct *wq, int cpu,

        if (!pwq) {

                pr_warning("workqueue: allocation failed while updating NUMA affinity of \"%s\"\n",

                           wq->name);

-               goto out_unlock;

+               mutex_lock(&wq->mutex);

+               goto use_dfl_pwq;

        }


        /*

Stage this hunk [y,n,q,a,d,/,K,g,e,?]? y

다음 block 의 code를 할 것인지 연속적으로 물어본다. 여기서 "y" 를 입력하면 이 부분만 git add 가 된다.


확인을 해보면,

$ git status

# Not currently on any branch.

# Changes to be committed:

#   (use "git reset HEAD <file>..." to unstage)

#

#       modified:   kernel/workqueue.c

#

# Changes not staged for commit:

#   (use "git add <file>..." to update what will be committed)

#   (use "git checkout -- <file>..." to discard changes in working directory)

#

#       modified:   kernel/workqueue.c

#

위에서 처럼 일부는 add 가 되고 나머지는 un-stage 상태가 된다. 


그 다음에

$ git commit -s

제목 쓰고.. 내용 쓰고.. 저장 하고 나온다.


또 그 다음에 나머지 수정 사항을 기록 한다.

$ git add

$ git commit -s

제목 쓰고.. 내용 쓰고.. 저장하고 나온다.


그렇게 하면 의도했던 대로 하나였던 commit 이 두 개로 분리가 된다.


사실 이렇게 하지 않아도 되는데, 지저분하거나 혹은 새로 작성해야 하는 문제가 발생한다. 물론 위와 같은 예제는 간단해서 다시 작성해도 되긴 하지만, 이와 같은 방법을 사용하면 이미 잘 작성된 code 에 실수 등이 발생하지 않을 것이다.(code는 건들지도 않으니.. 물론 분리를 잘못하면 발생하는 문제는 있긴 하다. :-) )


이렇게 해서 patch 를 보내면 된다. 



'Development Tip' 카테고리의 다른 글

VIM 에서 spelling 확인하기  (0) 2016.07.08
Git: 특정 commit 으로 이동 후, amend 하기  (0) 2014.02.28
const char* vs. char const*  (0) 2014.02.19
Fish shell environment  (0) 2013.12.03
Kernel mailing list 활용 방법  (0) 2013.11.08

+ Recent posts

티스토리툴바