시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB98353238.095%

문제

크기가 n이고, 체커보드처럼 n×n개의 칸으로 나누어져 있는 정사각형이 있다. 1 ≤ x1, y1, x2, y2 ≤ n 을 만족하는 두 위치 (x1, y1)와 (x2, y2)가 독립이 되려면, 서로 다른 행과 열을 차지하고 있어야 한다. 즉, x1 ≠ x2, y1 ≠ y2가 되어야 한다.n개의 위치가 독립일 되려면, 모든 쌍이 독립이 되어야 한다. 즉, 서로 다른 n개의 위치를 독립이 되도록 고르는 방법의 수는 총 n!개이다.

정사각형의 각 칸에 숫자가 쓰여 있다. 이 정사각형이 동차 정사각형이 되려면, n개의 독립적인 위치에 쓰여 있는 숫자의 합이 고르는 방법과 상관없이 항상 같아야 한다.

정사각형에 쓰여 있는 숫자가 주어졌을 때, 동차 정사각형인지 아닌지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 정사각형의 크기 n이 주어진다. (1 ≤ n ≤ 1000) 다음 n개 줄에는 n개의 숫자가 공백으로 구분되어서 주어진다. 각 숫자는 [-1000000, 1000000] 범위 내에 들어있다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 동차 정사각형이라면 "homogeneous"를, 아니라면 "not homogeneous"를 출력한다.

예제 입력 1

2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

예제 출력 1

homogeneous
not homogeneous
W3sicHJvYmxlbV9pZCI6IjY1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWNjMjggXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgblx1Yzc3NFx1YWNlMCwgXHVjY2I0XHVjZWU0XHViY2Y0XHViNGRjXHVjYzk4XHViN2ZjIG4mdGltZXM7blx1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNzg4XHViMmU0LiAxICZsZTsgeDEsIHkxLCB4MiwgeTIgJmxlOyBuIFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzcwNFx1Y2U1OCAoeDEsIHkxKVx1YzY0MCAoeDIsIHkyKVx1YWMwMCBcdWIzYzVcdWI5YmRcdWM3NzQgXHViNDE4XHViODI0XHViYTc0LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgeDEgJm5lOyB4MiwgeTEgJm5lOyB5Mlx1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0Lm5cdWFjMWNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjNjNVx1YjliZFx1Yzc3YyBcdWI0MThcdWI4MjRcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NzQgXHViM2M1XHViOWJkXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBuXHVhYzFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIzYzVcdWI5YmRcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViMjk0IFx1Y2QxZCBuIVx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViM2Q5XHVjYzI4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWI0MThcdWI4MjRcdWJhNzQsIG5cdWFjMWNcdWM3NTggXHViM2M1XHViOWJkXHVjODAxXHVjNzc4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVhY2UwXHViOTc0XHViMjk0IFx1YmMyOVx1YmM5NVx1YWNmYyBcdWMwYzFcdWFkMDBcdWM1YzZcdWM3NzQgXHVkNTZkXHVjMGMxIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWNjMjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc4XHVjOWMwIFx1YzU0NFx1YjJjY1x1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDAwKSBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWIyOTQgWy0xMDAwMDAwLCAxMDAwMDAwXSBcdWJjOTRcdWM3MDQgXHViMGI0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViM2Q5XHVjYzI4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1Yjc3Y1x1YmE3NCAmcXVvdDtob21vZ2VuZW91cyZxdW90O1x1Yjk3YywgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0ICZxdW90O25vdCBob21vZ2VuZW91cyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNjUyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvbW9nZW5lb3VzIHNxdWFyZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFzc3VtZSB5b3UgaGF2ZSBhIHNxdWFyZSBvZiBzaXplIG4gdGhhdCBpcyBkaXZpZGVkIGludG8gbiZ0aW1lcztuIHBvc2l0aW9ucyBqdXN0IGFzIGEgY2hlY2tlcmJvYXJkLiBUd28gcG9zaXRpb25zICh4MSx5MSkgYW5kICh4Mix5MiksIHdoZXJlIDEgJmxlOyB4MSx5MSx4Mix5MiAmbGU7IG4sIGFyZSBjYWxsZWQgJnF1b3Q7aW5kZXBlbmRlbnQmcXVvdDsgaWYgdGhleSBvY2N1cHkgZGlmZmVyZW50IHJvd3MgYW5kIGRpZmZlcmVudCBjb2x1bW5zLCB0aGF0IGlzLCB4MSZuZTt4MiBhbmQgeTEmbmU7eTIuIE1vcmUgZ2VuZXJhbGx5LCBuIHBvc2l0aW9ucyBhcmUgY2FsbGVkIGluZGVwZW5kZW50IGlmIHRoZXkgYXJlIHBhaXJ3aXNlIGluZGVwZW5kZW50LiBJdCBmb2xsb3dzIHRoYXQgdGhlcmUgYXJlIG4hIGRpZmZlcmVudCB3YXlzIHRvIGNob29zZSBuIGluZGVwZW5kZW50IHBvc2l0aW9ucy48XC9wPlxyXG5cclxuPHA+QXNzdW1lIGZ1cnRoZXIgdGhhdCBhIG51bWJlciBpcyB3cml0dGVuIGluIGVhY2ggcG9zaXRpb24gb2Ygc3VjaCBhbiBuJnRpbWVzO24gc3F1YXJlLiBUaGlzIHNxdWFyZSBpcyBjYWxsZWQgJnF1b3Q7aG9tb2dlbmVvdXMmcXVvdDsgaWYgdGhlIHN1bSBvZiB0aGUgbnVtYmVycyB3cml0dGVuIGluIG4gaW5kZXBlbmRlbnQgcG9zaXRpb25zIGlzIHRoZSBzYW1lLCBubyBtYXR0ZXIgaG93IHRoZSBwb3NpdGlvbnMgYXJlIGNob3Nlbi4gV3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSBpZiBhIGdpdmVuIHNxdWFyZSBpcyBob21vZ2VuZW91cyE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIGFuIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxMDAwKS4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGNvbnRhaW5zIG4gbnVtYmVycywgc2VwYXJhdGVkIGJ5IGV4YWN0bHkgb25lIHNwYWNlIGNoYXJhY3Rlci4gRWFjaCBudW1iZXIgaXMgYW4gaW50ZWdlciBmcm9tIHRoZSBpbnRlcnZhbCBbLTEwMDAwMDAsMTAwMDAwMF0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIHplcm8uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCB3aGV0aGVyIHRoZSBzcGVjaWZpZWQgc3F1YXJlIGlzIGhvbW9nZW5lb3VzIG9yIG5vdC4gQWRoZXJlIHRvIHRoZSBmb3JtYXQgc2hvd24gaW4gdGhlIHNhbXBsZSBvdXRwdXQ8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2006 H번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013