Help in third problem of google kickstart round B

Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

→ Обратите внимание

До соревнования
Codeforces Round 977 (Div. 2)
2 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Number Theory - Topic Stream

Shayan

До начала 08:31:31

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Um_nik	164
2	-is-this-fft-	160
2	maomao90	160
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя nipul1

Help in third problem of google kickstart round B

Автор nipul1, история, 4 года назад, По-английски

Problem My approach was to keep the multiplication factors in stack and pop them when a bracket ends

code

//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

#googlekickstart, #stack

nipul1
4 года назад
13

Комментарии (11)

Показать архивные | Написать комментарий?

kabeer27

4 года назад, # |

The value of factor will most probably overflow if it is something like 9(9(9(9(9(9.........)))

→ Ответить

nipul1

4 года назад, # ^ |

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

→ Ответить

CoderPenguin

4 года назад, # ^ |

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.

→ Ответить

nipul1

4 года назад, # ^ |

← Rev. 2 →

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

code

//JSD
#include<iostream>
#include<map>
#include<vector>
#define ll long long 
#define Maxx (long long)1e9
using namespace std;
void solve(int test){
	string s;
	cin>>s;
	int n=s.length();	
	int factor=1;
	map<char, int > m;
	vector<int > st;	
	for(int i=0;i<n;i++){		
		if(isdigit(s[i])){
			st.push_back(int(s[i]-'0'));			
		}
		if(s[i]==')'){
			int x=st.back();
			st.pop_back();			
		}
		if(isalpha(s[i])){
			factor=1;
			for(auto x: st){
				factor=(factor*x)%Maxx;
			}
			m[s[i]]=(m[s[i]]+factor)%Maxx;
		}
	}
	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;
}

and it is still giving me wrong answer on second test case

→ Ответить

ma_da_fa_ka

4 года назад, # ^ |

← Rev. 2 →

In your submission

1 factor should be long long

2 value of map mp should be long long

→ Ответить

BumbleBee

4 года назад, # ^ |

I solved it using modular arithmetic.
There are only additions and multiplications. Why would you need Fermat's theorem?

→ Ответить

nipul1

4 года назад, # ^ |

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

→ Ответить

kabeer27

4 года назад, # ^ |

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.

→ Ответить

nipul1

4 года назад, # ^ |

Thank you

→ Ответить

ma_da_fa_ka

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

nipul1

4 года назад, # ^ |

← Rev. 2 →

ok thanks , got it

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 04.10.2024 06:28:29 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке