11633 - Food portion sizes

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Nahiyan Kamal
New poster
Posts: 7
Joined: Sat Apr 04, 2009 6:40 pm

11633 - Food portion sizes

can anyone help me how to solve this problem? i have thought of a solution like this:

S=ax+by

let the food portion size if u

for first person,

i1=amount he needs
x1= amount wasted
y1=how many times he goes to fetch food

x1=u*ceil(i1/u)-i1
y1=ceil(i1/u)

s1=ax1+by1=(au+b)*ceil(i1/u)-a*i1
similarly
s2=(au+b)*ceil(i2/u)-a*i2
s3=(au+b)*ceil(i3/u)-a*i3
.......
S=S1+S2+.....
=(au+b)*(ceil(i1/u)+ceil(i2/u)+ceil(i3/u)+...)-a*(i1+i2+i3+.....)

now S is the ans

we can determine u to get S minimum.(y<=3) but u has to be very accurate so that it can be turned into fractoin (x/y form) brute force will make TLE.

am i correct?
so any idea how to solve this?

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 11633 - Food portion sizes

My model is the same as Nahiyan Kamal's. So, S-the-portion-size is any real number between max{w}/3 and max{w}. We are to find a "good" rational approximation to this optimal size. Nwo, we are not given any tolerance level as to which approximations are good enough. Maybe I'm missing something important from the problem statement, but I'm confused as to how to handle this problem, too.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11633 - Food portion sizes

You can solve it without using floating point. The result will always be an integer / 6.
Check input and AC output for thousands of problems on uDebug!