問題一覧 > 通常問題

No.303 割れません

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : LayCurseLayCurse
2 ProblemId : 831 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:50:26

問題文

新婚の高橋くんは新築の一戸建てにある家庭菜園を囲む長さ $L$ の塀を作りたいと思っています.
高橋くんの住む街では,全ての正整数 $k$ について長さ $k$ のブロックが $k$ 円で売られています.
高橋くんは,このブロックを好きな数だけ買って,繋げて長さ $L$ の塀にするつもりです.
買ったブロックは(長さを分割する方向に)自由に切っても構いませんが,$1$ 回切るたびにコストが $1$ 円だけかかります.

ただし,新婚の高橋くんは $2$ で割れることを忌み嫌います.
よって,偶数の長さのブロックは買わないこととしました.
また,長さ $L$ の塀ができた時に,ちょうど半分の,端から長さ $L/2$ の部分がブロックの継ぎ目になっていてはいけません.

さて,このような条件を満たすように塀を作るときの最小コストを求めてください.
むっ,簡単すぎてつまらないという声が聞こえてきたので,最小コストを達成するような塀の作り方のパターンの数も求めてください.
$2$ つの塀の作り方が違うとは,構成するブロックの数が違う,または,ある $i$ が存在して,左から $i$ 個目のブロックの長さが違うかのどちらかを満たせば違う作り方とみなします.
また,どうやっても,作るのが不可能ならば,最小コストとして $\verb|INF|$,パターンの数として $\verb|0|$ を,
最小コストを満たすような作り方が無限に存在する場合は,パターンの数として $\verb|INF|$ を出力してください.

入力

$L$

$1 \leq L \leq 3000000 = 3 \times 10^6$:$L$ は整数

出力

$1$ 行目に最小コストを,$2$ 行目にパターンの数を出力してください.

サンプル

サンプル1
入力
5
出力
5
5

四角 $1$ 個の長さは $1$,同じ色の連続は同じブロックとして,以下の $5$ 通りの作り方がコスト $5$ 円で作ることができます.

□□□□□  □□□■□  □■□□□  □■□■□  □■■■□

ちなみに,□□■■□は長さ $2$ のブロックを買えないために,コスト $5$ 円では作ることができません.
$5$ ばっかりで気持ちが良いですね.

サンプル2
入力
1
出力
1
1

$1$ ばっかりで気持ちが良いですね.

サンプル3
入力
10
出力
10
30

$10$ 円では,以下の $30$ 通りの塀を作ることができます.

□□□□□□□□□■  □□□□□□□■□■  □□□□□□□■■■  □□□■□□□□□■  □□□■□□□■□■  □□□■□□□■■■
□□□■■■□□□■  □□□■■■□■□■  □□□■■■□■■■  □□□■■■■■□■  □□□■■■■■■■  □■□□□□□□□■
□■□□□□□■□■  □■□□□□□■■■  □■□■□□□□□■  □■□■□□□■□■  □■□■□□□■■■  □■□■■■□□□■
□■□■■■□■□■  □■□■■■□■■■  □■□■■■■■□■  □■□■■■■■■■  □■■■□□□□□■  □■■■□□□■□■
□■■■□□□■■■  □■■■■■□□□■  □■■■■■□■□■  □■■■■■□■■■  □■■■■■■■□■  □■■■■■■■■■

ちなみに,□□□□□■■■■■は,端からちょうど $L/2=5$ だけ離れた部分が継ぎ目になっているので不許可です.
$10$ ばっかりじゃないけど,$30$ は $10$ で割れるので,気持ちが良いですね.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。