#P10122. [USACO18OPEN] Team Tic Tac Toe B

[USACO18OPEN] Team Tic Tac Toe B

Problem Description

Farmer John has 2626 cows, and it so happens that their names all start with different letters. So Farmer John uses the first letter of each cow’s name to refer to her—a letter from A-Z.

Recently, the cows have become obsessed with tic-tac-toe, but since they are not satisfied with only two cows playing together, they have adapted the game so that many cows can play at once. Just like regular tic-tac-toe, the game is played on a 3×33 \times 3 board, but instead of using only X and O, each cell is marked with a letter from A-Z, representing the first letter of the cow who occupies that cell.

Here is an example board:

COW
XXO
ABC

The cows will fill all nine cells before they get confused about how to determine the winner. Clearly, as in regular tic-tac-toe, if any single cow occupies an entire row, an entire column, or an entire diagonal, then that cow wins. However, since the cows think this is not easy to happen in a multi-cow game, they decided to allow cows to form teams of two. If some row, column, or diagonal contains only the letters of the two cows on a team, and also contains letters from both cows (not just one), then that team wins.

Please help the cows determine how many single cows or two-cow teams can win. Note that the same cell on the board may be used in wins for different cows or teams.

Input Format

The input contains three lines, each with three characters from A-Z.

Output Format

The output contains two lines. On the first line, output the number of individual cows that can win. On the second line, output the number of two-cow teams that can win.

COW
XXO
ABC
0
2

Hint

In this example, no single cow can win. However, if cow C and cow X form a team, they can win via the diagonal C-X-C. Similarly, if cow X and cow O form a team, they can win via the middle row.

Translated by ChatGPT 5