World Tour Finals

题目描述

编程比赛 World Tour Finals 正在进行中，$N$ 名选手参加了比赛，比赛时间已经过了二分之一。 本次比赛共有 $M$ 道题目，第 $i$ 道题的分数 $A_i$ 是 $500$ 到 $2500$（包含两端）之间且为 $100$ 的倍数。 对于每个 $i = 1, \ldots, N$，给出一个字符串 $S_i$ 表示选手 $i$ 已经做出的题目。 $S_i$ 是长度为 $M$ 的由 $o$ 和 $x$ 组成的字符串，其中 $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$ 的问题的答案。

3 4
1000 500 700 2000
xxxo
ooxx
oxox

0
1
1

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

1
1
1
1
0

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

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$ 是长度为 $M$ 的由 $o$ 和 $x$ 组成的字符串。 $S_i$ 至少包含一个 $x$。 输入中的所有数值都是整数。在比赛过半时，各选手的总分分别为选手 $1$ 为 $2001$ 分，选手 $2$ 为 $1502$ 分，选手 $3$ 为 $1703$ 分。 选手 $1$ 已经在不做任何更多题目的情况下领先所有其他选手的总分。 选手 $2$ 例如可以做第 $4$ 题以使总分达到 $3502$ 分，从而超过所有其他选手的总分。 选手 $3$ 例如也可以做第 $4$ 题以使总分达到 $3703$ 分，从而超过所有其他选手的总分。

标签: AtCoder|abc323C

来源

AtCoder|abc323C