coin1

설명

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

Running at : nc [pwnable.kr](http://pwnable.kr/) 9007

시작하면 하는 방법이 나온다. 설명을 해석해보면

금화를 주었다. 동전 중 위조품이 하나 있다. 
위조품은 실제 동전과 똑같다. 
그러나, 위조품은 실제 동전과 무게가 다르다. 
실제 동전은 무게가 10이다. 가짜 동전은 무게가 9이다. 
저울을 이용해서 가짜 동전을 찾는데 도움이 될 것이다.
만약 가짜 동전을 100전 찾으면, 너에게 상을 줄 것이다.
참고로, 60초 주어진다.

게임 룰
1. 동전의 개수 (N), 기회 (C)가 주어진다.
2. 계량할 동전의 인덱스 번호 세트를 지정해라.
3. 무게 정보를 줄 것이다.
4. 기회(C) 만큼 반복, 그리고 답을 입력해라.

풀이

실제 주어진 숫자와 기회를 보면, 계속 랜덤으로 바뀌고 N은 크고, C는 작다...

그러므로 빠르고 효율적으로 풀어야한다.

여기서 이진탐색 알고리즘을 쓰면 가장 빠르게 구할 수 있을 것같다.

from pwn import *

r = remote('pwnable.kr', 9007)

print(r.recvuntil('- Ready? starting in 3 sec... -\n\t\n'))
sleep(3)

for i in range(100):
    data = r.recvuntil('\n', drop=True)
    n, c = data.split(b' ')
    N = int(n.split(b'=')[1])
    C = int(c.split(b'=')[1])

    log.info(f'N : {N}')
    log.info(f'C : {C}')

    n_first = 0

    for j in range(C):
        # left
        data = ' '.join(str(i) for i in range(n_first, (n_first + N) // 2))
        log.info(f'send : {data}')
        r.sendline(data)
        recv_data = int(r.recvuntil('\n', drop=True))

        # 찾는 곳임
        if recv_data % 10:
            N = (n_first + N) // 2
        # 아닐 떄
        else:
            n_first = (n_first + N) // 2

    r.sendline(str(n_first))
    log.success(r.recvline())

r.interactive()

총 개수를 반으로 나눠 확인하고 또 반으로 나눠 좁혀가면 금방 구할 수 있다.

보면 이진탐색이 잘 돌아가서 답을 구한다.

그러나 시간이 60초만 주어져 그 안에 다 해결이 안된다. 그러므로 직접 서버에 접근해 로컬에서 돌리면 더 빠르게 될 것이다.

Flag

b1NaRy_S34rch1nG_1s_3asy_p3asy