로봇
시간 제한1초메모리 제한1024 MB
로봇이 오른쪽이나 아래로만 움직여 왼쪽 위에서 오른쪽 아래까지 가는 경로가 정확히 K개가 되도록 미로를 만듭니다. R과 S는 1000 이하입니다.
문제
크레쇼는 로봇과 노는 것을 좋아한다. 그는 로봇을 위해 미로를 만들고, 로봇이 그 안에서 어떻게 움직이는지 지켜본다.
로봇은 미로의 왼쪽 위 칸에서 출발한다. 미로는 R개의 행과 S개의 열로 된 판이며, 일부 칸은 막혀 있다. 로봇은 매 순간 현재 칸의 오른쪽 칸이나 아래 칸으로 이동할 수 있다. 그 칸이 막혀 있으면 로봇은 그곳으로 갈 수 없다. 로봇이 오른쪽 아래 칸에 도착하면 게임이 끝난다.
크레쇼는 게임에서 로봇이 취할 수 있는 서로 다른 경로가 정확히 K개가 되는 미로를 만들고 싶어 한다. 한 경로가 지나는 칸 중에 다른 경로가 지나지 않는 칸이 하나라도 있으면 두 경로는 서로 다른 것이다. 크레쇼가 이런 미로를 만들도록 도와라.
미로의 크기는 자유롭게 정할 수 있지만, R과 S는 모두 1000 이하여야 한다. 왼쪽 위 칸과 오른쪽 아래 칸은 막을 수 없다.
입력
첫 번째이자 유일한 줄에 자연수 K가 주어진다 (1 ≤ K ≤ 1 000 000 000).
출력
첫 번째 줄에 미로의 크기 R, S를 출력한다 (1 ≤ R, S ≤ 1 000).
이어서 R개의 줄에 각각 S개의 문자 '0' 또는 '1'을 출력한다. '1'은 막힌 칸, '0'은 빈 칸을 뜻한다.
힌트
첫 번째 테스트 데이터에 대한 설명: 아래 미로는 문제에서 설명한 대로 경로가 하나만 존재하는 미로 중 하나이다. 다음 풀이도 가능하다.
4 4
0001
0101
1001
0100