Oof! You've been coding the whole day and you even had no time for Stack Exchange!

Now, you just want to rest and answer some questions. You have T minutes of free time. You enter the site and see N new questions. To write an answer for each you'll need ti minutes. Of course, as a dedicated reputation gatherer, you want to answer as many questions as you can.

Can you write a program to calculate which questions do you have to answer to write maximum posts in T minutes?

## Input

First line of input consists T minutes you have for answering, and N, how many new questions are on the site.
The second line has N numbers: time you need to answer qi question.

## Output

Write either an array or numbers split with space: indexes of questions(counting from 0 or 1 - what is better for you) you should answer in order to write as many answers as you can. If you can't answer any questions, write nothing or anything to express that it's impossible. If there are several variants, write any.

## Examples

### Inputs               Possible outputs

60 5
30 5 10 20 3    0 1 2 4, 0 1 3 4 or 1 2 3 4

10 5
1 9 5 7 2         0 2 4 or 0 3 4

5 5
1 1 1 1 1         0 1 2 3 4

60 5
48 15 20 40 3  1 2 4 or 1 3 4

5 1
10

1 0

And of course it's , so the shortest code in bytes wins.

# Python 3.8, 81, 79, 75 bytes

Using the walrus operator :=:

lambda k,l:[i for j,i in sorted((v,k)for k,v in enumerate(l))if(k:=k-j)>=0]


Try it online!

-2 bytes thanks to @JoKing

-4 bytes thanks to @justhalf

# Python 3, 158, 137, 136, 130, 127, 117, 103, 95 bytes

def f(k,l):
q=[]
for j,i in sorted((v,k)for k,v in enumerate(l)):k-=j;q+=[i]*(k>=0)
print(q)


Try it online!

-21 bytes thanks to @79037662 by limiting indentation to 1-space.

-14 bytes thanks to @ mypetlion

-8 bytes thanks to @justhalf

Both solutions ignore N parameter.

• One easy golf is to use only a single space for the indents: tio.run/… Commented Nov 28, 2019 at 19:40
• Wouldn't that be -7 bytes? Commented Nov 28, 2019 at 19:42
• @game0ver Oh, nvm...you originally had -1 total in the message. I only counted -1 byte per indent level instead of -3. Commented Nov 28, 2019 at 20:11
• Another -3 bytes by modifying k instead of m. This trick can be applied to the Python 3.8 solution, too. Reducing it by 4 bytes by removing m. Commented Nov 29, 2019 at 11:00
• @justhalf That's brilliant, never crossed my mind to modify k instead :) Thank you! Commented Nov 29, 2019 at 11:06

# 05AB1E, 913 12 bytes

ā<æʒ¹sèO@}éθ


Takes the inputs in the order: $$\q_i\$$, $$\N\$$ (which is mostly ignored, see explanation below), $$\T\$$.
Uses 0-based indexing.

+4 bytes as bug-fix for test case [1,1,1,1,1] resulting in [0,0,0,0,0] instead of [0,1,2,3,4] (and now switched from 0-based to 1-based indexing).
-1 byte thanks to @Grimmy (and back to 0-based indexing again).

Explanation:

             # Take the (implicit) input-list qi
ā            # and push a list in the range [1, list-length] without popping the input itself
<           # Decrease each by 1 to make it 0-based: [0, list-length)
æ          # Get the powerset of this list of indices
#  i.e. [0,1,2] → [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]
ʒ         # Filter this list of lists by:
¹        #  Push the first input-list qi again
s       #  Swap to put the current list of the filter at the top of the stack
è      #  Index each into the list qi
O     #  Sum these values
@    #  Check if the (implicit) input-integer is >= this sum
#  (The very first iteration it will use the second input, which is the length N;
#   every other iteration it will use the third input, which is the total time T.
#   Since the very first inner list of the powerset will be the empty list,
#   this causes no problems; which is how we ignore the mandatory length N input)
}é  # After the filter: sort all remaining inner lists by length
θ # Pop and leave the last one, which is (one of) the list(s) with the most items
# (after which the result is output implicitly)

• You can go back to 0-based indexing by using .ā instead of āø. Commented Nov 29, 2019 at 13:25
• Here's a 12 Commented Nov 29, 2019 at 13:31
• @Grimmy Thanks! And I had no idea we had the builtin .ā. Commented Nov 29, 2019 at 13:54

# Japt, 222116 15 bytes

ð à ñÊÔæÈxgU <V


Try it

ð à                 combinations of indexes of 1st input
ñÊÔ             sorted by length and reversed
æ            get first element returning true when passed throug...
ÈxgU        elements of input at X indexes reduced by addition
<V   less than 2nd input


Takes input as [times...], time , amount

Saved 1 stealing from @Shaggy ÈxgU

• Well, damn! Wrote my solution up hours ago but got distracted by work and only now, after posting it, do I see this, which can be golfed down to my exact solution. Sorry. One of these days I'll learn to reload before posting! Commented Nov 28, 2019 at 22:43
• Your sorting method can be golfed to ñÊ but isn't actually necessary as à sorts by descending length. And r+ can be just x. Commented Nov 28, 2019 at 22:45
• I regolfed a bit by myself to 16.. You still beaten me @Shaggy, thanks for the tips! Commented Nov 28, 2019 at 23:16
• Ah, I think I might have been thinking of ã, which sorts by ascending length. Commented Nov 28, 2019 at 23:33
• @Embodiment of Ignorance it is valid too because we don't have to maximize the time, it was specified in the comments. Commented Nov 29, 2019 at 7:23

# dzaima/APL, 1514 13 bytes

+\∘<⍛≤+/⍛↑⍋⍤⊣


Try it online!

+\∘<⍛≤+/⍛↑⍋⍤⊣  train; left arg = ⍺ = t, right arg = ⍵ = T
≤         ⍺ <= ⍵
⍛          with ⍺ modified to
<             sorted
+\∘              and then, cumulative sum
so, cumulativeSum(sort(q)) ≤ T

⍋    the indices required for sorting
⍤⊣  applied on ⍺
so, the output, sorted by question time, if T=∞

↑     take first ⍺ elements from ⍵ (⍺ is +\∘<⍛≤, ⍵ is ⍋⍤⊣)
+/⍛        but summing ⍺ first


# Jelly, 8 bytes

ṢÄ>¬TịỤ{


A dyadic Link accepting the question times on the left and the total time on the right which yields the 1-indexed indices.

Try it online! (footer calls the Link and prints a formatted version of its output.)

(If we must take the number of questions, this works as full program accepting: question times; total time; number of questions.)

### How?

ṢÄ>¬TịỤ{ - Link: ts; T        e.g. [1, 9, 5, 7, 2]; 10
Ṣ        - sort ts                 [1, 2, 5, 7, 9]
Ä       - cumulative sums         [1, 3, 8,15,24]
>      - greater than (T)?       [0, 0, 0, 1, 1]
¬     - logical NOT             [1, 1, 1, 0, 0]
T    - truthy indices          [1, 2, 3]
{ - use left argument:
Ụ  -   indices by value      [1, 5, 3, 4, 2]   (i.e index 4 has 2nd largest value)
ị   - index into              [1, 5, 3]


Alternative 8:

ỤṁṢÄ>Ðḟɗ - indices-by-value moulded-like (cumulative-sums of sorted(ts) if not greater than T)


Try it online!

• Does Jelly have a single byte operator for <=, which would allow you to skip the NOT? Commented Nov 28, 2019 at 23:11
• No it does not. Commented Nov 28, 2019 at 23:13
• Shame. It looks like some solutions are assuming that the result must be strictly <T rather than <=T so it might be worth asking for clarification on that. Commented Nov 28, 2019 at 23:16
• @tsh Ah yeah, that's a bug, I should use T not M (since if no cumulative sums are not greater than the right argument the zeros will be the maximal values. T will instead get truthy indices, so non-zeros). Thanks for spotting that. (FWIW the alternative 8 byte solution works as-is) Commented Nov 29, 2019 at 10:49

# JavaScript (V8), 1171131101058571 63 bytes

(-3 thanks to Ver Nick says Reinstate Monica)

(-20 thanks to Arnauld)

(-14 thanks to Shaggy)

(-8 thanks to tsh)

a=>g=t=>(a[y=a.indexOf(i=Math.min(...a))]=t)<i?[]:[y,...g(t-i)]


Try it online!

Could probably be golfed some more...a function which takes input in three arguments: time, number of questions (not actually used), and an array of question times.

It will repeatedly find the smallest element in the array, and set it to the time available, removing it from the possibilities for the next iteration. It puts the index of the value into the output array.

Thanks to everyone who's contributed to golfing this answer...54 bytes shorter than the original!

• You can replace true with 1 Commented Nov 28, 2019 at 19:29
• @Arnauld Thanks! I forgot you could put variable assignments as arguments like that... Commented Nov 28, 2019 at 21:25
• 71 bytes. On my phone so can probably be golfed a bit further. Commented Nov 28, 2019 at 23:05
• Maybe 63 bytes? I'm not sure if this is correct (since previous comments does not suggest this with no reason)
– tsh
Commented Nov 29, 2019 at 10:04
• Good shout, @tsh, completely missed that. Commented Nov 29, 2019 at 12:35

# Japt-h, 14 bytes

Assumes 0 is not a valid unit of time.

ð à ñÊfÈxgU §V


Try it

ð à ñÊfÈxgU §V     :Implicit input of array U=q and integer V=T
ð                  :0-based indices of U
à                :Combinations, which, fortunately, includes the empty array, covering the last test case.
ñ              :Sort by
Ê             :  Length
f            :Filter
È           :By passing each throughout a function
gU        :    After indexing each back in to U
§V     :  Less than or equal to V?
:Implicit output of last element


Or, if we have to take N as input (or 0 is a valid unit of time).

o à ñÊfÈxgV §W


Try it

Where U=N, V=q, W=T, o creates the range [0,U) and everything else is as above.

# Red, 133 bytes

func[t b][s: 0 sort collect[foreach n sort collect[repeat i length? b[keep/only
reduce[b/:i i]]][if(u: s + n/1)<= t[s: u keep n/2]]]]


Try it online!

1-indexed. Ignores N

# R, 44 41 bytes

function(m,t)order(t)[cumsum(sort(t))<=m]


Try it online!

Takes input as Time, times. Returns numeric() for empty output.

Order the times, take cumulative sum and then select the times where the cumulative sum is less than or equal to total time.

-1 in the end to get 0-index

-1 byte thanks to Giuseppe
-2 bytes since 0-index is no longer needed

• The OP seems to indicate 0 or 1 indexing doesn’t matter.
– cole
Commented Nov 29, 2019 at 9:04
• 43 bytes Commented Nov 29, 2019 at 15:49

# Ruby, 68 64 60 59 58 bytes

->t,q{q.map.with_index.sort.reject{|x,|0>t-=x}.map &:last}


Try it online!

# JavaScript (ES10),  78  75 bytes

Saved 3 bytes thanks to @Neil

Takes input as (T)(list). Ignores N.

t=>a=>a.map((...x)=>x).sort(([a],[b])=>a-b).flatMap(([v,i])=>(t-=v)<0?[]:i)


Try it online!

• +1 for outgolfing me by 27 bytes...never would have thought of anything like this! Commented Nov 28, 2019 at 20:13
• -3 bytes: map((...x)=>x)
– Neil
Commented Nov 28, 2019 at 21:03
• @Neil Nice one! Thanks. Commented Nov 28, 2019 at 21:44

# Charcoal, 44 bytes

Ｎθ≔ＥＮ⟦Ｎι⟧ηＷ∧η¬‹θ§⌊η⁰«≔⌊ηι≧⁻§ι⁰θ≔Φη⁻⌕ηιλη⟦Ｉ⊟ι


Try it online! Link is to verbose version of code. Explanation:

Ｎθ


Input T.

ＥＮ⟦Ｎι⟧η


Input N and make a list of N questions with their original index.

Ｗ∧η¬‹θ§⌊η⁰«


Loop until there are no more questions that can be answered in the remaining time.

≔⌊ηι


Get the shortest question and its original index.

≧⁻§ι⁰θ


Subtract the question's time from the time remaining.

≔Φη⁻⌕ηιλη


Remove the question from the list of questions.

⟦Ｉ⊟ι


Print the question's original index.

• You have 3000 posts by now, congrats :) Commented Nov 28, 2019 at 21:08
• @VerNicksaysReinstateMonica wow, I'm actually first at something ;-)
– Neil
Commented Nov 29, 2019 at 1:26

# Python 3, 72 bytes

recursive solution, generating line separated console output

def f(T,L):
if L:M=min(L);I=L.index(M);L[I]=T;T<M or(print(I),f(T-M,L))


Try it online!

def f(T,L):
if L:            # do nothing if input is empty
M=min(L)
I=L.index(M)
L[I]=T          # set found list item to remaining time (item will be ignored next iteration)
T<M or(print(I),f(T-M,L))   # if the found question can be answered in the given time output and find next


# J, 16 bytes

(>:+/\@/:~)#/:@]


Try it online!

Attempt at an explanation:

>:                create mask of left arg greater than or equal to...
+/\@/:~         cummulative sum of sorted right arg
#        copy where true
/:@]    from permutation that sorts right arg

• any explanation? Commented Dec 1, 2019 at 17:15
• @Varad Mahashabde: Here is an attempt. If you need more context please let me know. Commented Dec 1, 2019 at 20:09

# C++11, 293 221 219 bytes

Here to decimate the competition I am not.

Notes :

1. g++ allows for variable-sized arrays. It saves bytes, so that what I did.
2. the range-based for loops needs a reference to write correctly?!
#include<iostream>
void f(int t,int c,int*a){int m,i;int y[c];for(int&b:y)b=0;for(;;){for(m=-1;y[++m]&m<c;);for(i=-1;++i<c;)if(a[m]>=a[i]&!y[i])m=i;if(t>=a[m]&!y[m]){y[m]=1;t-=a[m];}else break;}for(i=-1;++i<c;)if(y[i])std::cout<<i<<' ';}


Expanded version :

#include <iostream>

int minimum_term;
b = 0 ; // No questions have been answered
while (1) {
// Find the first unanswered question
for (minimum_term = 0; is_answered[minimum_term] and minimum_term < question_count; ++minimum_term);
for (int i = 0; i < question_count; ++i)
minimum_term = i;
// Answer question (which consumes time)
}
else break;
}
// Print index of every answered question
// 'cause returning them is a waste of bytes to implement
// Just echo it to a file or something
for (int i = 0; i < question_count; ++i)
std::cout<<i<<' ';
}

int main(int c, char** v) {
int question_count = atoi(v[2]), free_time = atoi(v[1]);
for (int i = 0; i < question_count; ++i)
// Run solution
}


Try it online!

• Welcome to CG&CC! I can't really help you golf this program, as I am not a C++ golfer, but I suggest you to look at tips for golfing in C++. Additionally, submissions don't have to be full programs, they can be functions taking input and outputting through their return value, which may or may not save bytes in this case. Commented Dec 1, 2019 at 18:16
• Also, while(1) can be for(;;). I suggest adding a Try it Online! link for future submissions Commented Dec 1, 2019 at 18:25
• for(i=3;i<c;++i) can be golfed to for(i=2;++i<c;) saving a byte. Commented Dec 1, 2019 at 22:27
• if(t-atoi(v[m])>=0&&!y[i-3]) can be golfed to if(t>=atoi(v[m])&&!y[i-3]) saving 2 bytes. Commented Dec 1, 2019 at 22:32
• np :-) Also think you can golf bool y[c];for(bool&b:y)b=0; to int y[c];for(int&b:y)b=0; saving 2 bytes. Commented Dec 3, 2019 at 20:51

# Husk, 9 bytes

↑#≤²∫O¹ηÖ


Try it online! Outputs an empty list if no solution is possible.