レンガ敷き詰め問題

概要

街の歩道や広場はレンガ敷きになっているところが多い. その中には,レンガに微妙な色の違いを持たせたり,置き方に工夫をすることで, 模様を浮かび上がらせているものもある.

そういう模様を見ていると,数学者は「広場をレンガで敷き詰める方法は何通り あるのだろうか」と自然に考えてしまう.

歩道については予選で扱ったので,本選では広場を扱う. 広場は長方形であるが*1,広場の中には建物や柱などの障害物も存在する. また,障害物は広場の隅や端にあるかもしれない. そのような広場の地面をレンガで敷き詰める方法の総数はいくつだろうか?

定式化

つまり,これは障害物を中に含む長方形を縦2 m,横1 mの長方形で敷き詰める方法の総数を計算する問題である. (広場に対応する) 敷き詰められる側の長方形の大きさは縦横ともに50 m以下であるとする. 下の例では,縦13 m,横14 mである長方形の中に,灰色で示された障害物がある. 障害物を除く部分が広場であり,そこをレンガで敷き詰める 方法が1つ示してある.

rei1.png

問題の入力は広場と整数kである.そのときの出力は広場をレンガで敷き詰める方法の総数をkで割った余りでなければならない.

入力形式

問題数は100000 (十万) であり,それらが100個のファイルに格納されている. 各ファイルに格納されている問題数は1000であり,1つの問題が複数のファイルに またがって格納されることはない.

各ファイルには次の形式で記述された問題が並んでいる. 各問題の記述は例えば次のようになっている.

21348 13 14 7
..............
...**.........
.....**.......
.....**.......
..............
....*..*...***
.............*
..............
.........*....
.........*....
*....*****....
**....*..*....
**............

最初の行には4つの整数が並び,左から順に問題番号 (0以上99999以下の整数), 広場の縦の長さ,広場の横の長さ,整数kを表す. それらは空白1つを間に挟んでいる. 広場の縦の長さをm,横の長さをnとする.

その後にm行続き,それは広場のどこに障害物があるのかを 示している. 各行はn個の文字から構成されており, 障害物が置かれている箇所は「*」, 障害物が置かれていない箇所は「.」で示されている. 障害物が全く置かれていない可能性もある.

詳細説明

  • 本選プログラム作成は26日 (木) の12時30分で終了する.
  • 26日 (木) の午後に,各チームはスパコンを45分間占有して, 問題を解く (最終トライアル) . 問題ファイルが置いてあるディレクトリはその際に連絡する. この45分が終わるまでに,入出力を含めて解答に関わるすべてを終了 させなくてはならない. (スパコンの使用法,利用できるノード数,コア数については配布される「プログラミング・ガイド」を参照.)
  • 問題ファイルが置いてあるディレクトリには101個のファイルが置かれている. その中のprob00.inからprob99.inが問題ファイルである. それ以外にstatistics.txtが置いてある.これは問題に関する情報を記述した ファイルである.複数の問題の内容が同一である可能性もある.
  • 解答は各チームのホームディレクトリへ単一のファイルとして置く. ファイル名は「チーム名.out」とする. 出力 (解答の書き込み) は必ず,提供ツールの出力関数によってルートプロセス (ランク0) から行わなければならない. 入力 (問題ファイルの読み込み) は必ずルートプロセス (ランク0) から行わなければならない.
  • すべての問題に解答する必要はなく,解答順も任意でよい.ただし,1つの問題に複数回解答した場合は,解答時刻の遅い方 (書き込まれた順が遅い方) を優先する.
  • 各問題ファイルにおいて,広場の縦の長さ,横の長さを表すmとnはともに1以上50以下の整数である.そして,kは2以上32767以下の整数である. (注意:「○○以上○○以下の整数」というときは,○○もその整数に含まれる.)
  • 入力ファイルにあるどの問題に対しても,敷き詰める方法が1つ以上存在することは保証されている.
  • 上記の内容に変更がある場合は,「内部向けノート」のページに掲載する.

審査基準

  • 解答終了時に正しい出力を与えた問題数のより多いチームが勝利する.
  • 正しい出力を与えた問題数が同じ場合には,正しい出力を与えた最後の問題に解答した時間のより短いチームが勝利する.(誤答の時間は考慮しない.)
  • 上記の内容に変更がある場合は,「内部向けノート」のページに掲載する.

*1 「広場」の英語はsquareであるが,ここでの広場において,縦と横の長さが等しい必要はない.

添付ファイル: filehonsen.pdf 6件 [詳細] filerei1.png 7件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2017-09-25 (月) 16:19:29 (22d)