#include #include #include #include #include #include std::vector split( const std::string & startline , const std::string & sep ) { std::vector separated ; std::string::size_type start { 0 } ; std::string::size_type pos ; do { pos = startline.find_first_of( sep , start ) ; separated.push_back( startline.substr(start , pos - start )) ; start = pos + 1 ; } while ( pos != std::string::npos ) ; return separated ; } //given a certain minute, find the next bus departures, sorted by time of //departure. Every entry contains the number of the busline and its departure std::vector> findNextDepartures( int minute , const std::vector> & schedule ) { int len = schedule.size( ) ; std::vector> departures ; for ( int i = 0 ; i < len ; i++ ) { int depart = schedule[i][1] ; while ( depart < minute ) { depart += schedule[i][0] ; } departures.push_back( std::make_pair( i , depart )) ; } std::sort( departures.begin( ) , departures.end( ) , []( const auto & p1 , const auto & p2 ) { return p1.second < p2.second ; } ) ; return departures ; } //find the arrival times of the buses in the order of their start std::vector findArrivals( const std::vector> & schedule , const std::vector> & departures ) { std::vector arrivals ; for ( auto it = departures.begin( ) ; it != departures.end( ) ; ++it ) { int arri = it->second + schedule[it->first][2] ; arrivals.push_back( arri ) ; } return arrivals ; } //at a given minute , should I let a bus pass ? yes, if the second bus arrives //strictly sooner, provided 2 buses don't leave at the same time and don't //arrive at the same time bool let_pass_one( int minute , const std::vector> & schedule ) { std::vector> next_departures = findNextDepartures( minute , schedule ) ; std::vector arrivals = findArrivals( schedule , next_departures ) ; if ( (next_departures[0].second != next_departures[1].second) && (arrivals[0] > arrivals[1] ) ) return true ; else return false ; } int main( ) { std::cout << "Please enter some bus schedules ( 3 numbers per line ) !\n" ; std::cout << "Enter to end!\n" ; std::string line ; std::vector allLines ; std::getline( std::cin , line ) ; while ( line.length( ) > 0 ) { allLines.push_back( line ) ; std::getline( std::cin , line ) ; } std::vector> schedule ; for ( auto & l : allLines ) { std::vector aLine { split( l , " " ) } ; std::vector numbers ; for ( auto & w : aLine ) numbers.push_back( std::stoi( w ) ) ; schedule.push_back( numbers ) ; } std::vector result ; for ( int i = 0 ; i < 60 ; i++ ) { if ( let_pass_one( i , schedule ) ) result.push_back( i ) ; } std::cout << "[ " ; std::copy( result.begin( ) , result.end( ) , std::ostream_iterator( std::cout , " " ) ) ; std::cout << "]\n" ; return 0 ; }