문제
어떤 양의 정수 $N$에 대해, 다음의 조건을 모두 충족하는 길이 $N$의 배열을 귀여운 배열이라고 하자.
- 이 배열에는 1ドル$ 이상 $N$ 이하의 모든 정수가 정확히 한 번씩 등장한다.
- 이 배열의 모든 길이 3ドル$ 이상의 부분 수열은 등차수열이 아니다. 부분 수열의 원소는 이웃하지 않을 수 있다.
그리고, 어떤 $N\times N$ 크기의 행렬에 대해 모든 행과 열이 귀여운 배열이면 이 행렬을 귀여운 행렬이라고 하자.
$N$이 주어졌을 때 귀여운 행렬이 존재하는지 여부를 판별하고, 존재한다면 그러한 행렬을 아무거나 하나 찾아 출력하시오.
출력
귀여운 행렬이 존재한다면 첫 줄에 1을 출력하고, 그 다음 $N$줄에 걸쳐 귀여운 행렬의 각 행의 $N$개 값을 공백으로 구분하여 출력한다.
귀여운 행렬이 존재하지 않는다면 첫 줄에 0을 출력한다.
서브태스크
| 번호 | 배점 | 제한 | | 1 | 4 | $N \le 4$.
|
| 2 | 96 | 추가적인 제약 조건이 없다.
|
W3sicHJvYmxlbV9pZCI6IjMzODA0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQ3V0ZSBNYXRyaXgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjVhNCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4ICROJFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViYWE4XHViNDUwIFx1Y2RhOVx1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFlMzhcdWM3NzQgJE4kXHVjNzU4IFx1YmMzMFx1YzVmNFx1Yzc0NCA8c3Ryb25nPlx1YWRjMFx1YzVlY1x1YzZiNCBcdWJjMzBcdWM1ZjQ8XC9zdHJvbmc+XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3NzQgXHViYzMwXHVjNWY0XHVjNWQwXHViMjk0ICQxJCBcdWM3NzRcdWMwYzEgJE4kIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhZTM4XHVjNzc0ICQzJCBcdWM3NzRcdWMwYzFcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWI0ZjFcdWNjMjhcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWM3NzRcdWM2YzNcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhZGY4XHViOWFjXHVhY2UwLCBcdWM1YjRcdWI1YTQgJE5cXHRpbWVzIE4kIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQ1ODlcdWI4MmNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YmFhOFx1YjRlMCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzc0IFx1YWRjMFx1YzVlY1x1YzZiNCBcdWJjMzBcdWM1ZjRcdWM3NzRcdWJhNzQgXHVjNzc0IFx1ZDU4OVx1YjgyY1x1Yzc0NCA8c3Ryb25nPlx1YWRjMFx1YzVlY1x1YzZiNCBcdWQ1ODlcdWI4MmM8XC9zdHJvbmc+XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+JE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVhZGMwXHVjNWVjXHVjNmI0IFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNWVjXHViZDgwXHViOTdjIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YWNlMCwgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWQ1ODlcdWI4MmNcdWM3NDQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1ZDU1OFx1YjA5OCBcdWNjM2VcdWM1NDQgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROJFx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWRjMFx1YzVlY1x1YzZiNCBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjE8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyAkTiRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWRjMFx1YzVlY1x1YzZiNCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVhYzAxIFx1ZDU4OVx1Yzc1OCAkTiRcdWFjMWMgXHVhYzEyXHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkYzBcdWM1ZWNcdWM2YjQgXHVkNTg5XHViODJjXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgXHVjY2FiIFx1YzkwNFx1YzVkMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MDxcL2NvZGU+PFwvc3Bhbj5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMVxcbGUgTlxcbGUgMzAwJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDQkLjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMzODA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ3V0ZSBNYXRyaXgiLCJkZXNjcmlwdGlvbiI6IjxwPkZvciBzb21lIHBvc2l0aXZlIGludGVnZXIgJE4kLCBhbiBhcnJheSBvZiAkTiQgaW50ZWdlcnMgaXMgY2FsbGVkIGEgPHN0cm9uZz5jdXRlIGFycmF5PFwvc3Ryb25nPiBpZiBpdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBhcnJheSBjb250YWlucyBldmVyeSBpbnRlZ2VyIGZyb20gJDEkIHRvICROJCBleGFjdGx5IG9uY2UuPFwvbGk+XHJcblx0PGxpPkV2ZXJ5IHN1YnNlcXVlbmNlIG9mIGxlbmd0aCAkMyQgb3IgbW9yZSBtdXN0IG5vdCBmb3JtIGFuIGFyaXRobWV0aWMgcHJvZ3Jlc3Npb24uIE5vdGUgdGhhdCBhIHN1YnNlcXVlbmNlIG1heSBiZSBub25jb250aWd1b3VzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsc28sIGEgbWF0cml4IG9mIHNpemUgJE4gXFx0aW1lcyBOJCBpcyBjYWxsZWQgYSA8c3Ryb25nPmN1dGUgbWF0cml4PFwvc3Ryb25nPiZuYnNwO2lmIGV2ZXJ5IHJvdyBhbmQgZXZlcnkgY29sdW1uIGlzIGEgY3V0ZSBhcnJheS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHZhbHVlIG9mICROJCwgb3V0cHV0IGFueSBjdXRlIG1hdHJpeCBpZiBzdWNoIGEgbWF0cml4IGV4aXN0cywgb3IgcmVwb3J0IHRoYXQgbm9uZSBleGlzdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgJE4kLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIGEgY3V0ZSBtYXRyaXggZXhpc3RzLCBwcmludCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MTxcL2NvZGU+PFwvc3Bhbj4gb24gdGhlIGZpcnN0IGxpbmUuIFRoZW4sIG92ZXIgdGhlIG5leHQgJE4kIGxpbmVzLCBwcmludCB0aGUgZWxlbWVudHMgb2YgZWFjaCByb3cgb2Ygc3VjaCBhIG1hdHJpeCBvbiBhIGxpbmUsIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5JZiBubyBjdXRlIG1hdHJpeCBleGlzdHMsIHByaW50IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4wPFwvY29kZT48XC9zcGFuPiBvbiB0aGUgZmlyc3QgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZSBOXFxsZSAzMDAkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgNCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIn1d