← 返回题目列表

AtCoder · joisc2016_c

C. 纸牌

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

ソリティア - 原题 PDF 第 1 页
原题PDF第9页
ソリティア - 原题 PDF 第 2 页
原题PDF第10页
ソリティア - 原题 PDF 第 3 页
原题PDF第11页
ソリティア - 原题 PDF 第 4 页
原始PDF第12号
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                          Contest Day 1 – Solitaire


                      ソリティア(Solitaire)



  JOI 君は,縦に3 マス,横にN マスの方眼状のボードと,いくつかのコマを使ってゲームをしている.
ゲームの初期状態において,1 個以上のマスにはコマが置かれており,また,1 個以上のマスにはコマが置
かれていない.
 このゲームの目的は,コマの置かれていないマスにコマを1 個ずつ置いていくことで,ボード上のすべ
てのマスにコマが置かれた状態にすることである.ただし,あるマスにコマを置ける条件は,以下のいず
れかが満たされることである.

   • そのマスの一つ上のマスと一つ下のマスの両方にコマが置かれている.

   • そのマスの一つ左のマスと一つ右のマスの両方にコマが置かれている.

  JOI 君はゲームの初期状態から始めて,目的を達成するまでにコマを置いていく順番が全部で何通りあ
るのかが気になった.ただしこの値は非常に大きくなることがある.
 あなたの課題は,JOI 君の代わりに,ゲームの初期状態から目的を達成するまでにコマを置いていく順
番の個数を1 000 000 007 で割った余りを求めることである.


課題

 ゲームの初期状態が与えられたとき,目的を達成するまでにコマを置いていく順番の個数を1 000 000 007
で割った余りを求めるプログラムを作成せよ.


入力

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

   • 1 行目には,整数N が書かれている.これは,ゲームで使うボードの大きさが,縦に3 マス,横に
    N マスであることを表す.

   • 続く3 行のそれぞれには,N 文字からなる文字列が書かれている.各文字は‘o’ もしくは‘x’ である.
   この3 行のうちのi 行目(1 ≦i ≦3) の左からj 文字目(1 ≦j ≦N) は,ボードの上からi 行目,左か
   らj 列目のマスの初期状態を表す.この文字が‘o’ のときは,ゲームの初期状態においてそのマスに
   コマが置かれていることを表す.また,‘x’ のときは,ゲームの初期状態においてそのマスにコマが
   置かれていないことを表す.


出力

 標準出力に,目的を達成するまでにコマを置いていく順番の個数を1 000 000 007 で割った余りを1 行で
出力せよ.



                     ソリティア– 1 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                          Contest Day 1 – Solitaire


制限

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

   • 1 ≦N ≦2 000.


小課題

小課題1 [10 点]

 以下の条件を満たす.

   • ゲームの初期状態において,コマの置かれていないマスの個数は16 個以下である.

   • N ≦30.


小課題2 [12 点]

   • ゲームの初期状態において,コマの置かれていない各マスについて,そのマスに上下左右に隣り合う
   マスのうちコマの置かれていないマスの個数が2 個以下である.


小課題3 [20 点]

 以下の条件を満たす.

   • ゲームの初期状態において,コマの置かれていないマスが縦に3 個連続して並ぶことはない.

   • N ≦30.


小課題4 [38 点]

   • N ≦300 を満たす.


小課題5 [20 点]

 追加の制約はない.





                     ソリティア– 2 / 4

Japanese Olympiad in Informatics 2015/2016
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                          Contest Day 1 – Solitaire


入出力例

  入力例1           出力例1
   3                        14
   oxo
   xxo
   oxo

 この入力例では,ゲームの初期状態は以下の通りである(コマの置かれたマスを○で表す).

                     ○   ○

                         ○

                     ○   ○

 次のいずれかの表に従ってコマを置いていくことで,目的を達成することができる(番号はコマを置い
ていく順番を表す).

      ○ 1 ○  ○ 1 ○  ○ 1 ○  ○ 1 ○  ○ 2 ○

      2 3 ○  2 4 ○  3 4 ○  4 3 ○  1 3 ○

      ○ 4 ○  ○ 3 ○  ○ 2 ○  ○ 2 ○  ○ 4 ○


      ○ 2 ○  ○ 3 ○  ○ 4 ○  ○ 3 ○  ○ 4 ○

      1 4 ○  1 2 ○  1 2 ○  1 4 ○  1 3 ○

      ○ 3 ○  ○ 4 ○  ○ 3 ○  ○ 2 ○  ○ 2 ○


      ○ 2 ○  ○ 2 ○  ○ 3 ○  ○ 4 ○

      3 4 ○  4 3 ○  2 4 ○  2 3 ○

      ○ 1 ○  ○ 1 ○  ○ 1 ○  ○ 1 ○

 目的を達成する順番はこれらの14 通りのみであるので,14 を出力する.



  入力例2           出力例2
   10                       149022720
   ooxooxoxoo
   xooxxxoxxx
   oxoxoooooo

 入力例2 はすべての小課題の制約を満たす.





                     ソリティア– 3 / 4

Japanese Olympiad in Informatics 2015/2016
                                                         Spring Training Camp/Qualifying Trial
                                             March 19–25, 2016, Komaba/Yoyogi, Tokyo

                                                                        Contest Day 1 – Solitaire



 入力例3           出力例3
 10                       0
 ooxoxxoxoo
 oxxxxxoxxx
 oxooxoxoxo

ゲームの初期状態によっては,目的を達成できないこともある.



 入力例4           出力例4
 20                       228518545
 oxooxoxooxoxooxoxoxo
 oxxxoxoxxxooxxxxxoox
 oxooxoxooxooxooxoxoo





                    ソリティア– 4 / 4