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"; }};