/* C++ algorithm help I am preparing for the national-wide programming contest after being 4th in the regional. I saw an interesting problem: There are n computers in a row. There are contestants from 3 citied: A, B, and C. If you how many contestants are from each city and where are contestants from A sitting, place the contestants from B and C in that way that two student form the same city cannot stay one to other. If there is no answer output -1 Example: 3 2 2(number of students from each city) 2 5 7(positions of the students from A) Output: BABCACA */ #include #include int main( int, char** ) { // number of participants of team A, B, and C unsigned a{}; unsigned b{}; unsigned c{}; std::cin >> a >> b >> c; // total number of participants unsigned total{ a + b + c }; // positions of team A unsigned *arr{ new unsigned[ a ]{} }; // get positions of team A for ( std::size_t _i{ 0 }; _i < a; ++_i ) { std::cin >> arr[ _i ]; // check for invalid position if ( arr[ _i ] < 1 || arr[ _i ] > total ) { std::cerr << "Invalid position!\n"; delete [] arr; return EXIT_FAILURE; } } // sort positions just in case std::sort( arr, arr + a ); // determine smaller and bigger team size between B and C unsigned upper{ std::max( b, c ) }; unsigned lower{ std::min( b, c ) }; // number of ranges to be filled unsigned partitions{ a + 1 }; // number of ranges that require contestants of the smaller team unsigned count{}; // search for neighbours in team A // and count large partitions for ( std::size_t _i{ 0 }; _i < a - 1; ++_i ) { if ( arr[ _i + 1 ] - arr[ _i ] <= 1 ) { std::cout << -1; delete [] arr; return EXIT_SUCCESS; } else if ( arr[ _i + 1 ] - arr[ _i ] - 1 > lower ) { ++count; } } // account for left edge if ( arr[ 0 ] == 1 ) { --partitions; } else if ( arr[ 0 ] - 1 > lower ) { ++count; } // account for right edge if ( arr[ a - 1 ] == total ) { --partitions; } else if ( total - arr[ a - 1 ] > lower ) { ++count; } // determine possibility of combination if ( upper > partitions + lower || count > lower ) { std::cout << -1; delete [] arr; return EXIT_SUCCESS; } char last{ 'A' }; // construct possible combination for ( std::size_t _i{ 0 }, _j{ 0 }; _i < total; ++_i ) { if ( arr[ _j ] == _i + 1 ) { last = 'A'; ++_j; } else if ( last == 'A' ) { if ( c <= b ) { last = 'B'; --b; } else { last = 'C'; --c; } } else if ( last == 'B' ) { last = 'C'; --c; } else if ( last == 'C' ) { last = 'B'; --b; } std::cout << last; } delete [] arr; return EXIT_SUCCESS; }

[Q&A] Seat Combination