[pwnable.kr] coin1

pwnable 문제라기 보다는 misc, 프로그래밍 문제에 가깝다.
N개의 코인 중 무게가 다른 코인 하나를 찾으라는데, 기회를 C번 준다.

근데 몇번 해보니까 2^C 보다 작은 N 값을 주길래 그냥 이진 탐색 코드를 짜면 될 것 같다는 생각이 들었다.

무게가 다르면 10으로 나누어떨어지지 않기에 그를 이용해서 가짜 코인이 들어있을 집합을 좁혀 나가면서 index를 찾아내고, 이 알고리즘을 100번 돌리면 답이 나온다.

from pwn import *

p = remote('0', 9007)

p.recvuntil(b"sec... -")
p.recvline()
p.recvline()

for i in range (100):
    line = p.recvline().decode().strip()
    N, C = map(int, re.findall(r'\d+', line))

    lo, hi = 0, N-1

    for _ in range(C):
        mid = (lo + hi) // 2

        idxs = list(range(lo, mid+1))
        query = " ".join(map(str, idxs))
        p.sendline(query)

        weight = int(p.recvline().strip())
        if weight == len(idxs) * 10:
            lo = mid + 1
        else:
            hi = mid

    p.sendline(str(lo))

    print(p.recvline().decode().strip())
print(p.recvline().decode().strip())
print(p.recvline().decode().strip())

b1naRy_S34rch1Ng_1s_3asy_p3asy

flag도 대놓고 이진 탐색이란다