SuperCon 2010 予選問題および認定問題 †問 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 になります.
ヒント †この問題 (と後に続く問題 B,C) の難しさの 1 つは敷き詰め方の総数がとても大きくなってしまうことです.そのため,敷き詰め方を1つずつ試す方法では計算時間が膨大になってしまいます.あまり計算時間がかからない方法を考えることが重要です. 問 B (スーパーコン2級認定問題 2010年度版) †縦が 3 cm,横が n cm である長方形 1 つの中に,縦が 2 cm,横が 1 cm である長方形を隙間なく敷き詰める方法の総数を計算するプログラムを作成して下さい.ただし,その数は大きいので,その数を k で割った余りを出力するようにして下さい.入力として与えられるのは n と k です. この例では,n = 6 であり,敷き詰め方はちょうど 41 通りあります.
問 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 通りあります. 注意 †すべての問いに共通する事項 †
問 A 用雛形プログラムと問 B 用雛形プログラムの内容は同じです.
詳細説明 †問 A, B についての詳細説明 †入力は以下のような形式で与えられます. n1 k1 n2 k2 ... ni ki ... nx kx 1 つの行が 1 つのテストデータに対応します.各行にある ni と ki が問題文の n と k に対応します.次の条件を入力は必ず満たしています.
出力では,各テストデータに対して出力すべき数字を印字し,印字後は改行して下さい.出力の順は入力の順と同一でなければなりません. 問 C についての詳細説明 †入力は以下のような形式で与えられます. m1 n1 k1 m2 n2 k2 ... mi ni ki ... mx nx kx 1 つの行が 1 つのテストデータに対応します.各行にある mi,ni,ki が問題文 m,n,k に対応します.第 1 級認定問題およびスーパーコン 2010 予選問題において,入力は次の条件を必ず満たしています.
出力では,各テストデータに対して出力すべき数字を印字し,印字後は改行して下さい.出力の順は入力の順と同一でなければなりません. 改訂履歴 †
|