#🔒 training for competation

374 messages · Page 1 of 1 (latest)

wet seal
#

Hi! I'm currently training for a programming competation and I'm stuck at a task, I got a solution but its not optimal:

from copy import copy


def main():
    N, M = map(int, input().split())
    sutok_limits = list(map(int, input().split()))

    sutok = copy(sutok_limits)
    j = 0
    while M >= 0:
        for i in range(N):
            if sutok[i] > 1:
                sutok[i] -= 1
            else:
                sutok[i] = sutok_limits[i]
                M -= 1
        j += 1
    print(j)


main()

the problem is that someone is waiting in a queue for his food and there are N ovens and M people before him, (sutok means ovens in my language) and in the next lime I read the times for each oven to cook the food for a person (everyone orders the same food)

indigo flintBOT
#

@wet seal

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
wet seal
#

example:
input:
2 6
1 2
output:
5

gentle gale
#

4 uses of the 1 minute oven over 4 minutes + 2 uses of the 2 minute oven over the same 4 minutes = 4 minutes to feed 6 people

wet seal
#

M is the amount of people before him

hollow walrus
gentle gale
#

oh i see

#

so just m+1 then

wet seal
#

yes

wet seal
# hollow walrus You should provide the exact problem statement without rewording it so that peop...

its in hungarian but translate:
Feri's favorite food is lángos, but not just any lángos—it's the onion and sour cream version made at his favorite snack bar. Over the years, the snack bar has become very popular, so there's always a long line, but on the plus side, the snack bar has multiple fryers, so it can make lángos simultaneously.

Feri arrived at the snack bar before it opened, but there are already M people ahead of him in line. The snack bar has N fryers, each of which takes T1, T2, ..., TN seconds to prepare a single lángos. The fryers start making the lángos continuously from the moment the snack bar opens, and as soon as one is done, the next one starts.

Write a program that determines how many seconds after opening it will take for Feri to receive his much-anticipated lángos!

Input
The first line of input contains two integers: N (the number of fryers) and M (the number of people standing in line in front of Feri).
The second line contains N positive integers T1, T2, ..., TN, where Ti represents the number of seconds the i-th fryer takes to make a lángos.

Output
Output a single integer representing the number of seconds after opening when Feri will get his lángos.

gentle gale
#

suppose that the oven which takes the longest time is denoted as max(T)

when max(T) runs once, every other T_1, T_2, .. T_i can run floor(max(T)/T_i) times.

suppose you sort the list of the ovens by their speed (O(nlogn))

you can calculate how many people you can feed in the runtime of one max(T) (the last oven in that list). if this number is greater than M, remove max(T) from the list and repeat.

once the number of people you can feed in the runtime of the newest max(T) is <= M: if its equal to M, it will take max(T) minutes. if its less than M, recurse for a new M = M - (the number of mouths the current set of ovens can feed).

this is sort of my line of thinking right now. theres a few problems with it and there might be a better approach, but this is how im looking at it

wet seal
#

what if sum(T) < M?

gentle gale
#

thats what you want, that means youve found the slowest oven that you can use, any slower and you guarantee that youve missed the solution, generally

#

after that you havs a subproblem of finding the same answer for M-sum(t) with the new subset of ovens

#

hence my thought of recursion

#

in general, lets say for a given set of ovens T = [T_1, T_2, ... T_i], we define T(s) as being the number of people the ovens on T can feed in s seconds, calculated by sum(s/T_i).

You want to find largest integer s such that T(s) < M. this actually automatically removes ovens that are too slow, now that i think about it

wet seal
#

okay, so far I got to here:

def main():
    N, M = map(int, input().split())
    ovens = sorted(map(int, input().split()))
    maxT = ovens[-1]

    can_feed_in_maxT_time = 0
    for oven in ovens:
        can_feed_in_maxT_time += maxT // oven


main()
gentle gale
#

then you set M = M - T(s) and repeat until M = 0

gentle gale
wet seal
#

isn'T it int(s/T_i)?

#

instead of sum(s/T_i)

gentle gale
#

sum(int(s/T_i)) i suppose

wet seal
#

s is the duration and T_i is the oven's cook time what do you sum here its a single number?

gentle gale
#

the ovens are running concurrently so if you have T = [1, 5], the first oven can run 5 times in the same 5 seconds that the second oven can run once

#

5/1 + 5/5

#

= 6 people in 5 seconds

wet seal
#

so its the code that I already did the can_feed_in_maxT_time

gentle gale
#

sort of. the idea of caring abt the max had to do with my previous thought process but im not so sure sorting is required anymore.

#

you have written the calculation for T(max(t))

#

i am wondering if there is a better way to choose an s for T(s) than T(max(t))

wet seal
#

maxT == s

#

isn't it?

gentle gale
#

T(s) is a function defined for any s

#

like f(x) = x^2

#

in this case youve done it for max(t), which still may be a good way im just thinking about optimization

#

im sort of solving this as i go

wet seal
#

so T looks like this:

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s//oven
        return returning
gentle gale
#

exactly

#

we want to find the largest s such that T(s)<M

#

then set M = M - T(s)

#

then repeat until M = 0

#

and sum all such T(s) found in the process

wet seal
gentle gale
#

probably

wet seal
#

so its like this currently?

def main():
    N, M = map(int, input().split())
    ovens = list(map(int, input().split()))

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    i = 0
    while T(i) < M:
        i += 1
    print(i)


main()
gentle gale
#

the upper bound for s is certainly M*max(T)

gentle gale
wet seal
#

doesn't give right answer

#

it gives 4 instead of 5

gentle gale
#

its not the full algorithm

#

the one you have

gentle gale
wet seal
#

okay

hollow walrus
gentle gale
#

oh you are right, it cant take any longer than the fastest one can it

hollow walrus
#

yep

#

If you're already paying nlogn for sorting you can solve it with a binary search, with M*min(T) being the upper bound. I'm wondering if there's something simpler though

gentle gale
#

i believe starting from there and counting down is likely fast on average? maybe? still think we can do better

gentle gale
wet seal
#

this is still not giving right answer: ```py
def main():
N, M = map(int, input().split())
ovens = list(map(int, input().split()))

def T(s):
    returning = 0
    for oven in ovens:
        returning += s // oven
    return returning

while M != 0:
    i = 0
    while T(i) < M:
        i += 1
    M = M - T(i)

print(i)

main()

gentle gale
#

just need max and min which is linear

wet seal
gentle gale
#

here uh

#

im on phone so this might take me a second

gentle gale
wet seal
# 
def main():
    N, M = map(int, input().split())
    ovens = list(map(int, input().split()))

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    sums = 0
    while M != 0:
        i = 0
        while T(i) < M:
            i += 1
        M = M - T(i)
        sums += i

    print(i)


main()
```?
gentle gale
wet seal
#

nope

gentle gale
#

still 4?

wet seal
#

yes

gentle gale
#

wajt

#

try it for another input and tell me if its still 1 off?

#

wait nvm

wet seal
#

probaly I should make the i cound count down from M*min(T)

#

that will give langest i and not smallest

gentle gale
#

its still getting to M=0 though

#

oh wait i think i know the problem

#

suppose the largest s such that T(s) < M is 3

#

T(3) is < m

#

so the while loop continues

#

i goes to 4

#

then it breaks

#

but you want 3

wet seal
#

so?

gentle gale
#

!e ```py
def main():
N, M = 2, 6
ovens = [1, 2]

def T(s):
    returning = 0
    for oven in ovens:
        returning += s // oven
    return returning

sums = 0
while M != 0:
    i = 0
    while T(i) < M:
        i += 1
    
    M = M - T(i)
    sums += i

print(i)

main()

#

huh i think i made an infinite loop

#

woops

wet seal
#

yes

#

M is never 0

#

it gets to negatives

#

probably

gentle gale
#

oh wait... heres an interesting thought that throws a wrench in this

wet seal
#

!e

def main():
    N, M = 2, 6
    ovens = [1, 2]

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    sums = 0
    while M > 0:
        i = 0
        while T(i) < M:
            i += 1
        
        M = M - T(i)
        sums += i

    print(i)


main()
indigo flintBOT
gentle gale
#

considerr this

#

oof i didnt think abt this

#

1, 5
3

modest zodiac
gentle gale
#

for one thing, largest s is T(5) when we actually want T(3)

wet seal
gentle gale
#

oh wait im stupid i think the second issue isnt real. i was gonna say something along the lines of divisibility but thats not an issue. you can feed any number of people with any oven, obviously

modest zodiac
gentle gale
#

!e

def main():
    N, M = 2, 6
    ovens = [1, 2]

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    sums = 0
    while M > 0:
        i = M*min(ovens)
        while T(i) > M:
            i -= 1
        
        M = M - T(i)
        sums += i

    print(i)


main()
modest zodiac
indigo flintBOT
gentle gale
#

still?? damn

#

oh my gosh im stupid

#

4 is correct in this instance, it works @wet seal

#

M is 6

#

we never accounted for that +1 from earlier, lmao

#

if M is actually 6 it works

#

me when my code is smarter than i am

#

!e

def main():
    N, M = 2, 6
    ovens = [1, 2]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    sums = 0
    while M > 0:
        i = M*min(ovens)
        while T(i) > M:
            i -= 1
        
        M = M - T(i)
        sums += i

    print(i)


main()
indigo flintBOT
gentle gale
#

theres a min running every loop which migjt slow things down so lets move that out

wet seal
gentle gale
#

!e

def main():
    N, M = 2, 6
    ovens = [1, 2]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        i = M*fastest
        while T(i) > M:
            i -= 1
        
        M = M - T(i)
        sums += i

    print(i)


main()
indigo flintBOT
wet seal
modest zodiac
# wet seal oh

I'm not really in a position to code rn unfortunately
But consider a priority queue

gentle gale
#

i think for very large N and M there is a better algorithm though

modest zodiac
wet seal
#

so which one should I go with?

modest zodiac
#

Mine would be M log N

gentle gale
#

i havent thought out the pq solution so i dont know

wet seal
#

Karma one can definetly be optimised to binary search in the range(0, M*fastest)

gentle gale
#

i also dont know how to find the time complexity for mine since it depends on the distance from M*min(T) to s such that T(s)<M

wet seal
#

limits:

image.png
gentle gale
#

i dont even know what the worst case for that distance is

wet seal
gentle gale
#

to know that id need a closed form solution for max(s)(T(s)<M)

#

if such a solution exists this becomes linear time i think

modest zodiac
# wet seal limits:

Don't go with mine then
Don't go with any solution that involves a linear or above M factor

wet seal
#

so I should make bi search

modest zodiac
#

Alternate:
Binary search the answer (how long it takes), calculate how many people that amount of time is served, update ranges accordingly

gentle gale
#

binary search is a bit tricky to implement here though

modest zodiac
#

N log M

gentle gale
#

you need the largest s, not any s

modest zodiac
wet seal
#

s is the time the restaurant is simulated for

gentle gale
#

T(s) is a function that returns the number of people all ovens can feed in s seconds

modest zodiac
wet seal
#

but we need the biggest s

gentle gale
#

the s which makes the algorithm work is the largest such s that T(s)<M

modest zodiac
gentle gale
#

how do you know if you are at the largest s without checking the one above it

modest zodiac
wet seal
# 
def binary_search_T(M):
    low, high = 0, M
    while low <= high:
        mid = (low + high) // 2
        if T(mid) > M:
            high = mid - 1
        else:
            low = mid + 1
    return high
```?
modest zodiac
#

it's just bin s

modest zodiac
wet seal
modest zodiac
wet seal
#

so currently: ```py

def main():
N, M = map(int, input().split())
ovens = list(map(int, input().split()))
M += 1

def T(s):
    returning = 0
    for oven in ovens:
        returning += s // oven
    return returning

fastest = min(ovens)
sums = 0
while M > 0:
    low, high = 0, M*fastest
    while low < high:
        mid = (low + high) // 2
        if T(mid) > M:
            high = mid - 1
        else:
            low = mid + 1
    i =  high
    M -= T(i)
    sums += i
print(i)

main()

#

its almost right

gentle gale
#

wdym almost right? did the answer change?

wet seal
#

it doesn't work for:
4 6
10 120 25 30

#

the output should be 50 and it gives 10

gentle gale
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        i = M*fastest
        while T(i) > M:
            i -= 1
        
        M = M - T(i)
        sums += i

    print(i)


main()
indigo flintBOT
gentle gale
#

hmm lemme see

#

how in the world is that getting 10

#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        i = M*fastest
        while T(i) > M:
            i -= 1
        M = M - T(i)
        sums += i

    print(sums)


main()
indigo flintBOT
wet seal
#

bruh

gentle gale
#

should*

#

and i see the reason why its 59 instead of 50 i think? maybe

wet seal
gentle gale
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        i = M*fastest
        while T(i) > M:
            i -= 1
        M = M - T(i)
        sums += i
        print(i, sums)

    print(sums)


main()
indigo flintBOT
gentle gale
#

yep 49+10 instead of 40+10... hmm

#

ah! got it

#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        i = M*fastest
        while T(i) > M:
            i -= fastest
        M = M - T(i)
        sums += i

    print(sums)


main()
#

50!

wet seal
#

what did you cange?

indigo flintBOT
wet seal
#

-= fastest

gentle gale
#

mhm

wet seal
#

now lets bin s this

#

ugh...

gentle gale
#

yeah its tougher now

#

i have a thought

wet seal
#

!e ```py
def main():
N, M = 4, 6
ovens = [10, 120, 25, 30]
M += 1

def T(s):
    returning = 0
    for oven in ovens:
        returning += s // oven
    return returning

fastest = min(ovens)
sums = 0
while M > 0:
    i = M * fastest
    while T(i) > M:
        i -= fastest
    M = M - T(i)
    sums += i

print(sums)

main()

indigo flintBOT
wet seal
#

I copied the wrong code

#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        low, high = 0, M * fastest
        while low < high:
            mid = (low + high) // 2
            if T(mid) > M:
                high = mid - fastest
            else:
                low = mid + fastest
        i = high
        M -= T(i)
        sums += i
    print(sums)


main()
indigo flintBOT
wet seal
#

wtf is 57 now?

gentle gale
#

yeah that doesnt work

gentle gale
wet seal
#

?

gentle gale
#

bin search from 0 to M normally, multiply by fastest when calling T

#

so when i increments by 1

#

it actually increments by fastest

#

if u know what i mean

wet seal
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s // oven
        return returning

    fastest = min(ovens)
    sums = 0
    while M > 0:
        low, high = 0, M
        while low < high:
            mid = (low + high) // 2
            if T(mid) > M:
                high = mid * fastest
            else:
                low = mid * fastest
        i = high
        M -= T(i)
        sums += i
    print(sums)


main()
indigo flintBOT
gentle gale
#

nono

#

T(mid*fastest)

wet seal
#

wait

gentle gale
#

everything else treats mid as just searching for a value from 0 to M

wet seal
gentle gale
#

oh wha

#

now what xd

wet seal
#

idk

#

I don't even know the inputs

modest zodiac
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    T = lambda time: sum(time // oven for oven in ovens)

    l, r = 0, 10**18
    while l < r:
        m = (l + r) >> 1
        if T(m) > M:
            r = m
        else:
            l = m + 1
    print(l)


main()
indigo flintBOT
gentle gale
#

oh yikes

wet seal
modest zodiac
gentle gale
#

thats just integer divisin by 2

wet seal
wet seal
#

gave 65 points instead of 10

#

but for some ungodly input it gives wrong output

gentle gale
#

yeeah division is super expensive

modest zodiac
#

cause I just saw you can have M and all oven time as 10**9
Which would break my code as it's r not inclusive

gentle gale
#

upper bound is M*fastest no matter what

#

why r we using 10**18

wet seal
#

we could go from my original code worked for the input this didn't work for

wet seal
modest zodiac
wet seal
modest zodiac
wet seal
gentle gale
#

it only works if M is immediately summable through T

#

that was the whole idea of the outer while loop

modest zodiac
gentle gale
#

because thats not what the algorithm is lol

modest zodiac
#

...ok

gentle gale
#

T(s)<M not T(s)=M

wet seal
#

the bs could say a good answer but we need the biggest answer

gentle gale
#

essentially look at it like this

modest zodiac
gentle gale
#

no im saying thats how the algorithm has to be

#

you cant find one s

#

you find the largest allowed

#

then change M

#

and do that until M is 0

#

there is no guarantee there is 1 such s that works for the first M

wet seal
gentle gale
#

imagine you have your list of oven timings

(1, 10, 5, 7)

#

T(s) is a transformation over this list

#

to (s//1, s//10, s//5, s//7)

#

think about what happens when s is < 10

#

the 10 term becomes 0

modest zodiac
wet seal
#

could this work? ```py
def main():
N, M = map(int, input().split())
ovens = list(map(int, input().split()))

T = lambda time: sum(time // oven for oven in ovens)

sums = 0
while M > 0:
    l, r = 0, M * min(ovens)
    while l < r:
        m = (l + r) >> 1
        if T(m) > M:
            r = m
        else:
            l = m + 1

    M = M - T(l)
    sums += l
print(sums)

main()

gentle gale
#

or you can not let me explain ._., there is no guarantee such an s exists for the first M

#

so you get as close as you can

#

then find the solution for the remainder

#

hence the summation

wet seal
modest zodiac
modest zodiac
# wet seal nope

an adhoc fix is, once the bs ends, check if T is actually M
then nudge it by +-1ing til the solution

#

not elegant but may work

gentle gale
#

im trying to figure out where i got this notion now lol

#

is there always some s such that T(s)=m?

#

1, 5
3

this says no

gentle gale
wet seal
#

as s in T(s) gets bigger the answer is getting bigger too right?

gentle gale
#

and if you check for >M

modest zodiac
gentle gale
#

well just plug any large s in

#

thats why i did the largest <M s

modest zodiac
#

e.g. two ovens finish in 1
then you never serve an odd number of ppl

gentle gale
#

yeah

modest zodiac
#

so actually, bs for smallest s s.t. T >= M?

gentle gale
#

i believe so

modest zodiac
#

or maybe you can bs on reals instead of integers
prolly doesn't work

gentle gale
#

ive been thinking abt this so long im having to reunderstand my owm thought processes lol

modest zodiac
#

I think you still only need to fix the bs code
like with bs, there's many variants, e.g. lowerbound, upperbound, etc.
you want the variant that finds the first >=

hollow walrus
#

not sure if that was the question, I wasn't following the whole thread

modest zodiac
#

not braining good currently

hollow walrus
#

also in the code you showed the upper bound can be M*min(T) which is probably much lower

gentle gale
#

i did say that haha

hollow walrus
#

but otherwise yeah binary search works

#

I was trying to figure out how to do it in linear time, but having to finish whole pies is messing things up for me

modest zodiac
hollow walrus
#

My thinking went in the direction of: What is the amount of work that each oven does compared to the rest?

For example if you have two ovens with speeds 1 and 2, per unit of time you bake 1.5 pies, so the first oven does 67% of the work, while the second oven does 33% of the work. So baking 7 pies will take at least 7/1.5 = 4.66 minutes

#

Which is really close to the answer, the problem is that you need complete pies.

gentle gale
#

are the percentages even relevant in that solution

#

theres surely no way its as simple as ceil(avg(T))

modest zodiac
#

yea... Also why I think bs on reals doesn't work
Pie fractions may be (mis)counted to add up to a pie

gentle gale
modest zodiac
#

doesn't hurt to try it?

gentle gale
#

no wait

#

its not

#

obviously

#

1, 10
1

hollow walrus
#

I originally computed the percentages to see how many pies each oven would bake in that time, it's not directly related to the rest of what I said

#

Because the first oven would bake 67% out of the 7

#

The problem is that again it's not a whole number

gentle gale
#

sorry, ceil(M/avg(T))

#

now if that works

#

ill cry

hollow walrus
#

There's no reason for that to work, you still need whole pies

#

also the result of that calculation is average baking speed, not time

#

no not even

#

it's something speed

gentle gale
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s / oven
        return returning

    print(M/T(1))


main()
indigo flintBOT
gentle gale
#

nope

#

should be approx 50

#

why doesnt that work

hollow walrus
#

!e

import numpy as np
time_per_pie = np.array([10, 120, 25, 30])
pie_per_time = 1 / time_per_pie
total_pies_per_time = pie_per_time.sum()
print(7 / total_pies_per_time)
indigo flintBOT
hollow walrus
#

was just checking something

hollow walrus
#

You do get 50 pies, just in fractions of completetion

gentle gale
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s / oven
        return returning

    print(M/T(max(ovens)) *max(ovens))


main()
indigo flintBOT
gentle gale
#

lol nope

wet seal
#

I got an other task for today should I post it in an other help thread?

gentle gale
#

ill be going to sleep after i figure out or give up on this one, so probably

hollow walrus
#

!e

import numpy as np
time_per_pie = np.array([10, 120, 25, 30])
pie_per_time = 1 / time_per_pie
total_pies_per_time = pie_per_time.sum()
time_taken = 7 / total_pies_per_time
print((time_taken // time_taken).sum())
indigo flintBOT
hollow walrus
#

uuh I messed it up, nvm

hollow walrus
#

feel free to close this one

wet seal
#

not yet

gentle gale
#

noooo im not done obsessing

wet seal
#

if you get to something just ping me

modest zodiac
#

this should be done if bs is fixed
unfortunately I am dum

hollow walrus
#

!e

import numpy as np
time_per_pie = np.array([10, 120, 25, 30])
pie_per_time = 1 / time_per_pie
total_pies_per_time = pie_per_time.sum()
time_taken = 7 / total_pies_per_time
print((time_taken // time_per_pie).sum())
indigo flintBOT
hollow walrus
#

There

#

That's the whole number of pies that will complete

#

If I did / instead of // at the end you'd get 7

hollow walrus
wet seal
#

could you write it without numpy (the judge doesn't support it)

hollow walrus
wet seal
#

oh

#

then I didn't say anything

gentle gale
#

!e

def main():
    N, M = 4, 6
    ovens = [10, 120, 25, 30]
    M += 1

    def T(s):
        returning = 0
        for oven in ovens:
            returning += s / oven
        return returning

    print(M/(T(max(ovens)/max(ovens))))


main()
indigo flintBOT
gentle gale
#

curse you 38.53211009147312

#

ok wow i think i finally managed to recollect my original thiught process while messing with this though

modest zodiac
gentle gale
#

imagine you run the slowest oven in T some amount of times to get to M on its own. you will have massively overshot because of all of the other ovens running concurrently.

as s shrinks in T(s), the terms which no longer "have the time" to run become 0, and so as you shrink s you lose the ovens that you can guarantee dont need to run at all

#

thats where the maximizing T(s)<M comes from

#

suppose some critical value k such that s = k+1 gives s>M and k-1 gives s<M.

you can guarantee any ovens zeroed out by s >= k will not be used at all

then you figure out how many times the slowest oven has to run

then you figure out how far that gsts you

then you repeat the steps for the remaining chunk

#

this was my original thought process

#

so we binary search for the s where T(s)>M, minus 1, M-=T(s), result+=s, repeat probably very few times id guess, then done

#

as for how to fix that binary search

#

my brain is gone and i think i solved it, on paper at least

#

thats good enough for me so im going to sleep

hollow walrus
wet seal
#

it would say if its timeout

hollow walrus
#

Do you know the input for which the answer is wrong?

wet seal
#

it says wrong answer

#

nope...

#

that's the problem

#

and its only 2 inputs from all the test cases

#

if you got some time / energy could you help me at #1307340581009096736 ?

#

its an out of time problen

#

m*

indigo flintBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.