ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1102. Странный диалог

My program passess all test but gets WA 1
Послано JAVATAR 14 июл 2012 03:08
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");

        }

    }

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