Lightoj-1051 Good or Bad

L
Problem NameGood or Bad
JudgeLightoj
Problem Linkhttps://lightoj.com/problem/good-or-bad
Algorithms & DSDynamic Programming
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); string s; ll n; ll mem[52][5][8]; map<char,ll>mp; ll dp(ll i,ll vo,ll con,ll ck_mix) { if(vo>2)return 1; if(con>4)return 1; if(i>=n) { return 0; } if(mem[i][vo][con]!=-1) { return mem[i][vo][con]; } ll ans=0; if(s[i]=='?') { ll tm_ans_vo=dp(i+1,vo+1,0,ck_mix); ll tm_ans_con=dp(i+1,0,con+1,ck_mix); if(ck_mix==0) { ans=tm_ans_vo&tm_ans_con; } else { ans=tm_ans_vo|tm_ans_con; } } else { if(mp[s[i]]==1) { ans=dp(i+1,vo+1,0,ck_mix); } else { ans=dp(i+1,0,con+1,ck_mix); } } return mem[i][vo][con]=ans; } int main() { mp['A']=1; mp['E']=1; mp['I']=1; mp['O']=1; mp['U']=1; fast; ll tcase=1; cin>>tcase; for(ll test=1; test<=tcase; test++) { cin>>s; n=s.size(); ll vo=0,con=0,good=1,ase=0; for(ll i=0; i<n; i++) { if(s[i]!='?') { if(mp[s[i]]==1) { vo++; con=0; } else { con++; vo=0; } if(vo>2||con>4) { good=0; } } else { ase=1; vo=0; con=0; } } if(ase) { if(good==0) { cout<<"Case "<<test<<": BAD"<<"\n"; } else { for(ll i=0; i<=n; i++) { for(ll j=0; j<4; j++) { for(ll k=0; k<6; k++) { mem[i][j][k]=-1; } } } ll ans=dp(0,0,0,0); if(ans) { cout<<"Case "<<test<<": BAD"<<"\n"; } else { for(ll i=0; i<=n; i++) { for(ll j=0; j<4; j++) { for(ll k=0; k<6; k++) { mem[i][j][k]=-1; } } } ans=dp(0,0,0,1); if(ans) { cout<<"Case "<<test<<": MIXED"<<"\n"; } else { cout<<"Case "<<test<<": GOOD"<<"\n"; } } } } else { if(good) { cout<<"Case "<<test<<": GOOD"<<"\n"; } else { cout<<"Case "<<test<<": BAD"<<"\n"; } } } return 0; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!