Moo Hunt
브론즈 II의견: 0
Bessie is playing the popular game "Moo Hunt". In this game, there are \(N\)
(\(3 \le N \le 20\)) cells in a line, numbered from \(1\) to \(N\). All cells either
have the character \(M\) or \(O\) with the \(i\)-th cell having character \(s_i\).
Bessie plans to perform \(K\) (\(1 \le K \le 2 \cdot 10^5\)) mooves. On her \(i\)-th
moove, Bessie will tap \(3\) different cells (\(x_{i},y_{i},z_{i}\))
(\(1 \le x_{i},y_{i},z_{i} \le N\)). Bessie will earn a point if \(s_{x_i}=M\) and
\(s_{y_i}=s_{z_i}=O\). In other words, Bessie will earn a point if she forms the
string \(MOO\) by tapping cells \(x_{i},y_{i},z_{i}\) in that order.
Farmer John wants to help Bessie get a new high score. He wants you to find the
maximum possible score Bessie could get across all possible boards if she
performs the \(K\) mooves as well as the number of different boards that will
allow Bessie to achieve this maximum possible score. Two boards are different if
there exists a cell such that the corresponding characters at the cell are
different.
Problem credits: Alex Liang
SCORING
- Inputs 3-5: \(N \le 8, K \le 10^4\)
- Inputs 6-12: There will be one test for each \(N \in \{14,15,16,17,18,19,20\}\) with no additional constraints on \(K\).
Problem credits: Alex Liang
The first line contains \(N\) and \(K\), the number of cells and the number of
mooves Bessie will perform.
Each of the next \(K\) lines contains \(x_i, y_i, z_i\) describing Bessie's \(i\)-th
move (\(x_i, y_i, z_i\) are pairwise distinct).
Output the maximum possible score Bessie could achieve, followed by the count of
different boards that will allow Bessie to achieve this maximum score.
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
평가 및 의견
Moo Hunt
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Moo Hunt