Harmony Analysis (Codeforces 610C)
Tags: Others, constructive algorithms

The semester is already ending, so Danil made an effort and decided to visit a lesson on harmony analysis to know how does the professor look like, at least. Danil was very bored on this lesson until the teacher gave the group a simple task: find 4 vectors in 4-dimensional space, such that every coordinate of every vector is 1 or  - 1 and any two vectors are orthogonal. Just as a reminder, two vectors in n-dimensional space are considered to be orthogonal if and only if their scalar product is equal to zero, that is: .Danil quickly managed to come up with the solution for this problem and the teacher noticed that the problem can be solved in a more general case for 2k vectors in 2k-dimensinoal space. When Danil came home, he quickly came up with the solution for this problem. Can you cope with it?

Input: The only line of the input contains a single integer k (0 ≤ k ≤ 9).

Output: Print 2k lines consisting of 2k characters each. The j-th character of the i-th line must be equal to ' * ' if the j-th coordinate of the i-th vector is equal to  - 1, and must be equal to ' + ' if it's equal to  + 1. It's guaranteed that the answer always exists.If there are many correct answers, print any.

Note: Consider all scalar products in example:  Vectors 1 and 2: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( + 1) + ( - 1)·( - 1) = 0  Vectors 1 and 3: ( + 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) + ( - 1)·( + 1) = 0  Vectors 1 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( - 1) + ( - 1)·( + 1) = 0  Vectors 2 and 3: ( + 1)·( + 1) + ( - 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) = 0  Vectors 2 and 4: ( + 1)·( + 1) + ( - 1)·( - 1) + ( + 1)·( - 1) + ( - 1)·( + 1) = 0  Vectors 3 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( + 1)·( - 1) + ( + 1)·( + 1) = 0 

Sample Inputs:
2

Sample Outputs:
++**
+*+*
++++
+**+

Solution (Python):
import sys
input = sys.stdin.readline

def neg(a):
    b = ''
    for i in range(len(a)):
        if a[i] == '+':
            b += '*'
        else:
            b += '+'
    return b
n = int(input())
a = '+'
e = [a]
for i in range(n):
    for j in range(2 ** i):
        b = e[j]
        e[j] += b
        e.append(b + neg(b))
for i in range(len(e)):
    print(e[i])

Solution (Python):
import sys

def check(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            diff = 0
            for k in range(n):
                if arr[i][k] == arr[j][k]:
                    diff += 1
                else:
                    diff -= 1
            if diff:
                return (arr[i], arr[j])
    return False

def inv(arr):
    return [not x for x in arr]

def gen(n):
    if n == 1:
        return [[True]]
    curr = gen(n // 2)
    ans = []
    ans.extend((x + x for x in curr))
    ans.extend((x + inv(x) for x in curr))
    return ans
k = int(input())
ans = gen(2 ** k)
for x in ans:
    sys.stdout.write(''.join(['+' if el else '*' for el in x]))
    sys.stdout.write('\n')

Solution (Python):
def anti(s):
    return ''.join(['+' if s[i] == '*' else '*' for i in range(len(s))])
k = int(input())
result = [[] for i in range(k + 2)]
result[0] = ['+']
for i in range(1, k + 1):
    for e in result[i - 1]:
        result[i] += [e + e]
        result[i] += [e + anti(e)]
print('\n'.join(result[k]))