Score : $250$ points

问题描述

正在进行一场编程比赛——世界巡回赛总决赛，有 $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$ 通过解决所有剩余问题一定能超过其他所有选手当前的总分，因此答案总是存在的。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The programming contest World Tour Finals is underway, where $N$ players are participating, and half of the competition time has passed. There are $M$ problems in this contest, and the score $A_i$ of problem $i$ is a multiple of $100$ between $500$ and $2500$, inclusive.

For each $i = 1, \ldots, N$, you are given a string $S_i$ that indicates which problems player $i$ has already solved. $S_i$ is a string of length $M$ consisting of o and x, where the $j$-th character of $S_i$ is o if player $i$ has already solved problem $j$, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player $i$ is calculated as the sum of the scores of the problems they have solved, plus a bonus score of $i$ points.
For each $i = 1, \ldots, N$, answer the following question.

• At least how many of the problems that player $i$ has not yet solved must player $i$ solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player $i$ can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• $2\leq N\leq 100$
• $1\leq M\leq 100$
• $500\leq A_i\leq 2500$
• $A_i$ is a multiple of $100$.
• $S_i$ is a string of length $M$ consisting of o and x.
• $S_i$ contains at least one x.
• All numeric values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_M$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print $N$ lines. The $i$-th line should contain the answer to the question for player $i$.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are $2001$ points for player $1$, $1502$ points for player $2$, and $1703$ points for player $3$.

Player $1$ is already ahead of all other players' total scores without solving any more problems.

Player $2$ can, for example, solve problem $4$ to have a total score of $3502$ points, which would exceed all other players' total scores.

Player $3$ can also, for example, solve problem $4$ to have a total score of $3703$ points, which would exceed all other players' total scores.

Sample Input 2

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

Sample Output 2

1
1
1
1
0

Sample Input 3

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

Sample Output 3

7
6
5
4
3
2
0

update @ 2024/3/10 01:44:25