問題
二島「お前らみとけよー！今日のプロコン全部AC(正解)してやるよ！」
そう言い放ち二島さんは浜工オリジナルプロコンへと取りかかりました。
問題はN問あり、それぞれ1~Nの問題番号が振られています。
そして宣言通り二島さんはN問ある全ての問題をAC(正解)することができました。
今回の浜工オリジナルプロコンはJOIの練習ということもあり、問題に対する出力結果が書いてあるファイルをアップロードする必要があります。
しかし二島さんは浜工オリジナルプロコンのルールをちゃんと読まずに取りかかったため
残り時間わずかで問題に対する出力結果を１つもアップロードしていないことに気づきました。
出力結果をアップロードしていない問題は得点を得ることが出来ません。
二島さんは全ての問題に対する出力結果をアップロードできれば一番いいのですが、もちろんそれが残り時間内に終わる保証はありません。
また、残り時間でいくつの出力結果をアップロードできるかもわかりません。
二島さんは目標をプロコン優勝に切り替え、現在１位の点数M点を超えるように出力結果をアップロードすることにしました。
二島さんは今現在0点で、一つも出力結果をアップロードしていません。
二島さんが優勝する確率をあげるためには、出来る限り効率のよい提出方法で、なおかつその提出方法で二島さんが得る点数が１位の点数M点を超えればいいと言うことに気づいた二島さんは、残り時間で出力結果をアップロードするために、以下の方法を思いつきました。
１．１番目〜N番目の問題の内,問題番号が連続した問題(以降問題群と呼ぶ)、なおかつその問題群の点数の合計がM点を超えるように問題群を作る。
２.このような問題群の作り方が複数有る場合、問題群の中の問題数がより少ない物を選ぶ。
３．２のような問題群の作り方が複数有る場合、問題群の中の問題の内、最も小さい番号が最も小さい問題群を選ぶ。
たとえば、Nが５以上の時、3問目,4問目,5問目を選んだ際、これは問題数3で、最も小さい番号が3の問題群となります。
また、上の条件のとき1問目,2問目,５問目を選んだ際、2問目と５問目は問題番号が連続したとは言えません。すなわち、このような問題群は作ることが出来ません。
また、例え問題番号が連続していても、問題群の問題の点数の合計がMを超えていない場合(つまりMと等しい場合も含む)も、このような問題群は作ることが出来ません。
二島さんはこの方法で出力結果をアップロードした時、何番目から何番目の問題をアップロードしたのかを求めなさい。
補足
この問題はHOJ412 最後の大勝負の制限時間を１秒短くした問題です。
O(N2)では通らないはず(通ったらすごい)
入力
N M p1 p2 . . . pN
1 行目に問題数の整数 N が与えられる。
2 行目に現在１位の人の点数を表す整数 M が与えられる。
3 行目からN行にわたり、i番目の問題の点数を表す整数 pi が与えられる。
出力
二島さんが上記の方法で出力結果をアップロードする問題を選んだ際、a~b問目を選んだとする。このときのaとbを空白区切りで一行に出力せよ。
また、上記の方法で出力結果をアップロードする方法が一つもない場合"NA"と出力せよ。出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- 5≦N≦105
- 1≦M≦108
- 1≦pi≦103
入出力例
入力例1
5 15 2 5 7 3 9
出力例1
3 5
解説
3問目から5問目の出力結果をアップロードした際に得られる点数は7+3+9で19点である。
これは１位の得点、すなわち15点を超えている。そして、問題番号が連続して選ばれている。
ちなみに2問目から4問目をアップロードした際は、得られる点数は5+7+3で15点だが、15点は１位の得点を超えてはいないのでこの提出方法はやってはいけない。
また、3問目と5問目(この２問)を選んだ際、得られる点数は16点なので１位の得点を超えてはいるが、問題番号が連続していないので、この提出方法はやってはいけない。
また、1問目から5問目や、1問目から4問目、2問目から５問目を選んだ際、得られる点数が１位の得点を超え、なおかつ問題番号が連続しているのですが、これらの提出方法は問題数が4や5と、3問目から5問目を提出する方法よりも多くの問題数がかかってしまうので、これらの提出方法はやらない。
よって、3問目から5問目を二島さんはアップロードするので、出力は3 5となる。
入力例2
5 9 5 5 5 5 5
出力例2
1 2
解説
仮に問題数も同じで条件を満たしている提出方法が複数有る場合、最も小さい番号が最も小さい提出方法を選ぶ。
今回は1問目から2問目、2問目から3問目、3問目から4問目、4問目から5問目を選ぶ方法が、問題数２なおかつ条件を満たす提出方法なのだが
1問目から2問目の中で最も小さい問題番号は1
2問目から3問目の中で最も小さい問題番号は2
3問目から4問目の中で最も小さい問題番号は3
4問目から5問目の中で最も小さい問題番号は4である。
この中で最も小さい問題番号が最も小さい提出方法は1問目から2問目を提出する方法なので、出力は1 2となる。
入力例1
5 15 1 2 1 4 6
出力例1
NA
解説
今回のコンテストでは条件を満たす提出方法が存在しない。よって出力は"NA"となる。