← 返回题目列表

AtCoder · joisc2018_i

I. 安全门

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

防犯ゲート (Security Gate) - 原题 PDF 第 1 页
原题PDF第1页
防犯ゲート (Security Gate) - 原题 PDF 第 2 页
原题PDF第2页
防犯ゲート (Security Gate) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                     Contest Day 3 – Security Gate


                  防犯ゲート(Security Gate)



 あなたはJust Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明(just odd
inventions)」をすることである.ここでは略してJOI 社と呼ぶ.
  JOI 社は機密情報の流出を防ぐべく,出入り口に防犯ゲートを設置している.会社に出入りする際は必
ずこの防犯ゲートを通る必要がある.また,一度に2 人以上の人がこのゲートを通ることはできない.
 この防犯ゲートは,人がゲートを通るたびに,会社に人が入った,または出た,という情報を記録して
いる.今,JOI 社の社員であるIOI 君の前には,ある1 日の防犯ゲートの記録がある.この記録は文字列
S で表される.S のi 文字目が‘(’ であるときは,i 番目に人がゲートを通った際,その人が会社に入った
ことを意味する.また,S のi 文字目が‘)’ であるときは,i 番目に人がゲートを通った際,その人が会社
から出たことを意味する.またIOI 君は,この日の始まりと終わりには,JOI 社内に誰もいなかったこと
を知っている.ここで,‘(’ と‘)’ のみからなる文字列であっても,記録としてはありえないものがある点
に注意せよ.例えば,())( や(() という記録は,JOI 社内にいる人数が負になったり,一日の終わりにま
だJOI 社内に人がいることになったりするので,ありえない.
  IOI 君が記録を確認した次の瞬間,JOI 社内に蔓延しているコンピュータウィルスによって,文字列S が
変化してしまった.IOI 君は調査の結果,文字列S が次のような過程で変化したと予想した.

   • まず,S のある連続する区間の文字が,すべて次のように変化した.その区間に含まれる文字全てに
   ついて,その文字が‘(’ ならば‘)’ に変化し,‘)’ ならば‘(’ に変化した.変化後の文字列をS ′ とす
   る.なお,変化した区間の長さが0 であること,つまり,S = S ′ であることもありうる.

   • 次に,S ′ の0 個以上の文字が‘x’ に変化した.変化後の文字列をS ′′ とする.

  IOI 君はS の情報を覚えていないため,S ′′ からS を復元しようと考えている.そのためにIOI 君はま
ず,S ′ としてあり得るものが何通りあるかを調べることにした.(IOI 君が何通りあるかを調べるのは,S
ではなくS ′ であることに注意せよ.)


課題

 文字列S ′′ が与えられたとき,S ′ としてあり得るものの個数を,1 000 000 007 で割った余りを求めよ.


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N が書かれている.これは,変化後の文字列S ′′ の長さがN であることを表す.

   • 2 行目には長さN の文字列S ′′ が書かれている.各文字は‘(’,‘)’,もしくは‘x’ のいずれかである.
   これは,変化後の文字列がS ′′ であることを表す.




                     防犯ゲート– 1 / 3

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                     Contest Day 3 – Security Gate


出力

  S ′ としてあり得るものの個数を,1 000 000 007 で割った余りを出力せよ.もし,S ′ としてあり得るもの
がない場合は,0 を出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦N ≦300.


小課題

 この課題では小課題は全部で5 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題1 [4 点]

   • N ≦100.

   • S ′′ 中の‘x’ の個数は4 個以下である.


小課題2 [8 点]

   • N ≦100.

   • S ′′ 中の‘x’ の個数は12 個以下である.


小課題3 [18 点]

   • N ≦100.

   • S ′′ 中の‘x’ の個数は20 個以下である.


小課題4 [43 点]

   • N ≦100.


小課題5 [27 点]

 追加の制限はない.





                     防犯ゲート– 2 / 3

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                     Contest Day 3 – Security Gate


入出力例

  入力例1        出力例1
   4                    3
   x))x

 入力例1 では,S ′ = )))( とすると,S としてありうるものが存在しないため,不適である.
 以下の3 通りの文字列は,S ′ である可能性がある.

   • S ′ = ())(.例えば,S = ()() とすればよい.

   • S ′ = ())).例えば,S = ()() とすればよい.

   • S ′ = )))).例えば,S = (()) とすればよい.

  S ′ としてあり得るものはこれらのみなので,3 を出力する.


  入力例2              出力例2
   10                             45
   xx(xx()x(x



  入力例3              出力例3
   5                              0
   x))x(



  入力例4              出力例4
   10                             684
   xxxxxxxxxx





                     防犯ゲート– 3 / 3