問題其の弐
第３問 浜名湖鰻と見習い料理人
浜名湖は鰻がとれることで有名で、浜松には数多くの鰻を料理する店があります。
そんな浜松で育ったウナギー・パイパーイパーイさんはついに自分の店を持つことになりました。
早速とれたての鰻をさばいて蒲焼きにしようとしたのですが、ウナギーさんは鰻をさばく技術がまだありません。
鰻を切る場所さえ決めてしまえばその位置に寸分の狂いもなく包丁を入れることは出来るのですが、
その鰻を切る場所を決めるのが苦手なウナギーさんはどうしても長さがバラバラな切り方をしてしまいます。
そのため、あるお客さんの鰻の蒲焼きが小さかったり、あるお客さんの鰻の蒲焼きがおおきすぎたりで不平等になってしまいます。
これではお店は成り立ちません。
そこで、ウナギーさんはまず今日は何人お客さんが来るかをいくつか予想した後、その日に仕入れたすべての鰻の長さを測り、その長さのデータを元に出来る限り大きくて、なおかつお客さんの人数分用意できる鰻の蒲焼きの長さを決めて物差しを使って鰻を切る位置を決めることにしました。
もちろん、切った鰻をつなげることはできません。
ウナギーさんは計算が苦手なので、この出来る限り大きくて、人数分用意できる鰻の蒲焼きの長さを求めるプログラムをあなたに作ってほしいと依頼しました。
お礼に鰻のひつまぶしが食べられると知ったあなたは喜んでこの依頼を受けることにしました。
このお礼としてもらえる鰻のひつまぶしはその日にウナギーさんがお客に振る舞った鰻の蒲焼きの切れ端を使って作られます。
2015/7/23 9:30AM---------------追記しました！---------------------
このひつまぶしに使われる鰻の量を求める式は
鰻の食べられる部分の長さの合計-(客の人数×出来る限り大きくて人数分用意できる鰻の蒲焼きの長さ)
となります。
---------------------------------------------------------------
少なくともどのくらい鰻が食べられるのか知りたくなったあなたは、もし必ずウナギーさんのお客の数の予想のどれか１つが当たるとした場合、絶対に残る鰻の切れ端の量も求めることにしました。
この日に仕入れた鰻の数N、それぞれの鰻の長さLi[cm]（頭などの食べられない部分は含まない）、ウナギーさんがお客さんの数を予想した数Y、ウナギーさんが予想したお客さんの人数Miを入力し、お客さんが仮にMi人来た場合どの長さで鰻を切ればいいかを出力し、そして、最終的にひつまぶしに少なくともどれほどの鰻が使われるかを求めて出力するプログラムを作成しなさい。
入力
N L1 L2 . . . LN Y M1 M2 . . . MY
1行目に鰻の数Nが与えられる。
2行目からは鰻の食べられる部分の長さLiが与えられる。これはソートされて与えられるわけではない。
2+N行目にはウナギーさんがした予想の数Yが与えられる。
2+N+1行目からはウナギーさんがした予想人数Miが与えられる。
出力
一部修正しました！
ウナギーさんがした予想に対する出来る限り大きくて予想した人数分の鰻の蒲焼きが用意できる鰻を切る長さを出力せよ。そして最後にあなたがひつまぶしで少なくとも食べられる鰻の長さを出力せよ。出力の最後に改行を入れること。
また、いっている意味がわからなかったら出力例の解説を見ること。
制約
全ての入出力ケースについて以下を満たす。
- 1 ≦ N,Li,Mi ≦ 10000
- 1 ≦ Y ≦ 1000
入出力例
入力例1
4 208 354 826 1111 3 6 9 2
出力例1
354 222 826 375
解説
解説
まずウナギーさんは6人が来ると予想した。
354[cm]で切った場合2個目の鰻から1つ、3個目の鰻から2つ、4個目の鰻から3つ捕れる。
これが6人のお客が来た場合に無事蒲焼きを作ることが出来、なおかつ鰻を出来る限り多く切ることが出来る
長さである。このとき、使わなかった1個目の鰻と、3個目と4個目の鰻の切れ端を使って合計375[cm]の鰻の切れ端をひつまぶしに使う。
次にウナギーさんは9人が来ると予想した。
222[cm]で切った場合2個目の鰻から1つ、3個目の鰻から3つ、4個目の鰻から5つ捕れる。
これが9人のお客が来た場合に無事蒲焼きを作ることが出来、なおかつ鰻を出来る限り多く切ることが出来る
長さである。このとき、使わなかった1個目の鰻と、2個目と3個目と4個目の鰻の切れ端を使って合計501[cm]の鰻の切れ端をひつまぶしに使う。
次にウナギーさんは2人が来ると予想した。
826[cm]で切った場合3個目の鰻から1つ、4個目の鰻から1つ捕れる。
これが2人のお客が来た場合に無事蒲焼きを作ることが出来、なおかつ鰻を出来る限り多く切ることが出来る
長さである。このとき、使わなかった1個目と2個目の鰻と、4個目の鰻の切れ端を使って合計847[cm]の鰻の切れ端をひつまぶしに使う。
ここで、今日来るお客さんはウナギーさんがした予想の6,9,2の内どれかということがわかっているので、もしどの予想が当たっても合計375[cm]の鰻はひつまぶしに使われるので375を出力する。
入力例2
4 2000 2000 2000 2000 3 1 4 10000
出力例2
2000 2000 NA 0