dmansilla07's blog

By dmansilla07, 12 years ago, In English

I submitted this code where I saved all the substrings in a vector v and then i find the next string at my function sig, however in this code sig("azz")="bza" and this is wrong because it should be "baa" however I got accepted. Then i submitted another code where sig("azz")="baa" and I got accepted too. Does anybody know if this case is valid or it is not?

using namespace std;
vector<string>v;
int n;
string s;
map<string,bool>m;
bool comp(string a,string b){
        if(a.length()!=b.length()){
            return a.length()<b.length();
        }
        return a<b;
}

string sig(string mini){
    string r="";
    
    if(mini[mini.length()-1]=='z'){
        bool ok=0;
        for(int i=mini.length()-1;i>=0;i--){
               if(mini[i]!='z'){
                    mini[i]++;
                    ok=1;
                    mini[mini.length()-1]='a';
                    return mini;
                }
        }
        if(!ok){
            for(int i=0;i<=mini.length();i++){
                r+="a";
            }   
        }
        return r;
    }
    else{
        mini[mini.length()-1]++;
        return mini;
    }
}
int main(){
    scanf("%d",&n);
    string mini="a";
    for(int i=0;i<n;i++){
        cin>>s;   
        for(int j=0;j<s.length();j++){
            for(int r=0;r<=s.length();r++){
                if(j+r>s.length())continue;
                string aux=s.substr(j,r);
                if(!m[aux]&&aux.length()>0)v.push_back(aux);
                m[aux]=1;
            }   
        }
    }    
    sort(v.begin(),v.end(),comp);
    string res="";
    if(v[0]!="a"){
        cout<<"a"<<endl;
        return 0;   
    }
    for(int i=0;i<v.size()-1;i++){
        if(v[i+1]!=sig(v[i])&&v[i+1]!=v[i]){
            res=v[i];
            break;
                          
        }
    }
    if(res!=""){
        cout<<sig(res)<<endl;   
    }
    else{
        cout<<sig(v[v.size()-1])<<endl;   
    }
}

In this code i corrected function sig:

string sig(string mini){
    string r="";
    
    if(mini[mini.length()-1]=='z'){
        bool ok=0;
        for(int i=mini.length()-1;i>=0;i--){
               if(mini[i]!='z'){
                    mini[i]++;
                    ok=1;
                    int u=mini.length()-1;
                    while(u>=0&&mini[u]=='z'){
                        mini[u]='a';
                        u--;
                    }
                    return mini;
                }
        }
        if(!ok){
            for(int i=0;i<=mini.length();i++){
                r+="a";
            }   
        }
        return r;
    }
    else{
        mini[mini.length()-1]++;
        return mini;
    }
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it