시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 21 16 48.485%

문제

N행, M열로 이루어진 표에 32비트 부호있는 정수가 저장되어 있다. 제일 왼쪽 열은 1이고, 오른쪽으로 갈 수록 번호가 1씩 증가한다.

Ai(1 ≤ i ≤ M)를 i번 열에 있는 모든 수의 곱으로 정의하자. 이때, 가장 큰 값을 갖는 열의 번호를 찾는 프로그램을 작성하시오. 그러한 열이 여러개라면, 번호가 가장 큰 열을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 M과 N이 주어진다. (1 ≤ M ≤ 20, 1 ≤ N ≤ 1000) 다음 N개 줄에는 M개의 32비트 부호있는 정수가 주어진다.

출력

각 테스트 케이스에 대해서 한 줄에 하나씩 가장 큰 곱을 갖는 열의 번호를 출력한다.

예제 입력 1

2
3 3
20 10 30
15 20 20
30 30 20
3 2
2 -2 2
2 -2 2

예제 출력 1

3
3
W3sicHJvYmxlbV9pZCI6IjM3MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0NWMiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWQ1ODksIE1cdWM1ZjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDQ1Y1x1YzVkMCAzMlx1YmU0NFx1ZDJiOCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWM2N2NcdWNhYmQgXHVjNWY0XHVjNzQwIDFcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4XHViODVkIFx1YmM4OFx1ZDYzOFx1YWMwMCAxXHVjNTI5IFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+QTxzdWI+aTxcL3N1Yj4oMSAmbGU7IGkgJmxlOyBNKVx1Yjk3YyBpXHViYzg4IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NCBcdWM1ZjRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjNWY0XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yjc3Y1x1YmE3NCwgXHViYzg4XHVkNjM4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTVx1YWNmYyBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBNICZsZTsgMjAsIDEgJmxlOyBOICZsZTsgMTAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggMzJcdWJlNDRcdWQyYjggXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhY2YxXHVjNzQ0IFx1YWMxNlx1YjI5NCBcdWM1ZjRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgVGFibGUiLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIHRoZSB0YWJsZSBvZiAzMi1iaXQgc2lnbmVkIGludGVnZXJzIHdpdGggbiByb3dzIGFuZCBtIGNvbHVtbnMuIFRoZSBjb2x1bW5zIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbSBiZWdpbm5pbmcgZnJvbSB0aGUgbGVmdCBzaWRlIG9mIHRoZSB0YWJsZS4gTGV0IEFpICgxICZsZTsgaSAmbGU7IG0pIGlzIHRoZSBwcm9kdWN0IG9mIGFsbCBudW1iZXJzIGluIHRoZSBpLXRoIGNvbHVtbi4gRmluZCB0aGUgbWF4aW11bSBvZiB0aGVzZSBwcm9kdWN0cyBhbmQgcHJpbnQgdGhlIGNvbHVtbiBudW1iZXIgd2hlcmUgdGhpcyBtYXhpbXVtIHByb2R1Y3QgaXMgYWNoaWV2ZWQuIElmIHRoZXJlIGFyZSBtYW55IHN1Y2ggY29sdW1ucywgcHJpbnQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHRoZSBjb2x1bW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Db25zaXN0cyBvZiBtdWx0aXBsZSB0ZXN0cy4gRWFjaCB0ZXN0IGJlZ2lucyB3aXRoIGEgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBtIGFuZCBuICgxICZsZTsgbSAmbGU7IDIwLCAxICZsZTsgbiAmbGU7IDEwMDApLiBFYWNoIG9mIHRoZSBuZXh0IG4gbGluZXMgY29udGFpbnMgbSAzMi1iaXQgc2lnbmVkIGludGVnZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBvbiBhIHNlcGFyYXRlIGxpbmUgdGhlIGNvbHVtbiBudW1iZXIgd2l0aCB0aGUgbWF4aW11bSBwcm9kdWN0LiBJZiB0aGVyZSBhcmUgc2V2ZXJhbCBvZiB0aGVtICZuZGFzaDsgcHJpbnQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHN1Y2ggY29sdW1uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2010 A번

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