I'm actually not OK with the assumption that the answer to the hobo question is solving a*a+b*b+c*c+d*d = 200 in an iterative fashion.
I think it is a square root and rounding question that can be solved with a greedy algorithm.
The guy with the highest workload could do a max of sqrt(200) = 14.142 hours for 14.142 days. Rounded down, that'd be 14*14=196, leaving only 4 hours of work for the other 3. That doesn't work.
Try 13... 200-(13*13)=31 for the other 3 and then check the next guy recursively, which gives the following code:
int find_worst_hours( int workleft, int numguys )
{
static int num_interations = 0;
int mine = (int)floor(sqrt((double)workleft));
TRACE( "Num iterations = %d\n", ++num_interations );
while( mine > 0 ) {
int leftover = workleft - mine*mine;
TRACE( "Guys Left %d:I would do %d, rest would do %d\n", numguys, mine, leftover );
if ( numguys == 1 ) {
// last guy
if ( leftover > 0 ) {
return -1; // bad solution, work left over.
} else {
// no work left, this is a good solution.
TRACE( "GOOD END, guy %d, work %d\n", numguys, mine );
return mine;
}
} else {
// check the rest of guys
if ( leftover == 0 ) {
return -1; // bad solution, the other guys need work
}
int next_guys_work = find_worst_hours( leftover, numguys-1 );
if ( next_guys_work > 0 ) {
// valid solution
TRACE( "GOOD PARTIAL, guy %d, work %d\n", numguys, mine );
return mine;
} else {
// couldn't find a solution... try less hours
mine--;
// continue while loop
}
}
}
return -1; // couldn't find solution
}
Which you can call once with:
find_worst_hours( 200, 4 );
And it should output:
Num iterations = 1
Guys Left 4:I would do 14, rest would do 4
Num iterations = 2
Guys Left 3:I would do 2, rest would do 0
Guys Left 4:I would do 13, rest would do 31
Num iterations = 3
Guys Left 3:I would do 5, rest would do 6
Num iterations = 4
Guys Left 2:I would do 2, rest would do 2
Num iterations = 5
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 1, rest would do 5
Num iterations = 6
Guys Left 1:I would do 2, rest would do 1
Guys Left 3:I would do 4, rest would do 15
Num iterations = 7
Guys Left 2:I would do 3, rest would do 6
Num iterations = 8
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 2, rest would do 11
Num iterations = 9
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 1, rest would do 14
Num iterations = 10
Guys Left 1:I would do 3, rest would do 5
Guys Left 3:I would do 3, rest would do 22
Num iterations = 11
Guys Left 2:I would do 4, rest would do 6
Num iterations = 12
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 3, rest would do 13
Num iterations = 13
Guys Left 1:I would do 3, rest would do 4
Guys Left 2:I would do 2, rest would do 18
Num iterations = 14
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 1, rest would do 21
Num iterations = 15
Guys Left 1:I would do 4, rest would do 5
Guys Left 3:I would do 2, rest would do 27
Num iterations = 16
Guys Left 2:I would do 5, rest would do 2
Num iterations = 17
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 4, rest would do 11
Num iterations = 18
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 3, rest would do 18
Num iterations = 19
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 2, rest would do 23
Num iterations = 20
Guys Left 1:I would do 4, rest would do 7
Guys Left 2:I would do 1, rest would do 26
Num iterations = 21
Guys Left 1:I would do 5, rest would do 1
Guys Left 3:I would do 1, rest would do 30
Num iterations = 22
Guys Left 2:I would do 5, rest would do 5
Num iterations = 23
Guys Left 1:I would do 2, rest would do 1
Guys Left 2:I would do 4, rest would do 14
Num iterations = 24
Guys Left 1:I would do 3, rest would do 5
Guys Left 2:I would do 3, rest would do 21
Num iterations = 25
Guys Left 1:I would do 4, rest would do 5
Guys Left 2:I would do 2, rest would do 26
Num iterations = 26
Guys Left 1:I would do 5, rest would do 1
Guys Left 2:I would do 1, rest would do 29
Num iterations = 27
Guys Left 1:I would do 5, rest would do 4
Guys Left 4:I would do 12, rest would do 56
Num iterations = 28
Guys Left 3:I would do 7, rest would do 7
Num iterations = 29
Guys Left 2:I would do 2, rest would do 3
Num iterations = 30
Guys Left 1:I would do 1, rest would do 2
Guys Left 2:I would do 1, rest would do 6
Num iterations = 31
Guys Left 1:I would do 2, rest would do 2
Guys Left 3:I would do 6, rest would do 20
Num iterations = 32
Guys Left 2:I would do 4, rest would do 4
Num iterations = 33
Guys Left 1:I would do 2, rest would do 0
GOOD END, guy 1, work 2
GOOD PARTIAL, guy 2, work 4
GOOD PARTIAL, guy 3, work 6
GOOD PARTIAL, guy 4, work 12
So it took only 33 iterations and we found the answer 2,4,6,12. This should be VERY fast to calculate.
counterdoing? \$\endgroup\$