C - World Tour Finals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

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 が全ての問題を解くことで、他のプレイヤー全員の現在の総合得点を上回ることができることが証明できます。 このことから、答えは常に定義されることに注意してください。

制約

  • 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 が一個以上含まれる
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

N 行出力せよ。 i 行目にはプレイヤー i に関する質問の答えを出力せよ。

入力例 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

出力例 1

0
1
1

競技時間の半分の経過時の各プレイヤーの総合得点は、プレイヤー 1 が 2001 点、プレイヤー 2 が 1502 点、プレイヤー 3 が 1703 点です。

プレイヤー 1 は 1 問も解かずとも、他のプレイヤー全員の総合得点を上回っています。

プレイヤー 2 は、例えば問題 4 を解けば総合得点が 3502 点となり、他のプレイヤー全員の総合得点を上回ります。

プレイヤー 3 も、例えば問題 4 を解けば総合得点が 3703 点となり、他のプレイヤー全員の総合得点を上回ります。

入力例 2

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

出力例 2

1
1
1
1
0

入力例 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

Score : 250 points

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