2026 年 USACO竞赛 第二场比赛铜奖组问题二—Moo Hunt

Bessie is playing the popular game "Moo Hunt". In this game, there are N (3≤N≤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 si.

Bessie plans to perform K (1≤K≤2⋅105) mooves. On her i-th moove, Bessie will tap 3 different cells (xi,yi,zi) (1≤xi,yi,zi≤N). Bessie will earn a point if  sxi=M
and syi=szi=O. In other words, Bessie will earn a point if she forms the string MOO by tapping cells xi,yi,zi 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.

INPUT FORMAT (input arrives from the terminal / stdin):

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 xi,yi,zi describing Bessie's i-th move (xi,yi,zi are pairwise distinct).

OUTPUT FORMAT (print output to the terminal / stdout):

Output the maximum possible score Bessie could achieve, followed by the count of different boards that will allow Bessie to achieve this maximum score.

SAMPLE INPUT:

5 6
1 2 3
1 2 3
1 3 5
2 3 4
5 3 2
5 2 3

SAMPLE OUTPUT:

4 2

The 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.

SAMPLE INPUT:

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 2

SAMPLE OUTPUT:

6 3

The boards that allow Bessie to achieve a maximum possible score of 6 are OOMOOO, OOMMOO, and OOMOOM.

SCORING:

Inputs 3-5: N≤8,K≤104

Inputs 6-12: There will be one test for each N∈{14,15,16,17,18,19,20} with no  additional constraints on K.

Problem credits: Alex Liang

历年学员USACO获奖战绩一览

2026赛季5位铂金级
2024-2025赛季5位铂金级
20238位铂金级

USACO 历年战绩

2026赛季战绩

  • 5位铂金级
  • 22位金级
  • 25位银级

2024–2025赛季战绩

翰林考点及辅导学生

  • 5位铂金级
  • 25位金级
  • 38位银级

2023–2024赛季战绩

  • 8位铂金级
  • 32位金级
  • 37位银级

2022–2023赛季战绩

  • 10位铂金级
  • 29位金级
  • 71位银级

篇幅有限,仅展示部分年份战绩。

在线咨询
微信咨询