from __future__ import print_function
from sys import stdin
import sys

def printf(str, *args):
    print(str % args, end='')

domain = 21        # 집합의 크기를 표현하는 상수
rel_size = 18      # 멱집합에서 나누어떨어진다는 것을 만족하는 관계의 크기를 위한 변수

# 순서쌍을 출력하는 함수
def print_pair(i, map_power_set, l, r):
    print(l, map_power_set[i][0], ", ", map_power_set[i][1], r,  end = ",", sep = '')

# matrixout 함수가 정방행렬 mx를 출력
def matrixout(mx, size):
    print("\u250c                  \u2510")
    for i in range(0, size):
        print("| ", end = "")
        for j in range(0, size):
            print("%3d" % mx[i][j], end = " ")
        print(" |")
    print("\u2514                  \u2518")

# setout 함수가 주어진 집합을 출력
def setout(A):
    count = 0
    if 1 not in A:
        print("\u2205")
        return
    printf("{")
    for i in range(0, domain):
        if A[i] == 1:
            if count != 0:
                printf(", ")
            printf("%d"%(i))
            count = 1
    
    printf("}")

setB = [0 for _ in range(0,domain)]     # 집합 B를 위한 배열 선언
relationD = []                          # 관계 D를 위한 이차원 배열 선언
lub_list = []           # 각 원소에 대한 첫 단계의 상계를 저장하는 리스트 구조
glb_list = []           # 각 원소에 대한 첫 단계의 하계를 저장하는 리스트 구조
count = 0                            # 집합 B가 가질 원소의 개수를 위한 변수
relation_number = 0                  # 격자가 가질 관계의 원소 개수를 위한 변수

# 20보다 작은 자연수에 대해 i|20을 만족하는 원소를 찾음
for i in range(1, domain):
    if 20 % i == 0:                  # i|20이면 
        setB[i] = 1
        count = count + 1

#setB[19] = 1                        # 마지막으로 20도 집합 B에 추가
setA = [1 for _ in range(0,count)]   # 원소들을 직접 저장하기 위한 배열
index = 0                           

for i in range(1, domain):
    if setB[i] == 1:
        setA[index] = i
        index = index + 1

# 집합 D에 대한 관계행렬 선언 
adjacencymx = [[0 for j in range(count)] for i in range(count)]
adjacencymx_lattice = [[0 for j in range(count)] for i in range(count)]
print("\nD\u2082\u2080 =", end = " ")
setout(setB)                       # 계산된 집합 A를 출력

# 집합 D의 원소에 대해 i|j를 만족하는 쌍을 찾음
for i in range(0, count):
    for j in range(i, count):
        if i <= j:
            relationD.append([setA[i],setA[j]])          
            relation_number = relation_number + 1
        if setA[j] % setA[i] == 0:             # i|j이면  
            adjacencymx[i][j] = 1
            adjacencymx_lattice[i][j] = 1

print("이고 부분순서관계 R = (D\u2082\u2080, ⪯) = { ")
for i in range(0, relation_number):
    if relationD[i][1] % relationD[i][0] == 0: 
        print_pair(i, relationD, '(', ')')

print("\b}이다. 하세 도형은 다음과 같다.\n")
print("                       20    ")
print("                      /  \   ")
print("                     4   10  ")
print("                      \ / |  ")
print("                       2  5  ")
print("                        \/   ")
print("                         1   \n")
print("집합 D\u2099의 임의의 두 원소에 대한 상한과 하한은 다음과 같다.\n")

# 관계행렬에 존재하는 추이관계와 반사관계를 만족하는 원소들을 제거함
for i in range(0, count):
    adjacencymx_lattice[i][i] = 0
    for j in range(0, count):
        if adjacencymx_lattice[i][j] == 1:
            for k in range(0, count):
                # iRj가 있을 때 jRk와 iRk가 있으면
                if adjacencymx_lattice[j][k] == 1 and adjacencymx_lattice[i][k] == 1 and j != k:
                    adjacencymx_lattice[i][k] = 0   # 추이관계인 원소 iRk를 제거

flag_break = False
for i in range(0, relation_number):
    first = setA.index(relationD[i][0])   # 관계의 첫 번째 원소의 인덱스를 대입
    second = setA.index(relationD[i][1])  # 관계의 두 번째 원소의 인덱스를 대입
    if first > second:    # 첫 번째 원소가 두 번째 원소보다 크면 다음 반복으로 건너뜀
        continue
    if first == second:   # 관계의 두 원소가 같으면 상한도 하한도 같음
        print_pair(i, relationD, '{','}') 
        print("\b의 상한은 ", relationD[i][0],", 하한은 ", relationD[i][1], "이다.", end="", sep = '')
    
    else:
        # 해당 이중 반복문으로 관계에 대한 상한을 찾고 출력
        for j in range(first + 1, count):
            for k in range(second, count):
                # 관계의 원소들의 상계 중에 상한과 같은 것을 확인
                if j == k and adjacencymx[first][j] == 1 and adjacencymx[second][k] == 1:
                    # 관계와 상한을 출력
                    print_pair(i, relationD, '{', '}') 
                    print("\b의 상한은 ", setA[j], end=",", sep = '')
                    flag_break = True   # 상한을 찾은 후 반복문을 나감
                    break
            if flag_break == True:      # 상한을 찾은 후 바깥쪽 반복문도 나감
                flag_break = False
                break
        
        # 해당 이중 반복문으로 관계에 대한 하한을 찾고 출력
        for j in range(first, -1, -1):
            for k in range(second - 1, -1, -1):
                # 관계의 원소들의 하계 중에 하한과 같은 것을 확인
                if j == k and adjacencymx[j][first] == 1 and adjacencymx[k][second] == 1:
                    # 관계와 하한을 출력
                    print("하한은 ", setA[j], "이다.", end="", sep = '')
                    flag_break = True   # 하한을 찾은 후 반복문을 나감
                    break
            if flag_break == True:      # 하한을 찾은 후 바깥쪽 반복문도 나감
                flag_break = False
                break
    print()
 
print("따라서 임의의 두 원소에 대한 상한과 하한이 하나씩 존재하므로 격자이다.\n\n")
