Topcoder SRM 514 Div2(Easy) MagicalGirlLevelTwoDivOne

https://community.topcoder.com/stat?c=problem_statement&pm=11476

N <= 50

ai <= 10^9 (1 <= i <= N)

-10^9 <= x,y <= 10^9

일때, 체스에서 knight 는 한쪽방향으로 1칸, 그리고 그에 수직한 축에서 한쪽방향으로 2칸을 가는데, 2칸대신 N 칸을

가는것을 N-knight jump 라고 부를 때, 플레이어는 ai-knight 점프 들을 매 순간마다 할 수 있을 때

(0,0) 에서 (x,y) 로 갈 수 있는 지 없는지 판단하는 문제이다.

조금만 생각을 해보면 N이 몇이던 (하나의 N에 대해) N-knight jump를 2번 하여 결과적으로

처음에 있던 곳으로부터 한쪽 방향으로 2만큼 이동하는 것이 가능하다는 것을 알 수가 있다.

그렇다면 N-knight jump 만으로 간 곳은 (N-2)-knight jump 만으로도 갈 수가 있다는 것을 알 수가 있고, 반대로

(N-2)-knight jump 만으로 간 곳은 N-knight jump 만으로도 갈 수가 있다는 것을 알 수가 있다.

그럼 결국 짝수인 N에 대해서 N-knight jump만으로 갈 수 있는 곳은 2-knight jump 만으로 갈 수 있고

홀수인 N에 대해서 N-knight jump만으로 갈 수 있는 곳은 1-knight jump 만으로 갈 수가 있기 때문에 

1-knight jump 와 2-knight jump 로 치환이 가능하다.

그리고 2-knight jump 는 기준점으로 부터 3번 점프해서 갈 수 있는 곳을 모두 표시해 보면 기준점 주변의

8가지 방향 모두로 갈 수 있다는 것을 알 수 있기 때문에 2-knight jump 로는 모든 곳을 갈 수 있다는 것이 되고

즉, 짝수-knight jump 만으로 모든 좌표로 이동이 가능하다는 것을 알 수 있게 된다.

그렇다면 1-knight jump 는 어떨까? 1-knight jump로 갈 수 있는 곳을 조금 그려보면 격자 모양으로 밖에 갈 수가

없다는 것을 알 수가 있게 되고 이것은 원점에서 출발하여 x+y 가 짝수인 점으로 밖에 가지 못한다는 것을 알 수가

있게 된다. 즉, 홀수-knight jump 로는 x+y 가 짝수인 모든 좌표로 이동이 가능하다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
class MagicalGirlLevelOneDivOne {
    public:
    string isReachable(vector<int> jumpTypes, int x, int y) {
        bool poss = false;
        for(int i = 0 ; i < jumpTypes.size(); i++){
            if(jumpTypes[i]%2==0) poss = true;
            else if((x+y)%2==0) poss = true;
        }
        return poss ? "YES" : "NO";
    }
};