Laboratory on Pluto (Codeforces 1775F)
Tags: Greedy, dp

As you know, Martian scientists are actively engaged in space research. One of the highest priorities is Pluto. In order to study this planet in more detail, it was decided to build a laboratory on Pluto.It is known that the lab will be built of $$$n$$$ square blocks of equal size. For convenience, we will assume that Pluto's surface is a plane divided by vertical and horizontal lines into unit squares. Each square is either occupied by a lab block or not, and only $$$n$$$ squares are occupied.Since each block is square, it has four walls. If a wall is adjacent to another block, it is considered inside, otherwise — outside.Pluto is famous for its extremely cold temperatures, so the outside walls of the lab must be insulated. One unit of insulation per exterior wall would be required. Thus, the greater the total length of the outside walls of the lab (i. e., its perimeter), the more insulation will be needed.Consider the lab layout in the figure below. It shows that the lab consists of $$$n = 33$$$ blocks, and all the blocks have a total of $$$24$$$ outside walls, i. e. $$$24$$$ units of insulation will be needed.You should build the lab optimally, i. e., minimize the amount of insulation. On the other hand, there may be many optimal options, so scientists may be interested in the number of ways to build the lab using the minimum amount of insulation, modulo a prime number $$$m$$$.Two ways are considered the same if they are the same when overlapping without turning. Thus, if a lab plan is rotated by $$$90^{\circ}$$$, such a new plan can be considered a separate way.To help scientists explore Pluto, you need to write a program that solves these difficult problems.  

Input: The first line contains two integers $$$t$$$ and $$$u$$$ ($$$1 \le t \le 2\cdot 10^5$$$, $$$1 \le u \le 2$$$) — the number of test cases and the test type. If $$$u=1$$$, you need to find any way to build the lab in an optimal way, and if $$$u=2$$$, you need to calculate the number of ways to do it.If $$$u=2$$$, then in the following line of input there is a prime integer $$$m$$$ ($$$10^8 \le m \le 10^9 + 9$$$), modulo which you need to calculate the number of ways.Each of the following $$$t$$$ lines of input contains a description of a test case consisting of one integer $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — the number of blocks the lab should consist of.It is guaranteed that if $$$u=1$$$, then the sum of $$$n$$$ on all test cases does not exceed $$$8\cdot10^5$$$.

Output: For each test case, output the answers in the format below, separating them with a newline. The output format depends on $$$u$$$ in the input data.If $$$u=1$$$, in the first line you need to print two integers $$$h$$$ and $$$w$$$ —the height and width of the area in which the lab should be built. Then, in each of the following $$$h$$$ lines, you must output a line $$$s_i$$$ consisting of $$$w$$$ characters "#" and ".". If the $$$j$$$-th character of the row $$$s_i$$$ is "#", then the corresponding square must contain a block of laboratory, otherwise, it is considered empty. Thus, we get a matrix of symbols. The condition must also be met that the first and last rows of the matrix, as well as the first and last columns, must have at least one character "#", otherwise we could output the same lab layout, but with smaller $$$h$$$ and $$$w$$$. If there are many options to build an optimal lab, you can print any of them.If $$$u=2$$$, you need to print two integers $$$p$$$ and $$$c$$$ — the number of outside walls in an optimal lab, and the remainder of the number of ways by prime modulo $$$m$$$.

Note: Consider the second example.If $$$n=1$$$, the only way to build a lab is to place a single block. In this case, the perimeter will be equal to four.When $$$n=2$$$, you must place two blocks side by side. This can be done either vertically or horizontally, so there are two ways. It is easy to see that the lab has six outside walls in this case.For $$$n=7$$$, all the $$$22$$$ optimal plans are shown in the picture below.  

Sample Inputs:
3 1
1
2
7

3 2
1000000007
1
2
7

Sample Outputs:
1 1
#
1 2
##
2 4
.###
####

4 1
6 2
12 22

Solution (Python):
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
from typing import *
from operator import add, xor, mul, ior, iand, itemgetter
import bisect
BUFSIZE = 4096
inf = float('inf')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(t, u) = MII()
if u == 1:
    for _ in range(t):
        n = II()
        m = int(n ** 0.5)
        while True:
            if m * m >= n:
                (c1, c2) = (m, m)
                break
            if m * (m + 1) >= n:
                (c1, c2) = (m, m + 1)
                break
            m += 1
        ans = [['#' for _ in range(c2)] for _ in range(c1)]
        for i in range(c1 * c2 - n):
            ans[0][i] = '.'
        print(c1, c2)
        for line in ans:
            print(''.join(line))
else:
    mod = II()
    tmp = 701
    dp = [[0] * tmp for _ in range(tmp)]
    dp[0][0] = 1
    for i in range(tmp):
        for j in range(tmp):
            dp[i][j] = (dp[i][j - 1] + dp[i - j][j]) % mod
    res = [dp[i][i] for i in range(tmp)]
    use2 = []
    for i in range(tmp):
        v = 0
        for j in range(i + 1):
            v += res[j] * res[i - j]
            v %= mod
        use2.append(v)
    use4 = []
    for i in range(tmp):
        v = 0
        for j in range(i + 1):
            v += use2[j] * use2[i - j]
            v %= mod
        use4.append(v)
    for _ in range(t):
        n = II()
        m = int(n ** 0.5)
        while True:
            if m * m >= n:
                (c1, c2) = (m, m)
                break
            if m * (m + 1) >= n:
                (c1, c2) = (m, m + 1)
                break
            m += 1
        ans = 0
        t = c1 + c2
        tmp = c1
        while tmp * (t - tmp) >= n:
            tmp -= 1
        k = tmp
        while True:
            if k * (t - k) >= n:
                ans += use4[k * (t - k) - n]
            elif k >= c2:
                break
            k += 1
        print((c1 + c2) * 2, ans % mod)

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())
from bisect import *
from heapq import *
from collections import *
from functools import *
from itertools import *
from time import *
from random import *
from math import log, gcd, sqrt, ceil
''
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def solve(testcase):
    (testcase, x) = MI()
    ''
    if x == 1:
        for _ in range(testcase):
            n = II()
            h = int(sqrt(n))
            w = ceil(n / h)
            grid = [['.' for _ in range(w)] for _ in range(h)]
            for i in range(h):
                for j in range(w):
                    if n:
                        grid[i][j] = '#'
                        n -= 1
                    else:
                        break
            print(h, w)
            for i in range(h):
                print(''.join(grid[i]))
    else:
        m = II()
        f = [0 for _ in range(700)]
        f[0] = 1
        for i in range(1, 700):
            for t in range(4):
                for j in range(i, 700):
                    f[j] += f[j - i]
                    f[j] %= m
        for _ in range(testcase):
            n = II()
            h = int(sqrt(n))
            w = ceil(n / h)
            while w - h > 1:
                w -= 1
                h += 1
            length = 2 * (h + w)
            res = 0
            while h * w >= n:
                res += f[h * w - n] * (1 + (h != w))
                res %= m
                h -= 1
                w += 1
            print(length, res)
for testcase in range(1):
    solve(testcase)

Solution (Python):
from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
    return int(input())

def st():
    return input()

def mj():
    return map(int, input().strip().split(' '))

def msj():
    return map(str, input().strip().split(' '))

def le():
    return list(map(int, input().split()))

def rc():
    return map(float, input().split())

def lebe():
    return list(map(int, input()))

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()

def joro(L):
    return ''.join(map(str, L))

def joron(L):
    return '\n'.join(map(str, L))

def decimalToBinary(n):
    return bin(n).replace('0b', '')

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def npr(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
    while start <= end:
        middle = (end + start) // 2
        if li[middle] >= num:
            answer = middle
            end = middle - 1
        else:
            start = middle + 1
    return answer

def upper_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
    while start <= end:
        middle = (end + start) // 2
        if li[middle] <= num:
            answer = middle
            start = middle + 1
        else:
            end = middle - 1
    return answer

def tir(a, b, c):
    if 0 == c:
        return 1
    if len(a) <= b:
        return 0
    if c != -1:
        return tir(a, 1 + b, c + a[b]) or tir(a, b + 1, c - a[b]) or tir(a, 1 + b, c)
    else:
        return tir(a, 1 + b, a[b]) or tir(a, b + 1, -a[b]) or tir(a, 1 + b, -1)

def abs(x):
    return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
    ans = -1
    while lb <= ub:
        mid = (lb + ub) // 2
        if li[mid] > val:
            ub = mid - 1
        elif val > li[mid]:
            lb = mid + 1
        else:
            ans = mid
            break
    return ans

def kadane(x):
    sum_so_far = 0
    current_sum = 0
    for i in x:
        current_sum += i
        if current_sum < 0:
            current_sum = 0
        else:
            sum_so_far = max(sum_so_far, current_sum)
    return sum_so_far

def pref(li):
    pref_sum = [0]
    for i in li:
        pref_sum.append(pref_sum[-1] + i)
    return pref_sum

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    li = []
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, len(prime)):
        if prime[p]:
            li.append(p)
    return li

def primefactors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:
        factors.append(n)
    return factors

def read():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def tr(n):
    return n * (n + 1) // 2
boi = int(998244353)
doi = int(1000000000.0 + 7)
hoi = int(500000.0 + 5)
soi = 499122177
poi = int(1000.0 + 50)
y = 'YES'
n = 'NO'

def bulli(x):
    return bin(x).count('1')
import sys
f = [0] * hoi
r = [0] * hoi

def ty(a, b):
    rr = 1
    while b:
        if b % 2:
            rr = rr * a % boi
        b = b // 2
        a = a * a % boi
    return rr

def inv(a):
    return ty(a, boi - 2)

def ncr(m, k):
    if m < 0 or k < 0 or k > m:
        return 0
    return f[m] * r[k] % boi * r[m - k] % boi

def gosa(a, b):
    if 0 != b:
        return gosa(b, a % b)
    return a
L = [0] * poi
d = [0] * poi

def start(p):
    L[0] = 1
    for i in range(1, 1000):
        for j in range(i, 1000):
            L[j] = (L[j - i] + L[j]) % p
    for i in range(1000):
        d[i] = L[i]
    for i in range(2, 5):
        M = [0] * poi
        for j in range(1000):
            for k in range(1 + j):
                M[j] = (d[j - k] * L[k] % p + M[j]) % p
        for j in range(1000):
            d[j] = M[j]

def ch(a, b, c):
    z = b * c - a
    print(b, c)
    for i in range(1, 1 + b):
        for j in range(1, 1 + c):
            if z == 0:
                print('#', end='')
            else:
                print('.', end='')
                z = z - 1
        print()

def op():
    import math as my
    m = so()
    z = int(my.sqrt(m))
    if m == z * z:
        ch(m, z, z)
        return
    z = 1 + z
    if m > (z - 1) * z:
        ch(m, z, z)
    else:
        ch(m, z - 1, z)
        return

def jp(p):
    import math as my
    m = so()
    z = int(my.sqrt(m))
    if m == z * z:
        print(z * 4, 1)
        return
    z = 1 + z
    (l, r, bec) = (z, z, 0)
    if m <= (z - 1) * z:
        l = l - 1
    while m <= l * r:
        if l == r:
            u = 1
        else:
            u = 2
        bec = (d[l * r - m] * u + bec) % p
        l = l - 1
        r = 1 + r
    print(2 * (l + r), bec)

def iu():
    import sys
    import math as my
    import functools
    import bisect as bs
    input = sys.stdin.readline
    from collections import deque, defaultdict
    ''
    (a, b) = mj()
    if b == 2:
        p = so()
        start(p)
    for i in range(a):
        if 1 == b:
            op()
        if 2 == b:
            jp(p)

def main():
    for i in range(1):
        iu()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()