[pwnable.kr] coin1 풀이

 

 

Analysis

---

 

N과 C값이 주어진다.

 

N은 동전의 갯수이다.

C는 선택할 수 있는 횟수이다.

 

N개의 동전 중에서 한 개가 가짜 동전이다.

클라이언트는 0~N-1 개의 인덱스 중에서 입력을 하면 그 인덱스에 해당하는 동전 무게의 합을 알려준다.

 

N값이 너무 커서 사람이 하기에는 무리가 있다.

C 횟수도 그렇고 딱 봐도 이진탐색을 써달라고 울부짖는게 보인다.

 

혹시 몰라 -1 도 넣어보고 했지만 에러는 발생하지 않는다.

 

이건 알고리즘 문제인듯;

 

Solution

---

이진탐색 코드를 작성하여 수행 중에, 시간 초과가 난다.

 

서버가 느리면 여기서 하라고 한다.

아니 ssh로 어디를 접속해야하나 싶었는데

그냥 이전 ssh 아무데나 들어가서 localhost로 하면 된다.

 

로컬호스트로 하니까 엄청 빨리 나온다..

 

from pwn import *

def has_fake(fr, to):

    l = list(range(fr, to))
    payload = ' '.join(map(str, l))
    print('[client]:', payload)
    p.sendline(payload.encode())

    server = int(p.recvline().decode())
    print('[server]:', server)
    if server == len(l) * 10:
        return False
    else:
        return True

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

p.recvuntil(b'3 sec... -\n')
p.recvline()


for find in range(100):
    prob = p.recvline().split()

    ns = {}

    for i in prob:
        key, value = i.split(b'=')
        ns[key] = int(value)

    N = ns[b'N']
    C = ns[b'C']

    print('N:',N)
    print('C:',C)

    cnt = C
    top = N
    bottom = 0
    while True:
        mid = (top + bottom) // 2

        if bottom == mid or mid == top:
            ans = mid
            break

        print('t:', top, 'm:', mid, 'b:', bottom, 'c:', cnt)
        cnt -= 1

        if has_fake(bottom, mid):
            top = mid
        else:
            bottom = mid 
    while cnt >= 0:
        print('t:', top, 'm:', mid, 'b:', bottom, 'c:', cnt)
        cnt -= 1 
        print('[client]:', mid)
        p.sendline(str(mid).encode())
        print('[server]:',p.recvline().decode())

p.interactive()

 

마지막에 C를 다 소모해야 정답인정되는 줄 몰랐지만, 덧붙여가며 풂

예외처리를 has_fake에서 하면 되지 않는가? -> 바로 하려고 했는데 에러나서 따로 처리하였다.