Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define X first
#define Y second

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;

const int INF = 1e9;


int main(){
	int ans = INF;
	int n, w, d;
	vector<pair<int,pii> > vr;

	cin >> n >> w >> d;
	int N = 2*(w+d);
	rep(i,n){
		int x, y;
		char f;
		cin >> x >> y >> f;
		int l, r;
		if( f == 'W' ){
			l = 2*w + d - x + y;
			r = N + x - d + y;
		}
		if( f == 'E' ){
			l = x + d - y;
			r = 2*w + d - x - y;
		}
		if( f == 'N' ){
			l = 2*w + d + y + x;
			r = N + d - y + x;
		}
		if( f == 'S' ){
			l = 2*w + d - y - x;
			r = 2*w + d + y - x;
		}
		//cout << l << " " << r << endl;
		for(;r<5*N; r+=N, l+=N){
			vr.eb( r, pii(i, l) );
		}
	}
	sort( all(vr) );

	int start=N-1;
	rep(i,n+1){
		int cl = 0;
		auto cur = vr.begin();
		while( cur->X < start ) cur++;
		start = max(start+1, cur->X);
		int cnt = 0, sum = 0;
		bool f[1005] = {};
		for(;cnt < n; cur++){
			int r  = cur->X;
			int id = cur->Y.X;
			int l  = cur->Y.Y;
			if( f[id] ) continue;
			if( cl < l ){
				cl = r;
				sum++;
			}
			f[id] = true;
			cnt++;
		}
		ans = min(ans, sum);
	}

	cout << ans << endl;
}