ACM (TJU) : 1701


// http://acm.tju.edu.cn/toj/showp1701.html

#include <algorithm>
#include <numeric>
using namespace std;

bool cmp (int x, int y)
{
    return x > y;
}

int main ()
{
    int dataset;
    scanf ("%d", &dataset);
    int cases = 0;

    while ( dataset-- ) {

        int borrow;
        int frnd;

        scanf ("%d %d", &borrow, &frnd);

        int value [1002];

        for ( int i = 0; i < frnd; i++ )
            scanf ("%d", &value [i]);

        printf ("Scenario #%d:\n", ++cases);

        int total = accumulate (value, value + frnd, 0);

        if ( total < borrow )
            printf ("impossible\n\n");

        else {
            sort (value, value + frnd, cmp);

            int count = 0;
            int index = 0;

            while ( borrow > 0 ) {
                borrow -= value [index++];
                count++;
            }

            printf ("%d\n\n", count);
        }

    }


    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s