Page 4 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; } thnx a lot c_pp atleast i learn something 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. I dont understood too. It is unbelievable! 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! Maybe, it means that test 1 not look like sample 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 Read only char-by-char (token-by-token). In the worst case you will have one string of 10^7 chars - this will get ML anyway (and with java it will occur much earlier). So, don't cheat, write parser honestly. #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> #include <cstdlib> #include <stdio.h> #include <string> #include <cstring> using namespace std; int flag=0; int flag1=0; char *a = new char [10000000]; int main() { int k=0,n=0,j=0,l=0; int i=0,pos=0; std::cin>>k; char c; for (j=1;j<=k+1;j++) { i=0; l=0; gets(a); n=strlen(a);n--;
if (n>0){
pos=n;
while (pos>0){ if ((a[pos]=='t') && (a[pos-1]=='u') && (a[pos-2]=='p') && (a[pos-3]=='t') && (a[pos-4]=='u') && (a[pos-5]=='o')) {l=1;pos=pos-6;} if ((a[pos]=='t') && (a[pos-1]=='u') && (a[pos-2]=='p') && (a[pos-3]=='n') && (a[pos-4]=='i')) {l=1;pos=pos-5;} if ((a[pos]=='n') && (a[pos-1]=='o') && (a[pos-2]=='t') && (a[pos-3]=='u') && (a[pos-4]=='p')) {l=1;pos=pos-5;} if ((a[pos]=='t') && (a[pos-1]=='u') && (a[pos-2]=='o')) {l=1;pos=pos-3;} if ((a[pos]=='e') && (a[pos-1]=='n') && (a[pos-2]=='o')) {l=1;pos=pos-3;} if ((a[pos]=='n') && (a[pos-1]=='i')) {l=1;pos=pos-2;} if (l==0) {break;} } if (l==1) std::cout<<"YES"; else std::cout<<"NO"; }}
delete [] a; } Don't read the whole file (and even line!) into memory - each time you need only the last and previous words - so, this problem is solvable in O(1) memory Page 3 #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; } Obviously you aren't testing all the words. You has to consider if the input string contains a substring that isn't (one/output/out/in/input/puton). I'll just add that test #1 for this problem is a pretty serious test that requires complete correctness, not just the samples to pass (unlike in other problems). 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 |
|