올림픽

문제 정보

문제

4년마다 열리는 올림픽에서는 순위에 따라 선수들에게 금, 은, 동메달을 수여한다. 따라서 선수들의 국적을 바탕으로 각 국가가 획득한 메달의 수를 셀 수 있다. 공식적으로는 이를 통해 각 국가의 순위를 가리는 방법이 없지만, 본질적으로 순위를 매기는 편이 더 재미있고 열기를 고취시킬 수 있기 때문에 순위를 매기는 방법들이 고안되었다. 이 문제에서는 널리 쓰이는 두 가지 방법을 생각해 본다.

  • 국가 x의 등수는 (국가 x보다 좋은 성적을 거둔 국가의 수 + 1) 로 정의한다.
  • 방법 1. 메달의 수를 종류에 관계 없이 세어 많은 국가가 적은 국가보다 좋은 성적이라 정의한다.
  • 방법 2. 금메달이 많은 국가가 적은 국가보다 좋은 성적이라 정의한다. 단, 같을 경우는 은메달이 많은 국가를 좋은 성적으로 정의하며, 은메달도 같은 경우는 동메달이 많은 국가를 좋은 성적으로 정의한다.

N개의 국가가 경쟁 중이며, 앞으로 K개의 경기가 남았다. 앞선 경기는 반드시 그렇지는 않았지만 남은 경기 모두는 금, 은, 동메달이 서로 다른 국가에 하나씩 주어지는 종목이다. 지금까지 그들이 획득한 메달의 수가 주어질 때, 앞으로 남은 K 경기의 결과에 따른 최선의 등수를 두 방법 각각에 대해 구하는 프로그램을 작성하라.

입력

입력은 T 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 T 가 주어진다.

각 테스트 케이스의 첫 행에는 두 정수 N\,(3 \le N \le 100), K\,(0 \le K \le 1,000) 가 공백으로 구분되어 주어진다. 다음 N 행에 걸쳐 한 행에 하나씩 각 국가가 획득한 금, 은, 동메달의 수가 공백으로 구분되어 주어진다.
각 메달의 수는 1,000을 넘지 않는다.

출력

각 테스트 케이스에 대해 두 행에 나누어 입력에서 주어진 순서에 따라 각 국가의 방법 1에 따른 최선의 등수를 공백으로 구분하여 출력하고, 다음 행에 마찬가지로 방법 2에 따른 최선의 등수를 출력한다.

예제 입력

2
4 1
1 1 1
0 1 0
0 0 1
0 0 1
4 1
0 0 0
1 0 0
0 1 0
0 0 1

예제 출력

1 2 2 2
1 2 2 2
3 1 1 1
1 1 1 1

노트

  • 첫 번째 테스트 케이스: 첫 번째 국가가 남은 경기에서 메달을 획득하지 못하더라도 다른 국가가 어떤 방법으로도 더 잘 할 수 없다.
  • 두 번째 테스트 케이스: 방법 1에 의하면, 첫 번째 국가를 제외한 모든 국가는 적어도 공동 1위가 될 수 있다. 그러나 첫 번째 국가의 경우 세 국가 중 적어도 둘은 메달을 획득하므로 첫 번째 국가보다 앞설 수밖에 없다. 방법 2에 의하면 어느 국가도 자신이 금메달을 획득하고 나머지 국가들이 적당히 은, 동메달을 나누어 가지면 1위가 될 수 있다.

7개의 댓글이 있습니다.