UVa 617 - Nonstop Travel

Problem link

Keyword: brute force, modulo

Algorithm:

Scan through 30 mph to 60 mph, and use an array to record which speed can be used.
A certain speed is said to be OK if no red light is encountered in the way, and use a for loop and mod operator to check that.
After the scan, output the speed value or range as specified.

Note:

1. Notice the moment when yellow light turned to red.
2. Since the position is a floating number, you have to use fmod() for mod operation.

Code:

#include<cstdio>
#include<cmath>
#include<algorithm>

int main()
{
    int light, t = 0, g[ 6 ], y[ 6 ], r[ 6 ];
    double loc[ 6 ];

    while( scanf( "%d", &light ) && light != -1 )
    {
        bool invalid[ 61 ] = { false };
        int out = 0;

        for( int i = 0; i < light; ++i )
            scanf( "%lf %d %d %d", loc+i, g+i, y+i, r+i );
        for( int speed = 30; speed <= 60; ++speed )
            for( int i = 0; i < light; ++i )
                if( fmod( loc[ i ] * 3600 / speed, g[ i ] + y[ i ] + r[ i ] ) > g[ i ] + y[ i ] )
                    invalid[ speed ] = true;

        printf( "Case %d:", ++t );
        for( int i = 30; i <= 60; ++i )
            if( !invalid[ i ] )
            {
                int end = std::find( invalid+i, invalid+61, true ) - invalid;
                if( i == end-1 )
                    printf( " %d", i );
                else
                    printf( " %d-%d", i, end-1 ), i = end;
                putchar( std::find( invalid+end, invalid+61, false ) == invalid+61? '\n' : ',' );
                ++out;
            }
        if( !out )
            puts( " No acceptable speeds." );
    }

    return 0;
}