레이팅 미적용N개의 행과 M개의 열로 구성된 격자판의 각 칸에 숫자들이 들어있다. 정수 K \((K \ge 2)\)가 주어진다. K는 N보다 작고, M보다도 작다. 격자판에서 R개의 행과 C개의 열을 R + \(C = K\)가 만족하도록 선택하고, 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자가 최소가 되도록 하려고 한다. \(N = 4,\) \(M = 5\)인 경우의 격자판의 예가 다음 그림과 같이 주어졌다고 하자.
위의 예에서 \(K = 3\)인 경우, 1행, 3행과 4열을 선택하면 다음 그림과 같이 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 제일 큰 숫자는 5이다.
3행, 3열과 4열을 선택하여도 선택된 행과 열을 제외한 나머지 칸 가운데 제일 큰 숫자는 5이다. 그러나 달리 선택하여 나머지 칸에 있는 숫자들이 모두 5보다 작게 만들 수는 없다.
숫자들이 들어있는 격자판과 선택할 수 있는 행의 개수와 열의 개수의 합이 주어졌을 때, 선택한 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자가 최소가 되도록 행과 열을 선택하기 위한 프로그램을 작성하시오.
※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.
첫 줄에는 격자판의 크기를 나타내는 정수 N과 M이 주어진다. N과 M은 3 이상이며, 300 이하인 정수이다. 둘째 줄에는 선택할 수 있는 행과 열의 개수의 합 K \((K < N,\) \(K < M)\)가 주어진다. 셋째 줄부터 격자판에 들어있는 양의 정수들이 한 줄에 한 행씩 1행부터 차례대로 주어진다. 격자판에 들어있는 각 숫자는 1 이상 500,000 이하의 정수이다. 같은 줄에 입력되는 각 정수들 사이에는 한 개의 공백이 있다.
첫 번째 줄에 R + \(C = K\)를 만족하는 R개의 행과 C개의 열을 선택하여, 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자의 최솟값을 출력한다. 둘째 줄에는 선택한 행의 개수와 이어서 행 번호를 오름차순으로 출력한다. 셋째 줄에는 선택한 열의 개수와 이어서 열 번호를 오름차순으로 출력한다. 행의 개수나 열의 개수가 0인 경우에는 해당하는 줄에 0만 출력한다. 같은 줄에 출력되는 각 정수들 사이에는 한 개의 공백을 둔다.
조건을 만족하는 답이 여러 개인 경우에는 그 중에서 하나만 출력하면 된다.
4 5
3
3 1 7 6 3
3 4 2 8 2
8 6 4 2 4
3 5 1 2 1
5
3 1 2 3
0
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2007 > 2차 대회 > 고등부 2번