ページ

2012/06/07

[競技プログラミング][C言語][AtCoder][ふか杯]単位

A - 単位

時間制限 : 2sec / スタック制限 : 8MB / メモリ制限 : 64MB

Description

今学期あなたは,k単位以上取得できなければ,留年してしまうことが分かった.
なんとしてもそれは避けたいので,n個の講義の中からいくつか選んで,k単位を取得したいと思う.

事前の調査によって,各講義で単位を取得するために最低限必要な出席回数が分かった.
学校などできるだけ行きたくないので,k単位以上取得するために必要な最小の出席回数を求めよう.

Input

入力は複数のテストケースからなる.入力の終わりは2つの0のみを含んだ行で示される.
各テストケースは以下の形式で与えられる.

n k
x1…xn
1≦n≦100
1≦k≦n
0≦xi≦100
テストケースの1行目には,2つの整数n, kが書かれている.nは講義の数を表し,kは必要な単位の数を表す.

テストケースの2行目には,n個の整数xiが書かれている.xiはi番目の授業の単位を修得するのに必要な出席回数を表す.

各講義で取得できる単位数は,すべて1単位である.
テストケースの数は1つのファイルにつき1,000個以下であることが保証されている.

Output

各テストケースに対して,最低限出席しなければならない回数を1行で出力せよ.

出典

A: 単位 - ふか杯 5th Contest | AtCoder

回答

AtCoder/fuka5_1.cpp at master · wada811/AtCoder · GitHub

ソートして k まで合計すれば必要最小限の出席回数になる。