Mathematical Problem (Codeforces 1916D)
Tags: Math, geometry

The mathematicians of the 31st lyceum were given the following task:You are given an odd number $$$n$$$, and you need to find $$$n$$$ different numbers that are squares of integers. But it's not that simple. Each number should have a length of $$$n$$$ (and should not have leading zeros), and the multiset of digits of all the numbers should be the same. For example, for $$$\mathtt{234}$$$ and $$$\mathtt{432}$$$, and $$$\mathtt{11223}$$$ and $$$\mathtt{32211}$$$, the multisets of digits are the same, but for $$$\mathtt{123}$$$ and $$$\mathtt{112233}$$$, they are not.The mathematicians couldn't solve this problem. Can you?

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.The following $$$t$$$ lines contain one odd integer $$$n$$$ ($$$1 \leq n \leq 99$$$) — the number of numbers to be found and their length.It is guaranteed that the solution exists within the given constraints.It is guaranteed that the sum of $$$n^2$$$ does not exceed $$$10^5$$$.The numbers can be output in any order.

Output: For each test case, you need to output $$$n$$$ numbers of length $$$n$$$ — the answer to the problem.If there are several answers, print any of them.

Note: Below are the squares of the numbers that are the answers for the second test case:$$$\mathtt{169}$$$ = $$$\mathtt{13}^2$$$$$$\mathtt{196}$$$ = $$$\mathtt{14}^2$$$$$$\mathtt{961}$$$ = $$$\mathtt{31}^2$$$Below are the squares of the numbers that are the answers for the third test case:$$$\mathtt{16384}$$$ = $$$\mathtt{128}^2$$$$$$\mathtt{31684}$$$ = $$$\mathtt{178}^2$$$$$$\mathtt{36481}$$$ = $$$\mathtt{191}^2$$$$$$\mathtt{38416}$$$ = $$$\mathtt{196}^2$$$$$$\mathtt{43681}$$$ = $$$\mathtt{209}^2$$$

Sample Inputs:
3
1
3
5

Sample Outputs:
1
169
196
961
16384
31684
36481
38416
43681

Solution (Python):
MOD = 1000000007
number_squares = []

def generate_number_squares():
    temp = ['1']
    number_squares.append(temp)
    hue = ['169', '961', '196']
    number_squares.append(hue)
    for i in range(5, 100, 2):
        index = i // 2
        new_numbers = []
        for j in range(len(number_squares[index - 1])):
            partial_num = number_squares[index - 1][j]
            partial_num += '00'
            new_numbers.append(partial_num)
        num = ''
        for j in range(i):
            if j == 0:
                num += '1'
            elif j == i // 2:
                num += '6'
            elif j == i - 1:
                num += '9'
            else:
                num += '0'
        new_numbers.append(num)
        num = ''
        for j in range(i):
            if j == 0:
                num += '9'
            elif j == i // 2:
                num += '6'
            elif j == i - 1:
                num += '1'
            else:
                num += '0'
        new_numbers.append(num)
        number_squares.append(new_numbers)

def display_numbers(n):
    for i in range(len(number_squares[n // 2])):
        print(number_squares[n // 2][i])
if __name__ == '__main__':
    test_cases = int(input())
    generate_number_squares()
    while test_cases > 0:
        number = int(input())
        display_numbers(number)
        test_cases -= 1

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
ans = [['1'], ['169', '196', '961']]
for i in range(5, 100, 2):
    next_ans = []
    for num in ans[-1]:
        next_ans.append(num + '00')
    next_ans.append('1' + '0' * ((i - 3) // 2) + '6' + '0' * ((i - 3) // 2) + '9')
    next_ans.append('9' + '0' * ((i - 3) // 2) + '6' + '0' * ((i - 3) // 2) + '1')
    ans.append(next_ans)
for test in range(int(input())):
    n = int(input())
    curr_ans = ans[(n - 1) // 2]
    for num in curr_ans:
        print(num)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    if n == 1:
        print(1)
        continue
    n //= 2
    for i in range(n):
        print('1' + '0' * i + '6' + '0' * i + '9' + '0' * 2 * (n - 1 - i))
        print('9' + '0' * i + '6' + '0' * i + '1' + '0' * 2 * (n - 1 - i))
    print('196' + '0' * 2 * (n - 1))