← 返回题目列表

AtCoder · abc323_c

E. 世界巡回赛总决赛

中文机器翻译题面 查看原题

分数: 250 点

问题陈述

编程大赛世界巡回赛总决赛正在进行中, N 选手正在参赛,比赛时间已过一半。 有 M 本次比赛的问题及得分 问题的 A_i 问题的 i 是的倍数 100 之间 500 和 2500,包括在内。

对于每个 i = 1, \ldots, N,给你一个字符串 S_i 表示玩家遇到哪些问题 i 已经解决了。 S_i 是一个长度为的字符串 M 组成 o 和 x,其中 j- 第一个字符 S_i is o 如果玩家 i 已经解决了问题 j,和 x 如果他们还没有解决这个问题。 到这里,还没有一个玩家能够解决所有的问题。

玩家总分 i 的计算方式为他们已解决问题的分数之和,加上 奖励分数 of 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 是一个长度为的字符串 M 组成 o 和 x.
  • 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

比赛时间过半时选手的总成绩为 2001 玩家积分 1, 1502 玩家积分 2,和 1703 玩家积分 3.

玩家 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