pwnable.kr Toddler's Bottle coin1 - 6 pt

pwnable.kr Toddler's Bottle coin1 - 6 pt

Mommy, I wanna play a game!
(if your network response time is too slow, try nc 0 9007 inside pwnable.kr server)

Running at : nc pwnable.kr 9007

$ nc pwnable.kr 9007

        ---------------------------------------------------
        -              Shall we play a game?              -
        ---------------------------------------------------

        You have given some gold coins in your hand
        however, there is one counterfeit coin among them
        counterfeit coin looks exactly same as real coin
        however, its weight is different from real one
        real coin weighs 10, counterfeit coin weighes 9
        help me to find the counterfeit coin with a scale
        if you find 100 counterfeit coins, you will get reward :)
        FYI, you have 60 seconds.

        - How to play -
        1. you get a number of coins (N) and number of chances (C)
        2. then you specify a set of index numbers of coins to be weighed
        3. you get the weight information
        4. 2~3 repeats C time, then you give the answer

        - Example -
        [Server] N=4 C=2        # find counterfeit among 4 coins with 2 trial
        [Client] 0 1            # weigh first and second coin
        [Server] 20                     # scale result : 20
        [Client] 3                      # weigh fourth coin
        [Server] 10                     # scale result : 10
        [Client] 2                      # counterfeit coin is third!
        [Server] Correct!

        - Ready? starting in 3 sec... -

N=297 C=9

황금 동전 중에 단 하나의 가짜 동전을 찾는 게임이다.
가짜 동전의 겉모습은 진짜와 완전히 같지만 무게가 다르다.
진짜 동전의 무게가 10, 가짜 동전은 9.
저울에 올려봐서 가짜를 찾아보자.
가짜 동전을 100번 찾는 것이 목표이다.
단, 60초의 시간 제한이 있다.

- 가이드 -
1. N 은 동전의 갯수, C 는 저울에 올려볼 수 있는 횟수를 뜻한다.
2. 저울에 올릴 동전들의 번호를 입력한다.
3. 무게가 출력된다.
4. 2~3 번을 C 번 반복하고 답을 입력한다.

- 예시 -
[서버] N=4 C=2       # 2번의 시도 안에 4개의 동전 중에 가짜를 찾아라
[클라] 0 1           # 첫 번째와 두 번째 동전을 저울에 올림
[서버] 20                          # 무게 결과 : 20
[클라] 3                           # 네 번째 동전을 저울에 올림
[서버] 10                          # 무게 결과 : 10
[클라] 2                           # 가짜 동전은 세 번째!
[서버] 정답!

시도 횟수와 시간이 제한되어 있기 때문에 효과적으로 빠르게 찾아내야 한다.

이번 문제는 이진 탐색(Binary Search)으로 코딩해서 푸는 것이 목표이다.

이진 탐색은 N 개 중에 하나를 찾는데 log₂N 번의 시도만에 찾아내는 알고리즘이다.

만약 4개 중에 하나 찾기는 log₂4 = 2. 즉, 2번 만에 찾을 수 있다.

저울에 무게를 달 때, 첫 번째가 0 부터 시작하므로 맨 마지막은 N-1 이라는 것을 주의하자.

from pwn import *

r = remote('pwnable.kr', 9007)
r.recvuntil('. -\n\t\n')

for i in range(100):
    a = re.search(r'N=(\d+) C=(\d+)', r.recvline())
    N = int(a.group(1))
    C = int(a.group(2))

    p = log.progress(str(i) + ' ' + a.group())

    low = 0
    high = N - 1
    for _ in range(C+1):
        mid = (low + high) // 2
        coin = ' '.join(map(str, range(low, mid+1)))
        p.status(coin)
        r.sendline(coin)

        try:
            weight = int(r.recvline())
        except ValueError:
            p.success(coin) # Correct!
            break

        if weight % 10:
            high = mid
        else:
            low = mid+1
r.interactive()

19.01.14까지만 볼 수 있음