这场题目除了最后一题稍微难了点，其他都是1眼题。
T1 Bike Tour
没啥好说的，一个循环解决。
T2 Bus Routes
没啥好说的，从第(n)的车站开始贪心取最晚的。
T3 Robot Path Decoding
这题也算有点意思吧，但是其实还是挺简单的，大概思路就是用栈模拟一下。
具体步骤
记当前位置位于(<x, y>)，用栈维护一个(<dx, dy>)的序列，表示下一步在两个方向的移动距离。
如果没有数字和括号，这个就是遍历一遍的事情。如果存在数字和括号，就把数字和括号处理掉，然后问题就又变成了遍历一遍的事情了。那么怎么把数字和括号处理掉呢？可以用一个类似括号匹配的过程处理。
- 如果读到数字，就把(<number, INVALID>)压入栈中。INVALID用于表示这是个数字。
- 如果读到字母，就把对应的移动距离压入栈中。
- 如果读到右括号，就不断把栈顶元素拿出，直到拿出的元素是数字。
- 如果是数字，那么把这一段总的移动距离乘上这个数字，再将这一段总的移动距离压入栈中。
- 如果是(<dx, dy>)，那么就把这个点的贡献加到这一段的移动距离上。
T4 Wandering Robot
这题有点意思，就额外写一篇博客把。
T3 AC代码
#include <bits/stdc++.h>
using namespace std;
// #include <ext/rope>
// using namespace __gnu_cxx;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef ll key_type;
// typedef null_mapped_type value_type;
// typedef tree<key_type, value_type, less<key_type>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
// typedef __gnu_pbds::priority_queue<pi,greater<pi>,pairing_heap_tag > heap;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int rnd(int l,int r){return l+rng()%(r-l+1);}
typedef long long ll;
typedef double db;
typedef pair<int,int> PI;
typedef vector<int> VI;
#define rep(i,_,__) for (int i=_; i<=__; ++i)
#define per(i,_,__) for (int i=_; i>= __; --i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define x1 _x
#define x2 __x
#define y1 _y
#define y2 __y
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define endl '
'
const double pi = acos(-1.0);
namespace IO{
bool REOF = 1; //为0表示文件结尾
inline char nc() {
static char buf[1 << 20], *p1 = buf, *p2 = buf;
return p1 == p2 && REOF && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? (REOF = 0, EOF) : *p1++;
}
template<class T>
inline bool read(T &x) {
char c = nc();bool f = 0; x = 0;
while (c<'0' || c>'9')c == '-' && (f = 1), c = nc();
while (c >= '0'&&c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = nc();
if(f)x=-x;
return REOF;
}
template<class T>
inline void write(T x){
if(x > 9) write(x / 10);
putchar('0'+x%10);
}
template<typename T, typename... T2>
inline bool read(T &x, T2 &... rest) {
read(x);
return read(rest...);
}
inline bool need(char &c) { return ((c >= 'a') && (c <= 'z')) || ((c >= '0') && (c <= '9')) || ((c >= 'A') && (c <= 'Z')) || (c==')') || (c=='('); }
// inline bool need(char &c) { return ((c >= 'a') && (c <= 'z')) || ((c >= '0') && (c <= '9')) || ((c >= 'A') && (c <= 'Z')) || c==' '; }
inline bool read_str(char *a) {
while ((*a = nc()) && need(*a) && REOF)++a; *a = ' ';
return REOF;
}
inline bool read_db(double &x){
bool f = 0; char ch = nc(); x = 0;
while(ch<'0'||ch>'9') {f|=(ch=='-');ch=nc();}
while(ch>='0'&&ch<='9'){x=x*10.0+(ch^48);ch=nc();}
if(ch == '.') {
double tmp = 1; ch = nc();
while(ch>='0'&&ch<='9'){tmp=tmp/10.0;x=x+tmp*(ch^48);ch=nc();}
}
if(f)x=-x;
return REOF;
}
template<class TH>
inline void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA>
inline void _dbg(const char *sdbg, TH h, TA... a) {
while(*sdbg!=',')cerr<<*sdbg++;
cerr<<'='<<h<<','<<' '; _dbg(sdbg+1, a...);
}
template<class T>
ostream &operator<<(ostream& os, vector<T> V) {
os << "[ "; for (auto vv : V) os << vv << ","; return os << " ]";
}
template<class T>
ostream &operator<<(ostream& os, set<T> V) {
os << "[ "; for (auto vv : V) os << vv << ","; return os << " ]";
}
template<class T>
ostream &operator<<(ostream& os, map<T,T> V) {
os << "[ "; for (auto vv : V) os << vv << ","; return os << " ]";
}
template<class L, class R>
ostream &operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.x << "," << P.y << ")";
}
#ifdef BACKLIGHT
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#endif
}
using namespace IO;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const int MAXV = 1e6 + 5;
const int MOD = 1e9; // 998244353 1e9+7
const int INF = 0x3f3f3f3f; // 1e9+7 0x3f3f3f3f
const ll LLINF = 0x3f3f3f3f3f3f3f3f; // 1e18+9 0x3f3f3f3f3f3f3f3f
const double eps = 1e-8;
// int dx[4] = { 0, 1, 0, -1 };
// int dx[8] = { 1, 0, -1, 1, -1, 1, 0, -1 };
// int dy[4] = { 1, 0, -1, 0 };
// int dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
// ll qp(ll a, ll b) {
// ll res = 1;
// a %= mod;
// assert(b >= 0);
// while(b){
// if(b&1)
// res = res * a % mod;
// a = a * a % mod;
// b >>= 1;
// }
// return res;
// }
// ll inv(ll x) {return qp(x, mod - 2);}
// ll factor[N], finv[N];
// void init() {
// factor[0]=1;
// for(int i=1; i<N; i++) factor[i] = factor[i-1] * i % mod;
// finv[N-1] = qp(factor[N-1], mod - 2);
// for(int i=N-2; i>=0; i--) finv[i] = finv[i+1] * (i+1) % mod;
// }
// ll c(ll n, ll m) {
// return factor[n] * finv[m] % mod * finv[n-m] % mod;
// }
// #define ls (x<<1)
// #define rs (x<<1|1)
// #define mid ((l+r)>>1)
// #define lson ls,l,mid
// #define rson rs,mid+1,r
// #define fore(_, __) for(int _ = head[__]; _; _=e[_].nxt)
// int head[N], tot = 1;
// struct Edge {
// int v, nxt;
// Edge(){}
// Edge(int _v, int _nxt):v(_v), nxt(_nxt) {}
// }e[N << 1];
// void addedge(int u, int v) {
// e[tot] = Edge(v, head[u]); head[u] = tot++;
// e[tot] = Edge(u, head[v]); head[v] = tot++;
// }
/**
* ********** Backlight **********
* 仔细读题
* 注意边界条件
* 记得注释输入流重定向
* 没有思路就试试逆向思维
* 我不打了，能不能把我的分还给我
*/
int n;
char s[2005];
void solve(int Case) {
read_str(s+1); n = strlen(s+1);
stack<pair<ll,ll> > stk;
rep(i, 1, n) {
if(s[i]>='2' && s[i]<='9') {
stk.push(mp(s[i]-'0', INF));
continue;
}
if(s[i] == '(') continue;
if(s[i] == 'N') {
stk.push(mp(MOD-1, 0));
continue;
}
if(s[i] == 'S') {
stk.push(mp(1, 0));
continue;
}
if(s[i] == 'E') {
stk.push(mp(0, 1));
continue;
}
if(s[i] == 'W') {
stk.push(mp(0, MOD-1));
continue;
}
if(s[i]==')') {
ll dx = 0, dy = 0;
while(!stk.empty()) {
pair<ll, ll> p = stk.top(); stk.pop();
if(p.se == INF) {
dx = dx * p.fi % MOD;
dy = dy * p.fi % MOD;
stk.push(mp(dx, dy));
break;
}
else {
dx = ((dx + p.fi) % MOD + MOD) % MOD;
dy = ((dy + p.se) % MOD + MOD) % MOD;
}
}
}
}
ll x = 0, y = 0;
while(!stk.empty()) {
pair<ll, ll> p = stk.top(); stk.pop();
x = ((x + p.fi) % MOD + MOD) % MOD;
y = ((y + p.se) % MOD + MOD) % MOD;
}
printf("Case #%d: %lld %lld
", Case, y+1, x+1);
}
int main()
{
#ifdef BACKLIGHT
freopen("in.txt", "r", stdin);
#endif
// ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int _T; read(_T); for (int _ = 1; _ <= _T; _++) solve(_);
// int _T=1; while(read(n)) solve(_T), _T++;
// solve(1);
return 0;
}