pwnable Toddler`s Bottle - coin1

문제파악

이번 문제는 진짜 코인 보다 무게가 1 적은 가짜 코인을 60초안에 100번 찾아내라는 문제이다. 처음 헷갈렸던 것은 케이스가 하나 주어지고 해당 케이스에서 100개의 가짜 코인을 정해진 횟수안에 찾으라는 줄 알고 어떤 알고리즘으로 풀 수 있는지 고민을 엄청 했다. 고민 중 불가능하다고 생각했고 검색해 본 결과 100개의 케이스가 주어지고 각 케이스마다 1개의 가짜 코인을 찾는 문제라는 것을 알 수 있었다.

이분탐색

60초라는 시간 제한이 있기 때문에 코드를 짜야한다. 그리고 확인할 수 있는 횟수가 제한되고 그 횟수를 잘 살펴보면 logN보다는 크게 나오는 것을 볼 수 있다. 따라서 이분탐색법으로 시도를 했다. nc로 접근을 하기 때문에 간단하게 파이썬으로 소켓 통신 프로그램을 짰다. 보통 pwntools를 많이들 사용하는 것으로 보이는데 pwntools를 활용 못하는 환경도 있을 것이고 추가 설치를 별로 좋아하지 않기에 기본 라이브러리들로 구성했다. 그리고 네트워크가 느려서 시간초과가 발생하여 pwnable.kr 서버에서 프로그램을 실행했다.

import socket
import time
import re

HOST = '127.0.0.1'
PORT = 9007

csock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

csock.connect((HOST, PORT))

data = csock.recv(2048).decode()
print(data)
time.sleep(3)

for i in range(0, 100):
  data = csock.recv(1024).decode()
  print(i, data)
  N = int(re.split(r"[\D]", data)[2])

  s = 0
  e = N

  while s <= e:
    m = int((s+e)/2)
    msg = ""
    for j in range(s, m+1):
      msg += str(j)+" "
    msg += "\n"
    csock.sendall(msg.encode())

    data = csock.recv(100).decode()
    if 'Correct' in data:
      break
    data = int(data)
    
    if not (data % 10) == 0:
      e = m
    else:
      s = m+1
data = csock.recv(1024).decode()
print(data)