레이팅 미적용베시(Bessie)는 인기 게임 "음머 사냥(Moo Hunt)"을 플레이하고 있다. 이 게임에는 \(N\)개 (\(3 \le N \le 20\))의 칸이 한 줄로 놓여 있고, \(1\)부터 \(N\)까지 번호가 붙어 있다. 모든 칸에는 문자 \(M\) 또는 \(O\)가 적혀 있으며, \(i\)번째 칸의 문자는 \(s_i\)이다.
베시는 \(K\)번 (\(1 \le K \le 2 \cdot 10^5\))의 음직임(moove)을 수행할 계획이다. \(i\)번째 음직임에서 베시는 서로 다른 \(3\)개의 칸 (\(x_{i},y_{i},z_{i}\)) (\(1 \le x_{i},y_{i},z_{i} \le N\))을 두드린다. \(s_{x_i}=M\)이고 \(s_{y_i}=s_{z_i}=O\)이면 베시는 1점을 얻는다. 다시 말해, 칸 \(x_{i},y_{i},z_{i}\)를 순서대로 두드려 문자열 \(MOO\)를 만들면 점수를 얻는다.
농부 존(Farmer John)은 베시가 새로운 최고 기록을 세우도록 돕고 싶어 한다. 존은 베시가 \(K\)번의 음직임을 수행할 때 가능한 모든 보드에 대해 베시가 얻을 수 있는 최대 점수와, 그 최대 점수를 달성할 수 있게 하는 서로 다른 보드의 수를 구해 주기를 원한다. 어떤 칸에서 두 보드의 해당 문자가 서로 다르면 두 보드는 서로 다른 것이다.
문제 제공: Alex Liang
배점
- 입력 3-5: \(N \le 8, K \le 10^4\)
- 입력 6-12: 각 \(N \in \{14,15,16,17,18,19,20\}\)에 대해 테스트가 하나씩 있으며, \(K\)에 대한 추가 제약은 없다.
문제 제공: Alex Liang
첫째 줄에 칸의 수 \(N\)과 베시가 수행할 음직임의 수 \(K\)가 주어진다.
다음 \(K\)개의 줄에는 베시의 \(i\)번째 음직임을 나타내는 \(x_i, y_i, z_i\)가 주어진다 (\(x_i, y_i, z_i\)는 쌍마다 서로 다르다).
베시가 얻을 수 있는 최대 점수를 출력한 뒤, 그 최대 점수를 달성할 수 있게 하는 서로 다른 보드의 수를 출력한다.
5 6
1 2 3
1 2 3
1 3 5
2 3 4
5 3 2
5 2 34 2The boards \(MOOOM\) and \(MOOMM\) allow Bessie to achieve a maximum score of \(4\).
In both boards, Bessie will earn points on mooves \(1,2,5,6\). It can be shown
that this is the maximum score Bessie can achieve, and those two boards are the
only possible boards allowing Bessie to achieve a score of \(4\).
6 12
2 4 3
2 3 4
3 5 2
3 5 1
3 1 5
3 1 2
6 1 5
1 6 4
2 3 6
3 6 2
4 1 6
3 4 26 3The boards that allow Bessie to achieve a maximum possible score of \(6\) are
\(OOMOOO\), \(OOMMOO\), and \(OOMOOM\).
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Bronze