作者:Jing Ling
博客:HackFun

0x00 Miscellaneous

IRC

problem

EasyCTF has an IRC channel! Check out #easyctf2017 on freenode to claim a free flag, and stick around to get on-the-fly updates during the competition.

solution

了解一波IRC，熟悉一下操作命令，找到Cannot join channel (+r) - you need to be identified with services 的解决方法，成功加入到#easyctf2017的频道。

A-maze-ing

problem

Solve a maze! ‘j’ is left, ‘k’ is down, ‘l’ is right, and ‘i’ is up. You input directions in a string. An example: “jkliilillikjk”. Submit your input string as the flag. (Whoops! You don’t have a maze, do you? Sucks to be you.

solution

easyctf{jjjjjjjjjjjjjjjjjjj}
easyctf{kkkkkkkkkkkkkkkkkkk}

参考：一个迷宫从入口进去，沿着右手边的墙走，是否肯定能走到出口？

0x01 Programming

Hello, world!

problem

Use your favorite programming language to print Hello, world! to stdout! Use the programming interface to do this!

Programming Judge codes:

AC: accepted
WA: WRONG ANSWER (you're bad)
TLE: time limit exceeded (make your code faster)
RTE: runtime error
JE: judge error (contact an admin if you encounter this)
CE: compilation error

solution

print('Hello, world!')

Things Add Up

problem

For this problem you will utilise the programming interface, which you can access via the navigation bar at the top of your screen.

The input for your program will be given via STDIN - that’s cin, input(), and System.in for cxx, Python, and Java respectively. Output goes to STDOUT - cout, print, and System.out. Your program will be run on several sets of input, and if your output matches ours for each testcase, this problem will be marked solved.

We’ll start with a simple challenge. Each testcase has two lines of input. The first will contain an integer N. The second will contain a sequence of integers a_1, a_2, ..., a_N. You are to output the sum of that sequence - that is, a_1 + a_2 + ... + a_n. Good luck!

Input Constraints

0 < N < 100
-1000 < a_i < 1000

Sample Input

5
2 4 7 3 1

Sample Output

17

solution

n = input()
s = raw_input().split()
r = 0
for x in xrange(n):
    r += int(s[x])
print(r)

Fizz Buzz 1

problem

Write a program that takes an integer n as input.

Output the numbers 1 through n, in increasing order, one per line.

However, replace any line that is a multiple of 3 with Fizz and any that are a multiple of 5 with Buzz. Any line that is a multiple of 3 and 5 should be written as FizzBuzz.

The input will be the number of lines to write, n, followed by a linebreak.

Sample input:

17

Sample output:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17

solution

n = input()
for x in xrange(1, n + 1):
    if x % 3 == 0:
        if x % 5 == 0:
            print('FizzBuzz')
        else:
            print('Fizz')
    elif x % 5 == 0:
        print('Buzz')
    else:
        print(x)

Library

problem

Your librarian has a 2-row bookshelf that can contain N books in each row. She wants to know the number of ways that she can fill the bookshelf with red-colored books and blue-colored books such that no 2 red-colored books are adjacent to each other (horizontally or vertically).

Input: the integer, N (1<=N<=2^1024)

Output: the number of ways you can place red-colored books and blue-colored books onto a N-column bookshelf. Since this number might be really big, output it mod 10^9+7.

Example: Input: 2

Your valid bookshelf layouts are:

BB
BB

BB
BR

BR
BB

RB
BB

BB
RB

RB
BR

BR
RB

Therefore, Output: 7

solutin

画图或编程找出规律公式，然后就是数学推导，最后编程计算：

1
2
3
4
5
6
7
8
9

import numpy as np
n = input()
temp = np.array([[0, 1], [1, 2]])
matrix = np.array([[0, 1], [1, 2]])
init = np.array([[3], [7]])
for x in xrange(n - 2):
    temp = np.dot(temp, matrix)
result = np.dot(temp, init)
print(result[0][0] % (10 ** 9 + 7))

来自VictorZC表哥的矩阵快速幂解法：

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

n = input()
   p = n-2
   a0=0
   a1=1
   a2=1
   a3=2
   r0=1
   r1=0
   r2=0
   r3=1
   mod=10**9+7
   while p>0:
       if p%2==1:
           c0=a0*r0+a1*r2
           c1=a0*r1+a1*r3
           c2=a2*r0+a3*r2
           c3=a2*r1+a3*r3
           r0=c0%mod
           r1=c1%mod
           r2=c2%mod
           r3=c3%mod
       c0=a0*a0+a1*a2
       c1=a0*a1+a1*a3
       c2=a2*a0+a3*a2
       c3=a2*a1+a3*a3
       a0=c0%mod
       a1=c1%mod
       a2=c2%mod
       a3=c3%mod
       p=p//2
   if n==1:
       print 3
   else:
       print (r2*3+r3*7)%mod

Fzz Buzz 2

problem

Oh no! Two of my keys are broken! Please help me make the same Fzz Buzz program, sans that one letter and queston marks.
As a side note, use of eval() and exec() is also frowned upon and will be marked invalid.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Create aliases
f = getattr(globals()['__bu\x69lt\x69ns__'],'\x69nput')
p = getattr(globals()['__bu\x69lt\x69ns__'],'pr\x69nt')
# Get user input
n = f()
# Prints text for line k and calls itself with the next line
def go(k):
    a = ((k % 15 == 0) and p('F\x69zzBuzz'))
    a = ((k % 3 != 0 and k % 5 == 0) and p('Buzz'))
    a = ((k % 3 == 0 and k % 5 != 0) and p('F\x69zz'))
    a = ((k % 3 != 0 and k % 5 != 0) and p(k))
    a = ((k < n) and go(k + 1))
go(1)

Down a Notch

problem

I’ve spent too long in the high level, let’s take the level down a notch. Help me find the correct input to this function!
Your answer should be in the format a:b where a and b are integers. Do not wrap it with easyctf{}.
Hint: Compiled with x86-64 gcc 4.9.4

check(int, int):
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %edi, -36(%rbp)
        movl    %esi, -40(%rbp)
        movl    -36(%rbp), %eax
        xorl    -40(%rbp), %eax
        movl    %eax, -4(%rbp)
        movl    -4(%rbp), %eax
        addl    $98, %eax
        movl    %eax, -8(%rbp)
        movl    -8(%rbp), %eax
        notl    %eax
        movl    %eax, %edx
        movl    -40(%rbp), %eax
        addl    %edx, %eax
        movl    %eax, -12(%rbp)
        movl    -12(%rbp), %eax
        xorl    -36(%rbp), %eax
        movl    %eax, -16(%rbp)
        movl    -40(%rbp), %eax
        imull   -4(%rbp), %eax
        cltd
        idivl   -8(%rbp)
        movl    %eax, %edx
        movl    -36(%rbp), %eax
        leal    (%rdx,%rax), %ecx
        movl    -12(%rbp), %edx
        movl    -16(%rbp), %eax
        addl    %edx, %eax
        xorl    %ecx, %eax
        movl    %eax, -20(%rbp)
        cmpl    $-814, -20(%rbp)
        sete    %al
        popq    %rbp
        ret

solution

推荐文章：从汇编角度浅析C程序

简单的汇编代码理解:

push rbp
mov rbp, rsp
mov [rbp-36], edi
mov [rbp-40], esi
mov eax,[rbp-36]   ;eax = r36
xor [rbp-40], eax  ;r40 = r40 ^ eax
mov [rbp-4], eax   ;r4 = eax
mov eax, [rbp-4]   ;eax = r4
add eax, 98        ;eax = eax + 98
mov [rbp-8], eax   ;r8 = eax
mov eax, [rbp-8]   ;eax = r8
not eax            ;eax = ~ eax
mov edx, eax       ;edx = eax
mov eax,[rbp-40]   ;eax = r40 
add eax, edx       ;eax = eax + edx
mov [rbp-12], eax  ;r12 = eax
mov eax, [rbp-12]  ;eax = r12
mov eax, [rbp-36]  ;eax = r36
mov [rbp-16], eax  ;r16 = eax
mov eax, [rbp-40]  ;eax = r40
imul eax, [rbp-4]  ;eax = eax * r4
cltd
idiv [rbp-8]       ;eax = eax / r8 edx = eax % r8
mov edx, eax       ;edx = eax
mov eax, [rbp-36]  ;eax = r36
lea ecx, [rdx+rax] 
mov edx, [rbp-12]  ;edx =r12
mov eax, [rbp-16]  ;eax = r16
add eax, edx       ;eax = eax + edx
xorl ecx, eax      ;ecx = ecx ^ edx
movl eax, [rbp-20] ;eax = r20
cmpl -814, [rbp-20];r20 ?= -814
sete al
popq [rbp]
ret

a = input()
b = input()
c = a ^ b
d = 98 + c
e = ~d + b
f = e ^ a
g = a + b * c / d ^ e + f
g ?= -814

整理一下：

g = a + b * (a ^ b) / (98 + (a ^ b)) ^ (~(98 + a ^ b) + b) + (~(98 + a ^ b) + b) ^ a

二元一次方程求解，暴力跑一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def check(a, b):
    c = a ^ b
    d = 98 + c
    e = ~d + b
    f = e ^ a
    res = a + b * c / d ^ e + f
    if res == -814:
        return True
    else:
        return False
for a in range(1000):
    for b in range(1000):
        find = False
        if check(a, b):
            find = True
            print "%d:%d" % (a, b) # 14:975
            break
    if find:
        break

MWayward Space Junk

problem

I’m trying to destroy some space junk, but it won’t stop moving!

nc wayward.tcp.easyctf.com 8580

Pilot Key: 7554eb73dc155375b47b4a655a27332b

hint: Try figuring out the trajectory of the junk.

solution

writeup

Match Me

problem

When making pairings between two sets of objects based on their preferences (in this case people), there can be multiple stable solutions, stable meaning that no two elements would prefer to be matched with each other over their current matching. A side-effect of having multiple solutions is that there are solutions favor one group over the other.

We received two files, one listing men and the other women. Each line contains a name, followed by a series of numbers. Each number N corresponds to their preference to be matched with the Nth member of the opposite list, with 1 being the highest.

For example, the entry “Joe 4, 5, 3, 1, 2” means that Joe would most prefer the 4th entry on the opposite list, and least prefer the 2nd.

We have heard that there are some pairings that will be together in all possible stable matchings, please find them. However, because there are quite a bit of them, please submit your solution as the following:

MD5 hash of (male_1,female_1)(male_2,female_2)...(male_n,female_n), where the pairings are sorted alphabetically by male names. For example, (Bob,Susie)(Jim,Carol)(Tom,Emma) would be submitted as b0d75104ce4b3a7d892f745fd515fea4.

Here are the lists of preferences:male preferences, female preferences.

Hint: This is a fairly well-known graph problem. I would guess there is some sort of internet source on it.

solution

writeup

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

#https://www.youtube.com/watch?v=Qcv1IqHWAzg
import hashlib
def main(maleFile,femaleFile,reverse):
    #These -10000's and such are to pad the array,
    #so nth id represents nth index
    males = [[-10000]]
    maleIDNameMap = {}
    females = [[-10000]]
    femaleIDNameMap = {}
    loadData(males,maleIDNameMap,maleFile)
    loadData(females,femaleIDNameMap,femaleFile)
    #Format is that the man's index is there id, and inside is [x,y] where y is id of person they're paired with,
    # and x is his rank for that person, rank being 0-based
    manCurrentAssignments = [[1000000,-1000]]*len(males)
    unassignedWomenIDs = list(range(1,len(females)))
    while(len(unassignedWomenIDs) != 0):
        #use i, so I don't ahve to worry about modifying list while looping through it.
        i = len(unassignedWomenIDs) - 1
        while(i >= 0):
            womanID = unassignedWomenIDs[i]
            i-=1
            #pop so that I don't check same combo again later.
            nextPrefferedManID = females[womanID].pop(0)
            thisWomanPrefferenceRank = males[nextPrefferedManID].index(womanID)
            if(manCurrentAssignments[nextPrefferedManID][0] > thisWomanPrefferenceRank):
                # assign this woman to this man
                del unassignedWomenIDs[i+1]
                oldAssigneeID = manCurrentAssignments[nextPrefferedManID][1]
                if(oldAssigneeID==-1000):
                    #ezpz
                    manCurrentAssignments[nextPrefferedManID] = [thisWomanPrefferenceRank,womanID]
                else:
                    #gotta kick off old woman, and try everything in range 1... cur
                    #except I'm doing something clever and only keeping men she hasn't tried on listRef
                    #so program may just iterate a few more times. No recursive dealing with kicking off more
                    #and more women.
                    unassignedWomenIDs.append(oldAssigneeID)
                    manCurrentAssignments[nextPrefferedManID] = [thisWomanPrefferenceRank,womanID]
    output = []
    if(reverse):
        for i in range(1,len(males)):
            output.append([femaleIDNameMap[manCurrentAssignments[i][1]],maleIDNameMap[i]])
    else:
        for i in range(1,len(males)):
            output.append([maleIDNameMap[i],femaleIDNameMap[manCurrentAssignments[i][1]]])
    return output
def loadData(listRef,idRef,fname):
    lines = []
    with open(fname) as f:
        lines = f.readlines()
    i = 1
    for line in lines:
        elements = line.split(' ')
        idRef[i] = elements[0]
        tmp = []
        for k in range(1,len(elements)):
            tmp.append(int(elements[k][:-1]))
        listRef.append(tmp)
        i += 1
maleFirst   = main('male','female',False)
femaleFirst = main('female','male',True )
toMD5 = []
for i in maleFirst:
    for j in femaleFirst:
        if(i[0] == j[0]):
            if(i[1]==j[1]):
                toMD5.append(i)
# For MD5
md5String = ""
for i in toMD5:
    md5String += "(%s,%s)" %(i[0], i[1])
print(md5String)
md5 = hashlib.md5(md5String.encode()).hexdigest()
print(md5)