레이팅 미적용소들은 창의적인 새 게임을 하나 생각해 냈는데, 놀랍게도 가능한 가장 창의적이지 않은 이름을 붙였다. 바로 "음메(Moo)"이다.
음메 게임은 정사각형 칸들로 이루어진 \(N \times N\) 격자 위에서 진행되며, 소는 "음메!"라고 외치고 칸에 자신의 숫자 ID를 적어 그 칸을 차지한다.
게임이 끝나면 모든 칸에 숫자가 하나씩 적혀 있다. 이 시점에, 어떤 소가 다른 어떤 영역보다 작지 않은 연결된 칸들의 영역을 만들었다면 그 소가 게임에서 승리한다. "영역"이란 모두 같은 ID 숫자를 가진 칸들의 그룹으로, 영역의 모든 칸이 같은 영역의 다른 어떤 칸과 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 직접 인접해 있는 것을 말한다(대각선은 인정하지 않는다).
혼자 플레이하는 것은 조금 지루하므로, 소들은 둘씩 짝을 지어 팀으로 플레이하는 것에도 관심이 있다. 두 소로 이루어진 팀은 이전과 같이 영역을 만들 수 있지만, 이제 영역의 칸들은 팀에 속한 두 소 중 어느 쪽의 것이어도 된다.
게임 판의 최종 상태가 주어졌을 때, 어느 한 소가 소유한 가장 큰 영역에 속하는 칸의 수와, 두 소 팀이 차지할 수 있는 가장 큰 영역에 속하는 칸의 수를 계산하도록 소들을 도와주자. 두 소 팀이 차지한 영역은 팀에 속한 두 소 중 한 소의 ID만이 아니라 두 소 모두의 ID 숫자를 포함할 때만 인정된다.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 250\))이 주어진다. 다음 \(N\)개의 줄에는 각각 게임 판의 최종 상태를 나타내는 정수 \(N\)개(각각 \(0 \ldots 10^6\) 범위)가 주어진다. 판에는 서로 다른 ID 숫자가 적어도 두 개 존재한다.
출력의 첫째 줄에는 어느 한 소가 차지한 가장 큰 영역의 크기를, 둘째 줄에는 어느 두 소 팀이 차지한 가장 큰 영역의 크기를 출력한다.
multimoo.in · 출력을 쓸 파일 multimoo.out4
2 3 9 3
4 9 9 1
9 9 1 7
2 1 1 95
10In this example, the largest region for a single cow consists of five 9s. If
cows with IDs 1 and 9 team up, they can form a region of size 10.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > US Open > Silver