Return to Answer

added 209 characters in body

Source Link

edited Oct 9, 2014 at 17:11

34.9k
13
133
237

The guy with the highest workload could do a max of sqrt(200)=14sqrt(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.

So tryTry 13... 200-(13*13)=31 for the other 3 ... and then check the next guy recursively. This, which gives the following code:

    find_worst_hours( 200, 4 );

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

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

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.

So try 13... 200-(13*13)=31 for the other 3 ... and then check the next guy recursively. This gives the following code:

    find_worst_hours( 200, 4 );

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

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:

find_worst_hours( 200, 4 );

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

Source Link

created Oct 9, 2014 at 14:42

Novicaine

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.

So try 13... 200-(13*13)=31 for the other 3 ... and then check the next guy recursively. This 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.