TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3669
  • 問題
  • P3669农田除草
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    农夫约翰要定期给农田除草。 

    农田可以看做2D网格状,约翰一开始位于一个空格子上,接下来有N步操作,比如其中一步操作是"W 10",表示约翰要往西边(左边)沿直线除去10个格子的草,每除一个格子耗费1秒。 

    因为约翰的除草速度很慢,当还没结束除草工作时,之前被除去草的一些格子的草可能又长了出来。长草时间花费x秒,也就是说如果一个格子的草在第t秒被除去,那么在第t+x秒又长了回来。 

    约翰可能需要重复对某些格子进行除草,约翰很是不爽,他为自己制定了一个原则:绝不重复进入一个已经被除去草的格子,除非该格子的草又长了回来。也就是说,当他从新进了某个格子,那么上一次他进该格子的时间应该是在x秒之前。 

    请你帮忙计算,为满足约翰的原则,x的值最大是多少才行。

    入力形式

    第一行,一个整数N(1≤N≤100)表示由N个除草操作。 
    接下来N行,每行由一个字母和整数构成,表示一个操作。其中字母N表示往北(往上),E表示往东(往右),S表示往南(往下),W表示往西(左边),数字表示沿该方向除草的格子数(1<=数字<=10)。

    出力形式

    一行,一个整数,表示x的最大值。如果约翰不可能重复进入任何格子,输出-1 

    サンプル入力 1

    6
    N 10
    E 2
    S 3
    W 4
    S 5
    E 8

    サンプル出力 1

    10

    サンプル入力 2

    14
    N 2
    N 2
    N 2
    N 2
    N 2
    E 3
    N 3
    W 3
    S 3
    S 2
    S 2
    S 2
    S 2
    S 2

    サンプル出力 2

    12

    ヒント

    样例1说明: 
    约翰在第17秒重复进入了第7秒进入过的格子,时间间隔为10。 
    约翰在第26秒重复进入了第2秒进入过的格子,时间间隔为24。 
    上述两者中小者才能满足要求,所以答案为10


    ソース  usaco 2016 January Contest Bronze Boss He 翻译