[ABC323C] World Tour Finals

题面翻译

有 $N$ 名选手和 $M$ 个问题，每个问题的分数范围在 $500$ 到 $2500$ 之间，是 $100$ 的倍数。每个选手都有一个表示已解决问题的字符串 $S$, 其中 $o$ 表示已解决，$x$ 表示未解决。每个选手的总分数是已解决问题的分数之和再加上他的编号。

问题是：对于每个选手 $i$ ，至少需要再解决多少尚未解决的问题，才能超过其他选手？

保证没有选手解决了所有 $M$ 道题，所以可以证明问题一定有解。

题目描述

$N$ 人のプレイヤーが参加するプログラミングコンテスト World Tour Finals が行われており、競技時間の半分が過ぎました。 このコンテストでは $M$ 問の問題が出題されており、問題 $i$ の点数 $A_i$ は $500$ 以上 $2500$ 以下の $100$ の倍数です。

各 $i\ =\ 1,\ \ldots,\ N$ について、プレイヤー $i$ がどの問題を既に解いたかを表す文字列 $S_i$ が与えられます。 $S_i$ は o, x からなる長さ $M$ の文字列で、$S_i$ の $j$ 文字目が o のときプレイヤー $i$ は問題 $j$ を既に解いており、x のときまだ解いていません。 ただし、どのプレイヤーもまだ全ての問題を解いてはいません。

プレイヤー $i$ の総合得点は、解いた問題の点数の合計に、ボーナス点 $i$ 点を加えた点数として計算されます。 さて、各 $i\ =\ 1,\ \ldots,\ N$ について以下の質問に答えてください。

• プレイヤー $i$ がまだ解いていない問題を少なくとも何問解くことで、プレイヤー $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 が一個以上含まれる
• 入力される数値は全て整数

Sample Explanation 1

競技時間の半分の経過時の各プレイヤーの総合得点は、プレイヤー $1$ が $2001$ 点、プレイヤー $2$ が $1502$ 点、プレイヤー $3$ が $1703$ 点です。 プレイヤー $1$ は $1$ 問も解かずとも、他のプレイヤー全員の総合得点を上回っています。 プレイヤー $2$ は、例えば問題 $4$ を解けば総合得点が $3502$ 点となり、他のプレイヤー全員の総合得点を上回ります。 プレイヤー $3$ も、例えば問題 $4$ を解けば総合得点が $3703$ 点となり、他のプレイヤー全員の総合得点を上回ります。