Supercomputing Contest 2010/予選・認定問題

SuperCon 2010 予選問題および認定問題 †

• 印刷用PDF版
• 予選・認定問題Ｑ＆Ａ

問 A (スーパーコン3級認定問題 2010年度版) †

街を歩いてると，レンガ敷きの歩道が見せる模様は規則的であるにも関わらず，なぜか不規則さを感じさせます．では，レンガを歩道に敷き詰める方法は何通りあるのでしょうか．それを考えてみましょう．

いきなり歩道にレンガを敷き詰めて数を計算すると通行のじゃまになるので，机の上に置ける模型で何通りあるのか考えることにしました．まっすぐな歩道を長方形だと思うことにします．縦が 2 cm，横が n cmである次のような長方形1つを考えます．

レンガは縦が 2 cm，横が 1 cm である長方形であるとします．

実際に模型を作って確かめると，n = 7 のときに敷き詰め方はちょうど 21 通りあることが分かりました．しかし，これでは n が大きくなったとき，敷き詰め方の数を模型で計算することは大きな苦労になります．そのため，それを計算するプログラムを作って，何通りあるのかすぐに分かるようにしましょう．

つまり，縦が 2 cm，横が 1 cm である長方形を隙間なく敷き詰める方法の総数を計算するプログラムを作成して下さい．ただし，その数は大きいので，その数を k で割った余りを出力するようにして下さい．入力として与えられるのは n と k です．

上の図では，n = 7 であり，敷き詰め方はちょうど 21 通りあります．少し例を示すと，次の表のようになります．

また，n = 31 のときには敷き詰め方の数が 2178309 になります．

このように n が大きくなると敷き詰め方の数も大きな値になるので，敷き詰め方の数を k で割った余りを出力するようにします．例えば，n = 7 の場合は，敷き詰め方が 21 通りなので，出力すべき値は，k = 3 ならば 0 で，k = 4 ならば 1 で，k = 9 ならば 3 になります．

• すべての問いに共通する注意事項
• 問 A, B についての詳細説明
• 問 A 用雛形プログラム (内容は問 B 用雛形プログラムと同じです．)

ヒント †

この問題 (と後に続く問題 B，C) の難しさの 1 つは敷き詰め方の総数がとても大きくなってしまうことです．そのため，敷き詰め方を1つずつ試す方法では計算時間が膨大になってしまいます．あまり計算時間がかからない方法を考えることが重要です．

問 B (スーパーコン2級認定問題 2010年度版) †

縦が 3 cm，横が n cm である長方形 1 つの中に，縦が 2 cm，横が 1 cm である長方形を隙間なく敷き詰める方法の総数を計算するプログラムを作成して下さい．ただし，その数は大きいので，その数を k で割った余りを出力するようにして下さい．入力として与えられるのは n と k です．

この例では，n = 6 であり，敷き詰め方はちょうど 41 通りあります．

• すべての問いに共通する注意事項
• 問 A, B についての詳細説明
• 問 B 用雛形プログラム (内容は問 A 用雛形プログラムと同じです．)

問 C (スーパーコン 1 級認定問題 2010 年度版 兼 スーパーコン 2010 予選問題) †

縦が 3 cm，横が m cm である長方形 1 つと縦が 2 cm，横が n cm である長方形 1 つを，底辺が一直線上にあるように横に並べた図形の中に，縦が 2 cm，横が 1 cm である長方形を隙間なく敷き詰める方法の総数を計算するプログラムを作成して下さい．ただし，その数は大きいので，その数を k で割った余りを出力するようにして下さい．入力として与えられるのは m と n と k です．

この例では，m = 4, n = 3 であり，敷き詰め方はちょうど 41 通りあります．

• すべての問いに共通する注意事項
• 問 C についての詳細説明
• 問 C 用雛形プログラム

注意 †

すべての問いに共通する事項 †

1. 作成するプログラム
   1. プログラムは入出力の部分を規定した雛形プログラムをもとに，その一部を修正する形で作って下さい． 作成の際には，「変更・削除しないこと」とコメントされている行は変更・削除しないようにして下さい．したがって，ここで指定された入力，出力以外のものを期待したプログラムは審査対象から除外されます．その他は適宜変更や追加して構いません．また，関数等を宣言して使用しても構いません．

• 問 A 用雛形プログラム
• 問 B 用雛形プログラム
• 問 C 用雛形プログラム

問 A 用雛形プログラムと問 B 用雛形プログラムの内容は同じです．

1. プログラムはヘッダファイル等を使わずに1つのファイルとしてまとめたものを提出して下さい．詳しくは「認定証応募方法」および「予選応募方法」のページをご覧ください．
2. プログラムは C 言語で記述して下さい．詳細は以下の通りです．
   • プログラムは ANSI C に準拠する C 言語で記述して下さい．例えば，Windows のVisual C++ などで開発をするとき，Windows 特有の関数を使わないように注意して下さい．
   • int は 32 ビット，long は 64 ビットを仮定します．
   • Linux gcc ver 3.4.6を使用してコンパイルし，Linux 上で実行します．
   • エンディアンの違いによるトラブルに対しては対処しません．

1. 審査方法
   1. スーパーコン認定では，応募プログラムをコンパイルし，複数のテストデータから構成される 1 つの入力ファイルに対して実行し，すべてのテストデータに正確な答えを出している場合に合格とします．
   2. 各入力ファイルに対して，実行時間が 10 分を越えた場合には失格とします．
   3. 審査環境におけるメモリはおよそ 2 ギガバイトです．
   4. スーパーコン 2010 予選については，複数の審査用入力ファイルに対して実行し，すべてに正確な答えを出したプログラムの中から，実測した合計計算時間の順で，東西それぞれ上位 10 チームを本選出場候補チームとして選びます．ただし，1 校からは最大 2 チームしか本選出場できません．本選出場候補チームには，同時にスーパーコン 1 級も授与します．

詳細説明 †

問 A, B についての詳細説明 †

入力は以下のような形式で与えられます．

n1 k1
n2 k2
...
ni ki
...
nx kx

1 つの行が 1 つのテストデータに対応します．各行にある ni と ki が問題文の n と k に対応します．次の条件を入力は必ず満たしています．

• 各 ni は 1 以上 32767 以下の整数．
• 各 ki は 2 以上 32767 以下の整数．
• 同じテストデータが複数回現れるかもしれません．
• テストデータの数 (入力ファイルの行数) は 600000 (六十万) です．

出力では，各テストデータに対して出力すべき数字を印字し，印字後は改行して下さい．出力の順は入力の順と同一でなければなりません．

問 C についての詳細説明 †

入力は以下のような形式で与えられます．

m1 n1 k1
m2 n2 k2
...
mi ni ki
...
mx nx kx

1 つの行が 1 つのテストデータに対応します．各行にある mi，ni，ki が問題文 m，n，k に対応します．第 1 級認定問題およびスーパーコン 2010 予選問題において，入力は次の条件を必ず満たしています．

• 各 mi と ni は 1 以上 32767 以下の整数．
• 各 ki は 2 以上 32767 以下の整数．
• 同じテストデータが複数回現れるかもしれません．
• テストデータの数 (入力ファイルの行数) は 600000 (六十万) です．

出力では，各テストデータに対して出力すべき数字を印字し，印字後は改行して下さい．出力の順は入力の順と同一でなければなりません．

改訂履歴 †

• 問Aの記述中，「n = 30」を「n = 31」に訂正． (2010年6月4日)