Guys,how did u solve the problem C?I am unable to understand the editorial.Any kind of help would be appreciated
I wrote my own parser function which solved it using recursion
My code
bool isDigit(char a){
return a >= '0' && a <= '9';
}
long long int parseNumber(string &a, int &i){
ll num = 0;
while(isDigit(a[i])){
num = num*10%inf;
num = (num + a[i]-'0')%inf;
i++;
}
return num;
}
pair<ll,ll> parser(string &a, int &i){
pair<ll,ll> change(0,0);
ll j;
while(i < a.size()){
if(isdigit(a[i]))j = parseNumber(a,i);
if(a[i] == '('){
i++;
auto k = parser(a,i);
change.first = (change.first + j*k.first%inf)%inf;
change.second = (change.second + j*k.second%inf)%inf;
debug(i,j,change);
}
else if(a[i] == ')'){
i++;
debug(i,change);
return change;
}
else{
if(a[i] == 'N')
change.second = (change.second-1+inf)%inf;
if(a[i] == 'S')
change.second = (change.second+1)%inf;
if(a[i] == 'E')
change.first = (change.first+1)%inf;
if(a[i] == 'W')
change.first = (change.first-1+inf)%inf;
i++;
}
}
debug(change);
return change;
}
void solve(int test_case){
cout << "Case #" << test_case << ": ";
string a;
cin>> a;
debug(a);
int i = 0;
auto k = parser(a,i);
k.F+=1;
k.S+=1;
cout << k.F << " " << k.S << "\n";
}
1 Like
First, you need to just see that no matter the order of the moves finally you will reach the same position even if the order changes so, for each letter you can find out the number of repetitions by creating a stack and as soon as you receive a number the number is put into the stack and for a letter the number of repetition is the product of all the number in the stack modulo 10^9 now if you reach a “)” you remove the topmost element in the stack and so on.
Finally you can calculate the change in the positions.And you receive the answer.
Here is my code
1 Like
I used stack to calculate the number of times each direction was used. (you can solve a similar in spoj CODE:MMASS)
Then simply subtract south-north and east-west (taking mod 10^9) . add 1 to both and print.
1 Like
Thanks man! It was a nice explanation
1 Like
If u need python code 
import sys
readline = sys.stdin.readline
flush = sys.stdout.flush
T = int(readline().strip())
nums = set([str(_) for _ in range(10)])
N = 10**9
for t in range(1, T+1):
program = readline().strip()
cur = [0, 0]
stack = []
for char in program:
if char == 'N':
cur[0] -= 1
elif char == 'S':
cur[0] += 1
elif char == 'W':
cur[1] -= 1
elif char == 'E':
cur[1] += 1
elif char in nums:
stack.append((cur[0], cur[1], int(char)))
elif char == '(':
cur = [0, 0]
elif char == ')':
pop = stack.pop()
cur[0]=pop[0]+pop[2]*cur[0]
cur[1]=pop[1]+pop[2]*cur[1]
final_row = (1+cur[0])%N
if final_row == 0:
final_row = N
final_column = (1+cur[1])%N
if final_column == 0:
final_column = N
print("Case #%d: %d %d" % (t, final_column, final_row))
1 Like
A similar solution to this Long Challenge’s REBIT. Created a structure that holds value for North, East , West , South moves and defined Add and Multiply operations.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const ll mod = 1e9;
const db eps = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;
#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl
struct dir
{
ll north, east, west, south;
dir(ll _n , ll _e , ll _w , ll _s) : north(_n), east(_e), west(_w), south(_s) {}
};
dir add (const dir& dir1, const dir& dir2)
{
return dir( (dir1.north+dir2.north)%mod , (dir1.east+dir2.east)%mod , (dir1.west+dir2.west)%mod , (dir1.south+dir2.south)%mod ) ;
}
dir mul (const ll m, const dir& dir2)
{
return dir( (m*dir2.north)%mod , (m*dir2.east)%mod , (m*dir2.west)%mod , (m*dir2.south)%mod ) ;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
ll t;
cin >> t;
for(ll i=1 ; i<=t ; ++i)
{
cout << "Case #" << i << ": ";
string s;
cin >> s;
stack<int> numbers;
stack<char> characters;
stack<dir> directions;
ll north =0 ,west = 0,east = 0,south = 0;
for(ll i=0 ; i<s.size() ; ++i)
{
if( s[i] >= '1' && s[i] <= '9') numbers.push(s[i]-'0');
else if( s[i] == '(') characters.push( s[i] );
else if( s[i] == ')' )
{
char c = characters.top();
characters.pop();
dir ans = dir(0,0,0,0);
while(c!='(')
{
ans = add(ans,directions.top());
directions.pop();
c = characters.top();
characters.pop();
}
ll multiplier = numbers.top();
numbers.pop();
ans = mul( multiplier , ans );
characters.push('#');
directions.push(ans);
}
else
{
characters.push( '#' );
if(s[i] == 'N') directions.push( dir(1,0,0,0) );
if(s[i] == 'E') directions.push( dir(0,1,0,0) );
if(s[i] == 'W') directions.push( dir(0,0,1,0) );
if(s[i] == 'S') directions.push( dir(0,0,0,1) );
}
}
dir ans = dir(0,0,0,0);
while( !directions.empty() )
{
dir hey = directions.top();
directions.pop();
ans = add(ans,hey);
}
if(ans.east - ans.west >= 0)
cout << 1 + (ans.east-ans.west)%mod << " " ;
else
cout << (ll)1e9 - (ans.west - ans.east - 1)%mod << " " ;
if(ans.south - ans.north >= 0)
cout << 1 + (ans.south-ans.north)%mod << endl ;
else
cout << (ll)1e9 - (ans.north - ans.south - 1)%mod << endl ;
}
return 0;
}
1 Like