#PU1327. USACO 2023 US Open Contest, Silver — Problem 2. Field Day

USACO 2023 US Open Contest, Silver — Problem 2. Field Day

USACO 2023 US Open Contest, Silver — Problem 2. Field Day

题目描述

Note: The time limit for this problem in Python is 15s. Other languages have the default time limit of 2s. Each of Farmer John's NN barns (2≤N≤1052\le N\le 10^5) has selected a team of CC cows (1≤C≤181\le C\le 18) to participate in field day. The breed of every cow is either a Guernsey or a Holstein. The difference between two teams is defined to be the number of positions ii (1≤i≤C1 \leq i \leq C) at which the breeds of the cows in the iith positions differ. For every team tt from 1…N1 \ldots N, please compute the maximum difference between team tt and any other team.

输入格式

The first line contains CC and NN. The next NN lines each contain a string of length CC of Gs and Hs. Each line corresponds to a team.

输出格式

For each team, print the maximum difference.

数据范围

Inputs 2-5: C=10C = 10 Inputs 6-9: All answers are at least C−3C-3. Inputs 10-20: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

5 3
GHGGH
GHHHH
HGHHG
5
3
5
The first and third teams differ by $5$. The second and third teams differ by
$3$.