[HSCTF 9] travelling-salesman

1. 개요

정렬 문제

 

TPS 알고리즘인줄알고 시간을 많이 소비했는데 잘못 짚었습니다.

 

2. 분석

1) 문제

uclidean traveling salesman over single dimension? nc travelling-salesman.hsctf.com 1337

Task
You are handing out newspapers to classrooms in HSN. There is a list of classrooms given to you that you have to visit. These classrooms are conveniently located in a single hallway, which has 100 classrooms numbered 1 .. 100 in order. Since you are lazy, you want to minimize your walking distance. Given that you must start and end at classroom 1, output the order of classes to visit in order to minimize your walking distance. If there are multiple solutions, output any.

Interaction Details: There will be 3 test cases.
For each test case, you will be given an array of integers representing the classrooms to visit. You will then be prompted to enter a list of space separated integers representing the order in which the classrooms will be visited.

Sample Interaction:
[59, 68, 24, 83]
order: 59 83 68 24

[27, 29, 43, 50, 78, 21, 70, 89, 93, 85] 
order: 27 29 43 50 78 21 70 89 93 85 Distance too large

 

2) 외판원 순회?

일단 알고있는 외판원 순회 알고리즘과 차이점은 a -> b, b -> a 비용이 같다.

 

그리고 외판원 순회는 최대 입력이 16일때만 가능합니다. 문제에서 입력의 크기가 주어지지 않았지만, 최대 입력은 50입니다.

 

즉, 일반적인 외판원 순회 알고리즘이 아닙니다.

 

3) 정렬

a -> b, b -> a 비용이 같기 때문에 내림차순 또는 오름차순으로 정렬되어 탐색할때 가장 비용이 작습니다.

 

내림차순, 오름차순 비용은 모두 같은데

 

문제에서는 오름차순으로 정렬하면, 틀리다고 나와서, 내가 잘못 안건가?

 

- 그리고 문제 다시보니 3개의 테스트 케이스 준다고 했지만, 5개였다.

 

3. exploit

1) 코드

from pwn import *
import re

# 문자열로 받은 도시를 리스트로 변환합니다.
def get_cities():
    message = p.recvuntil("]").decode("utf-8")
    m = re.sub("[^0-9]", " ", message)
    s = [int(c) for c in re.split("[ ]+", m) if c != '']
    return s

# 정렬
def tp(l):
    r = l[0:1] + sorted(l[1:], reverse=True)
    return " ".join([str(c) for c in r])

# 1. 연결
p = remote('travelling-salesman.hsctf.com', 1337)

# 2. 초기 인풋
message = p.recvuntil("disabled ==")
print('message', message)

# 3. 테스트 케이스 5번 반복
for _ in range(5):
    l = get_cities()
    print('cities', l)
    order = tp(l)
    print('order', order)
    p.sendline(order)

result = p.recvall()
print('result', result)

 

2) 확인