I just cin every string and then solve using it. 0.156 accepted

delete

Edited by author 04.10.2020 16:38

outputon

YES

Edited by author 28.08.2018 23:32

If in the line "outputon", this does not mean that you need to put "out" and "puton", since sometimes you can put "output" and "one".

Сheck out this test:
1
outputone
Answer : "YES"

Perhaps this will help you.

Edited by author 01.11.2017 18:28

Edited by author 01.11.2017 18:29

Don't use cin(TL1) and getc(WA1), use scanf and get AC:

char s[(int)1e7];
scanf("%s", &s);
length = strlen(s);

There only 10 situations!!!!!
//1. in
//2. input
//3. inputon
//4. inputone

//5. out
//6. output
//7. outputon
//8. outputone

//9. puton
//10. one

Check their in inverse order.

   bool check(char const* s){
        while(*s != '\n'){
               if (s == "one") s += 3;
              // there s == "one" only pseudocode, you may check
             //  as memcmp(s, "one",3) == 0
               else  // ......

               //.............

               // 10 times else
               else if (s == "in") s +=2;
               else
                  return false;
         }
        return true;
   }

I don't know why my O(N) solution is crashing on 1st test.

Code on C++11: http://ideone.com/BZIoKv

Maybe I don't know some disadvantages of C++? Or it's my algorithm error?

I always get ML, and i cant understand what sould i do?

I tried to use Scanner and BufferedReader.

Please tell me method to solve this.

My solution using DFA works half a second.
In the ranking of many solve the problem for 0.1 second. How?

Help please)! Why WA 1? I check my Pascal code and the answer is right!

I read 3 chars and run the follow DFA:
                one on in/out put
lost:
empty:
in/out:
input/output:
put:

here is my code:

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <string>

using namespace std;

inline bool good(char C)
{
    return (C >= 'a' && C <= 'z');
}

int a[5][4] = {{0, 0, 0, 0},
               {1, 0, 2, 4},
               {1, 0, 2, 3},
               {1, 1, 2, 4},
               {0, 1, 0, 0}};

char c[3];

bool get_ans()
{
    int n_u = 0, pos = 1;

    if (!good(c[2])) {
        return (c[0] == 'i' && c[1] == 'n');
    }

    bool n2 = 0;
    while (true)
    {
        if (pos == 0) return 0;
        if (n2) return (pos != 0 && pos != 4);

        c[0] = c[n_u % 3];

        for (int i = 3 - n_u; i < 3; i++)
        {
            c[i] = getc(stdin);
            if (!good(c[i])) {
                if (i == 0) return (pos != 0 && pos != 4);
                if (i == 1) return 0;
                n2 = 1;
                break;
            }
        }


        if (!n2 && c[0] == 'o' && c[1] == 'n' && c[2] == 'e') {
            pos = a[pos][0];
            n_u = 3;
            continue;
        }

        if (c[0] == 'o' && c[1] == 'n') {
            pos = a[pos][1];
            n_u = 2;
            continue;
        }

        if (!n2 && c[0] == 'o' && c[1] == 'u' && c[2] == 't') {
            pos = a[pos][2];
            n_u = 3;
            continue;
        }

        if (c[0] == 'i' && c[1] == 'n') {
            pos = a[pos][2];
            n_u = 2;
            continue;
        }

        if (!n2 && c[0] == 'p' && c[1] == 'u' && c[2] == 't') {
            pos = a[pos][3];
            n_u = 3;
            continue;
        }
        return 0;
    }
}

int main()
{
//    assert(freopen("inp.in", "r", stdin) != NULL);

    int n; assert(scanf("%d", &n) == 1);

    c[0] = getc(stdin);

    for (int i = 0; i < n; i++)
    {
        bool ok = 0;
        c[0] = getc(stdin);

        if (good(c[0])) {
            c[1] = getc(stdin);
            if (good(c[1])) {
                c[2] = getc(stdin);
                ok = get_ans();
            } else {
                ok = 0;
            }
        }

        if (ok) printf("YES\n");
        else printf("NO\n");
    }
}

Edited by author 10.12.2013 21:13

Edited by author 10.12.2013 21:15

Edited by author 10.12.2013 21:22

"(one|puton|out|output|in|input)+"
it has simple solve using regexp, but i got ML 1. How to read correctly?

Edited by author 18.09.2013 18:24

#include <iostream>
#include <cstdlib>
#include <stdio.h>
//#pragma comment(linker, "/STACK:16777216")


using namespace std;

int flag=0;
int flag1=0;
char *a = new char [10000001];


  int f(int pos,int flag,int n){
    int l=0;
    if ((pos==n+1) && (flag==1)) {std::cout<<"YES"<<endl; flag1=1; return 0;}
    if ((pos==n+1) && (flag==0)) {}
    else if (pos<=n){
    {if ((a[pos]=='o') && (a[pos+1]=='u') && (a[pos+2]=='t') && (a[pos+3]=='p') && (a[pos+4]=='u') && (a[pos+5]=='t')) {f(pos+6,1,n);l=1;}
    if ((a[pos]=='i') && (a[pos+1]=='n') && (a[pos+2]=='p') && (a[pos+3]=='u') && (a[pos+4]=='t')) {f(pos+5,1,n);l=1;}
    if ((a[pos]=='p') && (a[pos+1]=='u') && (a[pos+2]=='t') && (a[pos+3]=='o') && (a[pos+4]=='n')) {f(pos+5,1,n);l=1;}
    if ((a[pos]=='o') && (a[pos+1]=='u') && (a[pos+2]=='t')) {f(pos+3,1,n);l=1;}
    if ((a[pos]=='o') && (a[pos+1]=='n') && (a[pos+2]=='e')) {f(pos+3,1,n);l=1;}
    if ((a[pos]=='i') && (a[pos+1]=='n')) {f(pos+2,1,n);l=1;}
    if (l==0) {}
    }}
}



int main()
{
    int k=0,n=0,j=0;
    int i=0;
    std::cin>>k;
    char c;
    for (j=1;j<=k+1;j++)
    {
        i=0; flag1=0;
        while (((c = getchar()) != '\n') ) {a[i]=c;i++;}
        n=i-1;

       if (n>0) {
                 f(0,0,n);
                  if (flag1==0) std::cout<<"NO"<<endl;}

    }




}

Edited by author 11.07.2013 23:48

Edited by author 11.07.2013 23:49

#include<iostream.h>
#include<string.h>
using namespace std;
int main()
{
    int number;
    cin>>number;
    string s;
    int i=0;
    for(;i<number;i++)
    {
       cin>>s;
       std::size_t find=s.find("puton");
       std::size_t find1=s.find("one");
       if((find != std::string::npos)||(find1 != std::string::npos))
       cout<<"YES\n";
       else
       cout<<"NO";
       s.clear();
    }
    //system("pause");
    return 0;
}

For those who solved this in Java with a lots of tricks. Thumbs up!

Take a look at P1148. It's really similar. E.g. simple DP problem, which becomes stick in ass with Time + Memory limits :)

I just don't get why this task has kindof 'small' difficulty, and P11048 has 'large' difficulty.

I'd say this was much more harder than P1148 for me to get AC in Java.

Reading by Console.Readline() or Console.ReadToEnd gets Memory Limit, reading by Console.Read() gets Time Limit.
Is there any other way to read without getting MLE and TLE?

Hello, please can some one tell me what is wrong with my program.
I use DFA and read the strings from end of the string to start. But it always gets WA 1.
:(



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

////////////State Class/////////////////////////////////
class State{
    byte label;
    boolean isAccepting;
    ArrayList<State> childern=new ArrayList<State>();

    public State(char label,boolean isAcepting){
        this.label=(byte)label;
        this.isAccepting=isAcepting;
    }
}
//////////////////////////////////////////////////////

//////////////Main class/////////////////////////////
public class Main {

    //Start state
    State start=new State('$',false);

    //Current State
    State currentState=start;

    //States in state machine
    State e=new State('e', false);
    State en=new State('n', false);
    State eno=new State('o', true);

    State n=new State('n', false);

    State ni=new State('i', true);

    State no=new State('o', false);
    State not=new State('t', false);
    State notu=new State('u', false);
    State notup=new State('p', true);

    State t=new State('t', false);

    State tu=new State('u', false);
    State tuo=new State('o', true);

    State tup=new State('p', false);
    State tupt=new State('t', false);

    State tuptu=new State('u', false);
    State tuptuo=new State('o', true);

    State tupn=new State('n', false);
    State tupni=new State('i', true);



    public void constructStateTree(){

            start.childern.add(e);
            start.childern.add(n);
            start.childern.add(t);

            e.childern.add(en);
            en.childern.add(eno);
            eno.childern=start.childern;

            n.childern.add(ni);
            n.childern.add(no);
            ni.childern=start.childern;

            no.childern.add(not);
            not.childern.add(notu);
            notu.childern.add(notup);
            notup.childern=start.childern;

            t.childern.add(tu);
            tu.childern.add(tuo);
            tu.childern.add(tup);
            tuo.childern=start.childern;

            tup.childern.add(tupn);
            tup.childern.add(tupt);

            tupn.childern.add(tupni);
            tupni.childern=start.childern;

            tupt.childern.add(tuptu);
            tuptu.childern.add(tuptuo);
            tuptuo.childern=start.childern;

    }


    public boolean travelTree(byte c){
        boolean isValid=false;

        for(int i=0;i<currentState.childern.size();i++)
            if(c==currentState.childern.get(i).label)
            {
                currentState=currentState.childern.get(i);
                isValid=true;
                break;
            }

        return isValid;
    }


    public static void main(String args[]) throws IOException{
        BufferedReader bfr= new BufferedReader(new InputStreamReader(System.in));
        int inputSize=Integer.parseInt(bfr.readLine());
        boolean isDialog=true;
        Main m=new Main();
        m.constructStateTree();
        byte[] b=new byte[10000000];

        for(int i=0;i<inputSize;i++){
             m.currentState=m.start;
             int j=0;
             byte sb;

             while((sb= (byte) bfr.read())!=-1){
                if(sb==(byte)'\n')
                      break;

                    b[j]=sb;
                    j++;
                }


                for(j=j-1;j>=0;j--){
                    isDialog=m.travelTree(b[j]);
                    if(!isDialog)
                        break;
                }

                if(isDialog&&m.currentState.isAccepting)
                      System.out.println("YES");
                else
                  System.out.println("NO");

        }

    }

}
/////////////////////////////////////////////////////

Can you help me for DFA? I am really not sure how to solve the question.

Thanks for your help in advance.

I use this!
 in_:=ord('i')*64+ord('n');
 out_:=ord('o')*4096+ord('u')*64+ord('t');
 on_:=ord('o')*64+ord('n');
 put_:=ord('p')*4096+ord('u')*64+ord('t');
 e_:=ord('e');

then you can do 'If' operation in o(1) time, so i get ac in 0.314
when i use strings i got TL!

I use DFA algorithm
at first I tried the getc() method and parse letter one by one , and got AC -0.65 s
then, I use scanf() method to scan in the whole text and then use the same algorithm
,got AC -0.093
quite confusing??

Edited by author 29.07.2011 11:16

Edited by author 29.07.2011 11:17