SRM538 Div1 Easy(250), Div2 Medium(500) EvenRoute

EvenRoute

x+yが偶数の点を偶、奇数の点を奇とする。偶の点が1個でもあるならば、スタート地点と各点を往復して、最後に偶の点に行けば、パリティを0にできる。また、偶の点が無いならば、最初の移動でパリティが1になり、その後どのように移動してもパリティは1のまま。よって、パリティを0にできることと、偶の点が1個でもあることは同値。同様にして、パリティを1にできることと、奇の点が1個でもあることが同値だと分かる。

#include <string>
#include <vector>
using namespace std;

class EvenRoute{public:
string isItPossible( vector <int> x, vector <int> y, int wantedParity )
{
    bool even = false;
    bool odd = false;
    for ( int i=0; i<(int)x.size(); i++ )
        if ( (x[i]+y[i])%2==0 )
            even = true;
        else
            odd = true;

    if ( wantedParity==0 && even ||
         wantedParity==1 && odd )
        return "CAN";
    else
        return "CANNOT";
}};