Daeseok's Blog

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

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

[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()
 

CodeChef

Alogrithm 연습을 위한 site 를 소개하려 한다.

어쩌다 Google Codejam 을 알게 되었는데, 문제를 몇개 열어 풀어보려고 시도를 했지만 어떻게 접근을 해야 하는지 조차 생각해내지 못해 좌절(?)을 맞게 되었다. 그래서 여기저기 Community 도 돌아다녀보며 사람들이 어떻게 이런 Competition을 준비하는지에 대한 내용을 보게 되었다. 그 중 TopCoder 라는 곳을 먼저 알게되었는데, 오래동안 준비해왔던 단체라 볼 수 있는 자료도 많고 java applet 을 통해 Web 환경에서  algorithm test 를 할 수 있도록 만들어 놓았다.(나중에 posting 하겠다.) 하지만 단점이라고 굳이 짚자면 지원되는 language 가 4개 밖엔 없었고(C++, java, C#, Visual basic) 내가 하고 싶어한 python은 아직 준비중이 었던 것이다. 또 하나는 algorithm 문제를 쉬운 것, 혹은 어려운 것만 모아 두지 않아 찾아보고 할만한 것(?)만 시도 해봐야 하는 것이다. 이 사이트도 나중에 도전을 해봐야 겠지만 지금은 조금 무리인 듯 해서 다른 site 를 찾던 중에 CodeChef를 찾은 것이다.

URL : http://ww2.codechef.com

이 사이트의 가장 큰 장점은 다양한 language 를 지원하는 것과 나이도별(easy, medium, hard, challenge, peer) 문제를 모아둔 것이다. 물론 Algorithm test 중 과정에서 실패한 항목에 대한 출력을 안해준다는 것이다. 그래서 내가 어떤 input 값에 대한 output 이 잘못되었는지 스스로 확인해봐야 하는 것이 문제이다.(TopCoder 는 이런 것들을 확인해준다)

하는 방법은 간단하다.

1. Site 에 접속하여 가입을 한다.

   - 가입 후 확인 메일이 오는데, 확인 메일에서 link를 따라가면 password 를 설정 할 수 있다.

   - 또한 facebook 계정과 연동이 되어 그냥 해도 될 듯 했지만 연동하지 않았다.

가입이 완료 되었다면,

2. Practice ==> Easy 문제를 보자

위 그림에서 박스로 되어 있는 부분으로 가서 "Easy" 클릭

3. 진입

이와 같이 문제와 Sucessful Submission 개수 및 정확도 등을 보여준다. 맨 위에 있는 문제는 "Easy" 중에서도 어려운 문제인 듯 하다. 푼사람이 많지 않으니.. ㅎㅎ

그래서 맨 아래에서 부터 풀어 올라와면 좋을 듯!!!

4. 한문제를 풀어보자.(미리 풀어봤으니)

Holes in the Text 라는 주제의 문제를 풀어보자(아래에서 7번째에 있다. )

물론 영어라는 압박(?) 있지만 걱정말자 Example 만 잘 보면 그냥 문제의 의도를 알수도 있다. 아니면 이 문제의 답변글을 살펴 보셔도.. 

암튼 문제를 간단히 요약하면 주어진 문자열에 영문자(대문자만)에 있는 구멍(?)의 개수가 몇개인지 찾는 문제이다. 

(예를 들어 "A" 는 구멍이 1개, "B" 는 2개, C, E, F 이런 녀석은 구멍이 없는 문자다)

Example로 나온 "CODECHEF" 는 구멍이 "O"와 "D" 에 하나씩 2개가 있는 것이다. 

사실 이런 문제는 문자가 구멍이 몇개 있을 것이라는 규칙 같은 것이 없다.(Table 을 만들어 줘야 할 것이다.)

5. 내 개인 컴퓨터로 문제를 열심히 풀어 Example에 나온 input 과 output 에 맞도록 작성한다.

(Python으로)

alphaHoles에 A~Z 순서로 hole의 개수를 미리 적어 놓는다.

그리고 input으로 들어오는 문자열에서 문자를 하나씩 꺼내 'A' ascii 값을 빼준다.(65) 그렇게 되면 정확히 alphaholes table에 각 문자에 맞는 hole 개수 값을 갖고 올 수 있다. 그리고 다 더 해서 출력해주면 끝~

6. code를 만들었으니 확인해봐야 겠다.

문제 아래를 보면, "SUBMIT" 이라는 버튼이 있다. 클릭하자

(SUBMIT 버튼 위에 보면 지원되는 language 와 Time limit 같은 것은 확인하자.)

SUBMIT 을 click 하면,

위에서 처럼 창이 뜬다 여기에 code를 넣고 맨아래 Submit 을 클릭하면 되는데 그전에 자신이 사용할 language를 선택해야 한다. python을 선택하고 code를 넣겠다.

위에 처럼 code를 붙여 놓고 맨아래의 submit button을 클릭하면 된다. 그럼 progressbar 가 나오고 정상적으로 완료되면 Accept 가 되는 것이다.(이미 submit을 한번 했으므로 이 화면은 제외하겠다.)

그리고 나중에 나의 Code를 다시 보려면,

문제 제목 옆에 보면 "MY SUBMISSIONS" 라는 버튼이 있다. 클릭하면 내가 했던 Submit 을 모두 볼수 있다(한번에 성공했다면 하나밖에 없겠지만 여러번 했던 경우에 모두 볼 수 있을 것이다.)

미리 code test를 local에서 하고 넣는 것이라 compile 오류는 없겠지만 대게 Time limitation에서 걸린다. 시간을 짧게 요하는데 빨리 끊내지 못하고 시간을 끌면 Fail 난다.

이런 식으로 하나씩 하면 된다. 물론 막히거나 어려운 점이 있을 것으로 예상된다. 그렇다면 다른 사람이 이미 성공한 소스를 참조를 해보자. 다른 사람 소스에 너무 의존하는 것보다 자신이 하는 것이 좋지만 너무 어렵다면 참조를 하는 것도 좋을 듯하다. 문제가 많으니 처음엔 참조하더라도 나중에는 그냥 쉽게 풀수 있지않을까 한다. 

내가 10개정도 풀었는데 Easy 문제는 10~20분정도면 충분히 풀수 있을 것으로 본다. 하나씩 풀고 공유할 알고리즘이 있다면 써보도록 하겠다.