1. paizaラーニングトップ
  2. レベルアップ問題集
  3. Aランクレベルアップメニュー(言語選択)
  4. 問題一覧 PHP編
  5. 区間の積

Aランクレベルアップメニューのアイコン
区間の積 (paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

数列 A についての情報と、整数 K が与えられます。
次の条件を満たす A の部分列の最短の長さを答えてください。

・ 数列に含まれる全ての要素の積が K 以上である。

なお、数列の部分列とは、数列の連続した 1 つ以上の要素を取り出して作ることができる数列のことです。

入力される値

N K            
A_1 A_2 ... A_N


・ 1 行目には、数列 A の要素数 N と、条件に使う整数 K が与えられます。
・ 2 行目には、数列 A の各要素 A_1, A_2 ... A_N が与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

1 行の出力

・ 条件を満たす A の部分列の最短の長さ l を 1 行で出力してください。

l

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N ≦ 10 ^ 5
・ 1 ≦ K ≦ 10 ^ 10
・ A_i は、0, 1, 2のいずれか

入力例1

5 1
1 1 1 1 1

出力例1

1

入力例2

6 16
2 0 2 2 2 2

出力例2

4

問題一覧へ戻る

ページの先頭へ戻る