CodeIQ過去問集28:壊れたパスカルの三角形
本稿はCodeIQで2014年12月8日~2015年1月12日に出題された コード銀行:大きなべき乗の計算 という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
壊れたパスカルの三角形
パスカルの三角形は、上記のように隣り合った数の和を下段に書くことで作ることができます。
【問題】
パスカルの三角形を作るとき、隣り合った数の和を下段に追加していきますが、一か所だけ差を計算してしまっています。 次の図では、4段目・左から3つ目の値が、2 - 1 = 1になっているので、そこから下の部分の数が通常のパスカルの三角形と異なっています。
このような、壊れてしまったパスカルの三角形の一番下の段が入力として与えられたとき、“何段目”の、“左から何番目”の値を求める際に差を計算してしまったのかを特定するプログラムを書いてください。
※「差」は、『大きい方の値から小さい方の値を引く』と考えてください。
【入力・出力】
テキストファイルの1行目にパスカルの三角形の段数k、2行目にk個の整数値が半角スペース区切りで書かれたものを入力ファイルとします。k個の整数値は、壊れたパスカルの三角形のk段目を表しています。これらの値を読み込み、間違えた計算方法で計算してしまった部分(差を計算した部分)を特定し、その段数と左から数えて何番目に当たるかを半角スペース区切りで出力してください。
入力例
7 1 6 13 14 9 4 1
出力例
4 3
【解答方法】
broken_pascal.zipをダウンロードしてください。 中には以下のファイルが含まれています。
- sample.in.txt, sample.out.txt
例で示したデータと、その解答です。
- case01.in.txt, case02.in.txt, case03.in.txt, case04.in.txt, case05.in.txt
これを入力として、正しい実行結果が得られるプログラムを書いてください。
(解答・解説は後日)