CCC '13 J4 - Time on task

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2013 Stage 1, Junior #4

You have been asked by a parental unit to do your chores.

Each chore takes a certain amount of time, but you may not have enough time to do all of your chores, since you can only complete one chore at a time. You can do the chores in any order that you wish.

What is the largest amount of chores you can complete in the given amount of time?

Input Specification

The first line of input consists of an integer T (0 \le T \le 100\,000), which is the total number of minutes you have available to complete your chores.

The second line of input consists of an integer C (0 \le C \le 100), which is the total number of chores that you may choose from. The next C lines contain the (positive integer) number of minutes required to do each of these chores. You can assume that each chore will take at most 100\,000 minutes.

Output Specification

The output will be the maximum number of chores that can be completed in time T.

Sample Input 1

6
3
3
6
3

Output for Sample Input 1

2

Explanation of Output for Sample Input 1

Chores must be completed in at most 6 minutes. There are 3 chores available. The first chore takes 3 minutes. The second chore takes 6 minutes. The third chore takes 3 minutes. The answer is 2 since only 2 of these chores can be completed in 6 minutes of time. Specifically, the first and last chore can be completed in the allowable time. It is not possible to complete all 3 chores in 6 minutes.

Sample Input 2

6
5
5
4
3
2
1

Output for Sample Input 2

3

Explanation of Output for Sample Input 2

Tasks 3, 4, and 5 can be completed in 6 minutes. It is not possible to complete more than 3 tasks in 6 minutes.


Comments


  • -2
    leotong1518  commented on Oct. 12, 2018, 10:44 p.m.

    hi


    • -1
      NNNNNOOO  commented on Feb. 7, 2019, 7:38 p.m. edited

      hi


      • -2
        Arihan10  commented on Feb. 8, 2019, 5:06 p.m. edited

        Hello, and welcome to DM::OJ! Comments should only be used for help about the topic/problem at hand, not out-of-context messages or extended discussion.

        Before commenting, think: Is this comment going to help somebody who views this problem? Jokes and other comments are welcome, but first do this test: Is somebody who views this comment a year from now still going to find this funny and/or helpful? Is this an inside joke that only me and my friends know? If so, then please try to refrain from commenting.

        The rest, however, I will leave to your own judgement. Please, and thank you Big V.


  • -10
    zwang24  commented on Aug. 23, 2018, 5:27 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 6
    bobhob314  commented on Jan. 4, 2015, 7:15 p.m.

    C is 5 but there are six lines below C.


    • 2
      FatalEagle  commented on Jan. 4, 2015, 8:23 p.m.

      Fixed.