← 返回题目列表

AtCoder · icpc2015summer_day4_a

A. 边界在哪里

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

问题陈述

某个星球上有一个岛国JAGAN,国土非常狭长,并向东和西延伸。 据说这个狭长的国家由两个主要文化区组成——东部和西部。东部地区往往具有东方文化特征,西部地区往往具有西方文化特征,但是,当然,这两个文化区域之间的界限并不明确,这一直是一个问题。

您需要使用给定的数据集来估计边界。

更精确的分配规范如下:

  1. JAGAN 被划分为 $n$ 个县,在东西方向上形成一条线。 每个都道府县的编号为 1, 2, ..., $n$ 从西到东.
  2. 每个数据集由 $m$ 个特征组成,其中有 'E'(东)或 'W'(西)每个都道府县。 这些数据表明,每个都道府县从食物、衣服等不同角度都具有东方或西方的特色。
  3. 在估计中,您必须选择实现最小误差的文化边界。 也就是说,你必须最小化 'W在东侧并且 'E在西侧。
  4. 在估计中,您只能从两个都道府县之间的边界中选择文化边界。

有时,所有都道府县都可以被估计为东部或西部文化区。 在这些情况下,为简化起见,您实际上必须考虑将边界放置在第 0 号都道府县和第 1 号都道府县之间,或者在第 $n$ 都道府县和第 $n+1$ 都道府县之间。 当你得到多个最小值时,你必须输出最西(编号最少)的结果。

编写一个程序来解决作业。


输入

每个输入的格式如下:

$n$ $m$
$d_{11}$...$d_{1n}$
...
$d_{m1}$...$d_{mn}$

第一行由两个整数组成 $n$ ($1 \le n \le 10{,}000$), $m$ ($1 \le m \le 100$), 表示分配中的都道府县数量和要素数量。 以下 $m$ 行是作业中给定的数据集。 每行恰好包含 $n$ 个字符。 第 $i$ 行 $d_{ij}$ 中的第 $j$ 个字符是 'E'(东)或 'W'(西), 这表明第$j$个县从第$i$个角度来看具有东部或西部特征。

输出

在一行中打印估计结果。 输出由两个按升序排序的整数组成,表示两个县接触边界。


示例输入 1

2 1
WE

样本输入 1 的输出

1 2

示例输入 2

3 2
WWE
WEE

样本输入 2 的输出

1 2

两个估计“1 2“和”2 3“实现最少 1 个错误。 不受你必须采用最西方估计的限制, 你必须输出“1 2".


示例输入 3

3 1
WWW

样本输入 3 的输出

3 4

在这种情况下,所有都道府县都是西部的。 正如问题陈述中所描述的, 实际上,您必须考虑到第三都道府县和第四都道府县之间的边界。


示例输入 4

3 1
WEW

样本输入 4 的输出

1 2

你不能假设'E的和 'W是分开的。