Problem My approach was to keep the multiplication factors in stack and pop them when a bracket ends
code
Please Help I am unable to find the mistake
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Problem My approach was to keep the multiplication factors in stack and pop them when a bracket ends
//JSD
#include<iostream>
#include<map>
#include<stack>
#define ll long long
#define Maxx (long long)1e9
using namespace std;
void solve(int test){
string s;
cin>>s;
int n=s.length();
stack<int> st;
int factor=1;
map<char, int > m;
for(int i=0;i<n;i++){
if(isdigit(s[i])){
st.push(int(s[i]-'0'));
factor*=int(s[i]-'0');
}
if(s[i]==')'){
int x=st.top();
st.pop();
factor/=x;
}
if(isalpha(s[i])){
m[s[i]]+=factor;
}
}
ll x=0,y=0;
x=(x+m['S'])%Maxx;
x=(x-m['N']+Maxx)%Maxx;
y=(y+m['E'])%Maxx;
y=(y-m['W']+Maxx)%Maxx;
cout<<"Case #"<<test<<": "<<y+1<<" "<<x+1<<"\n";
}
int main(){
ll t;
cin>>t;
int test=1;
while(t--){
solve(test);
test++;
}
return 0;
}
Please Help I am unable to find the mistake
Name |
---|
The value of factor will most probably overflow if it is something like 9(9(9(9(9(9.........)))
so how can I deal with it, I thought of using modular arithmatic while contest but got stuck in the fact that fermat's theorem can't be applied to non prime numbers for taking mod so how actually we can handle that. thanks for replying
Fermat's little theorem only comes into play when computing modulo inverse. There are no divisions, so it doesn't really matter if the value you've to take modulo by is prime or not.
actually I had divided the factor value by the top of stack but now I have changed my code a bit and removed division part by recalculating the factor value each time it is needed
and it is still giving me wrong answer on second test case
In your submission
1 factor should be long long
2 value of map mp should be long long
I solved it using modular arithmetic.
There are only additions and multiplications. Why would you need Fermat's theorem?
Now I have changed the code using addition and multiplications but still getting a WA earlier I used division in my logic that's why I needed fermat's theorem Please review the code in my previous comment
you could keep a stack of values instead of doing division you can just go back to the previous value, Example you encounter 2(9(..)).
You append into your stack [1, 2, 18] as we encounter them in 2 .. 9 order, then after 9's parenthesis is closed you can just pop the 18 and go back to using 2, no need of division.
Thank you
My approach : Total digits will be at max 500 since each digit will be linked with at least 2 parenthesis and one char. So there are total 500digits. Just brute them every time you encounter ')', do some arithmetic, count frequency of each char. complexity will be (n^2 + m) where n is 500 and m is length of string. AC code https://ideone.com/qXVQCT
ok thanks , got it