직사각형

• 30×30개의 모든 셀을 이용해서 최적의 답을 찾으려고 시도하면 함정에 빠지기 쉽다.
• 약 팔기 를 확장한다는 아이디어로 접근하면 간단하다. 약 팔기을 가운데 칸을 중심으로 양쪽으로 2개의 축이 있어서, 그것을 이용해서 k진법의 2자리 수를 만드는 문제로 생각해보자. 그럼 이 문제는 가운데 칸을 중심으로 4개의 축이 있어서 k진법의 4자리 수를 만드는 것으로 생각할 수 있다. 가운데 칸을 중심으로 십자 방향의 칸들을 제외한 나머지 칸들에는 전부 0을 채우면 된다.
• 그러면 모든 축의 길이를 14 이상으로 만들수 있으므로, 15진법의 4자리 수를 모두 만들 수 있다. 15^4 - 1 = 50624이므로 문제에서 요구한 50000보다 크다.

"""Solution code for "BOJ 19568. 직사각형".

- Problem link: https://www.acmicpc.net/problem/19568
- Solution link: http://www.teferi.net/ps/problems/boj/19568

Tags: [ad hoc]
"""


def main():
    row = [0] * 30
    row[15] = 1
    for _ in range(14):
        print(*row)
    print(*([15] * 15 + [0] + [15 * 15] * 14))
    row[15] = 15 * 15 * 15
    for _ in range(15):
        print(*row)


if __name__ == '__main__':
    main()