StarCTF-PPC-Part

这次由六星战队负责出题的*ctf质量也是挺好的,虽然和BCTF时间上,有些冲突。但是由于太渣,早就放弃了BCTF,最后很遗憾Web一题也没做出来,只做了道PPC的题目magic_num,所以稍微写点吧

题目要求

随意给出n(1<=n<=14)个num(0<=num<=1024),然后可以通过? start_num end_num来获得在[start_num,end_num]中有几个num,在不超过99次询问的情况下,找到所有num,而且num可能有几个是相同的

算法实现

先定义函数findOne()使用二分法查询n=1时的num,然后通过递归的方式查询n>1时的所有num,倘若查询start_unm-start_num=1时,获得的结果就是start_num的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from pwn import *                                   

r = remote("47.89.18.224", 10011)

def findOne(start = 0, end = 1024):
end = (start+end)/2
temp_len = 0
result = 0
while(True) :
r.sendline("? "+str(start)+' '+str(end))
print "send:"+"? "+str(start)+' '+str(end)
p = r.recvline().strip('\n')
print "recv:"+p

if p == '1':
if end == start+1:
result = start
break
else:
end = (start+end)/2
elif p == '0':
if end == start+1:
result = end
break
else:
temp_len = end - start
start = end
end = end + temp_len/2
return result

def findSectionValue(start = 0, end = 1024, n = 0, results = []):
end = (start+end)/2
temp_len = 0;
r.sendline("? "+str(start)+' '+str(end))
print "send:"+"? "+str(start)+' '+str(end)
p = r.recvline().strip('\n')
print "recv:"+p
num = int(p)

if end == start+1:
if num >= 1:
for i in range(num):
results.append(start)
elif num == 0:
for i in range(n-num):
results.append(end)
else:

if num > 1 and int(n-num) > 1:
findSectionValue(start, end, num, results)
temp_len = end - start
findSectionValue(end, end + temp_len, n-num, results)
elif num > 1 and int(n-num) == 1:
findSectionValue(start, end, num, results)
temp_len = end - start
results.append(findOne(end, end + temp_len))
elif num == 1 and int(n-num) > 1:
results.append(findOne(start, end))
temp_len = end - start
findSectionValue(end, end + temp_len, n-num, results)
elif num == 1 and int(n-num) == 1:
results.append(findOne(start, end))
temp_len = end - start
results.append(findOne(end, end + temp_len))
elif num == 0 and int(n-num) > 1:
temp_len = end - start
findSectionValue(end, end + temp_len, n-num, results)
elif num == 0 and int(n-num) == 1:
temp_len = end - start
results.append(findOne(end, end + temp_len))
else:
findSectionValue(start, end, num, results)

return results


start = 0
end = 1024
n = 0
result = 0
r.recvuntil("n = 1\n")
result = findOne(start, end)
print "! " + str(result)
r.sendline("! " + str(result))

i = 0
while(i < 9):
p = r.recvlines(2)
n = int(p[-1][-2:])
print "n:" + str(n)

results = []
results = findSectionValue(start, end, n, results)
sendStr = "!"
for j in range(n):
sendStr = sendStr + " " + str(results[j])
print sendStr
r.sendline(sendStr)
i = i + 1
print r.recvlines(2)

一些坑

很简单的程序写了很长时间,一是太渣了,其次就是没有好好的顺一下,导致中间很多的查询是多余的,从而最后查询次数超过了99次。难受啊!