![[PukiWiki]](image/pukiwiki.png "[PukiWiki]") |
Supercomputing Contest 2010/本選問題 |
|
Top / Supercomputing Contest 2010 / 本選問題
Table of Contents
各年TOP
ARCHIVELINK
Counter: 5749,
today: 3,
yesterday: 3
最新の20件2023-09-13
2023-09-06
2023-09-01
2023-08-28
2023-08-01
2023-06-29
2023-06-12
2023-06-01
2023-05-31
2023-05-30
2022-10-05
2022-09-27
2022-08-26
|
レンガ敷き詰め問題 †概要 †街の歩道や広場はレンガ敷きになっているところが多い． その中には，レンガに微妙な色の違いを持たせたり，置き方に工夫をすることで， 模様を浮かび上がらせているものもある． そういう模様を見ていると，数学者は「広場をレンガで敷き詰める方法は何通り あるのだろうか」と自然に考えてしまう． 歩道については予選で扱ったので，本選では広場を扱う． 広場は長方形であるが*1，広場の中には建物や柱などの障害物も存在する． また，障害物は広場の隅や端にあるかもしれない． そのような広場の地面をレンガで敷き詰める方法の総数はいくつだろうか？ 定式化 †つまり，これは障害物を中に含む長方形を縦2 m，横1 mの長方形で敷き詰める方法の総数を計算する問題である． (広場に対応する) 敷き詰められる側の長方形の大きさは縦横ともに50 m以下であるとする． 下の例では，縦13 m，横14 mである長方形の中に，灰色で示された障害物がある． 障害物を除く部分が広場であり，そこをレンガで敷き詰める 方法が1つ示してある．  問題の入力は広場と整数kである．そのときの出力は広場をレンガで敷き詰める方法の総数をkで割った余りでなければならない． 入力形式 †問題数は100000 (十万) であり，それらが100個のファイルに格納されている． 各ファイルに格納されている問題数は1000であり，1つの問題が複数のファイルに またがって格納されることはない． 各ファイルには次の形式で記述された問題が並んでいる． 各問題の記述は例えば次のようになっている． 21348 13 14 7 .............. ...**......... .....**....... .....**....... .............. ....*..*...*** .............* .............. .........*.... .........*.... *....*****.... **....*..*.... **............ 最初の行には4つの整数が並び，左から順に問題番号 (0以上99999以下の整数)， 広場の縦の長さ，広場の横の長さ，整数kを表す． それらは空白1つを間に挟んでいる． 広場の縦の長さをm，横の長さをnとする． その後にm行続き，それは広場のどこに障害物があるのかを 示している． 各行はn個の文字から構成されており， 障害物が置かれている箇所は「*」， 障害物が置かれていない箇所は「.」で示されている． 障害物が全く置かれていない可能性もある． 詳細説明 †
審査基準 †
|
rei1.png