Wednesday, 08 December, 2021

Rifat's Blog

Competitive Programming Notebook

single post

  • Home
  • Lightoj-1051 Good or Bad
DP, LightOJ, Solve By OJ, Solve By Topic

Lightoj-1051 Good or Bad

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;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

Created by Abu Rifat Muhammed Al Hasib
2021 © All rights reserved


error: Alert: Content is protected !!