AT_abc323_c [ABC323C] World Tour Finals

题目描述

有 $N$ 名选手参加的编程竞赛 World Tour Finals 正在进行中，比赛时间已经过了一半。本次比赛共出了 $M$ 道题目，第 $i$ 道题的分值 $A_i$ 是 $500$ 到 $2500$ 之间的 $100$ 的倍数。

对于每个 $i=1,\ldots,N$，给出一个字符串 $S_i$，表示选手 $i$ 已经解出的题目。$S_i$ 是由 o 和 x 组成的长度为 $M$ 的字符串，$S_i$ 的第 $j$ 个字符为 o 时，表示选手 $i$ 已经解出了第 $j$ 道题，为 x 时表示还未解出。注意，没有任何一名选手已经解出了所有题目。

选手 $i$ 的总得分为其已解出题目的分值之和，加上奖励分 $i$ 分。

现在，对于每个 $i=1,\ldots,N$，请回答以下问题：

• 选手 $i$ 至少还需要解出多少道尚未解出的题目，才能使其总得分超过其他所有选手当前的总得分？

另外，根据题目中的条件和限制，可以证明选手 $i$ 如果解出所有题目，一定可以超过其他所有选手当前的总得分。因此，答案总是存在。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出 $N$ 行。第 $i$ 行输出关于选手 $i$ 的问题的答案。

输入输出样例 #1

输入 #1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

输出 #1

0
1
1

输入输出样例 #2

输入 #2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

输出 #2

1
1
1
1
0

输入输出样例 #3

输入 #3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

输出 #3

7
6
5
4
3
2
0

说明/提示

限制条件

• $2\leq N\leq 100$
• $1\leq M\leq 100$
• $500\leq A_i\leq 2500$
• $A_i$ 是 $100$ 的倍数
• $S_i$ 是由 o 和 x 组成的长度为 $M$ 的字符串
• $S_i$ 至少包含一个 x
• 输入的所有数值均为整数

样例解释 1

比赛进行到一半时，各选手的总得分分别为：选手 $1$ 为 $2001$ 分，选手 $2$ 为 $1502$ 分，选手 $3$ 为 $1703$ 分。选手 $1$ 即使一题不做，也已经超过了其他所有选手的总得分。选手 $2$ 只要解出第 $4$ 题，总得分就能达到 $3502$ 分，超过其他所有选手。选手 $3$ 也只要解出第 $4$ 题，总得分就能达到 $3703$ 分，超过其他所有选手。

由 ChatGPT 4.1 翻译