Well, here are some hints: 1. Use DFA. If you do'nt know what it is, visit this page http://en.wikipedia.org/wiki/Deterministic_finite_automaton (pay attention to the table of states) 2. use getc() instead of cin>>ch or cin.getch() or whatever you use (for C++/C only) 3. Try this: 3 outputoutputinputon inputone Edited by author 13.06.2007 17:36I would recommend using gets() for all that want to have the whole string at once. It still is fast enough and does not time limit. How exactly do you use DFS for this? Can you provide an example of some other problem similar to this which is solvable by DFS? Thank you. It's Not DFS problem!!!!! It's DFA(Deterministic finite automaton) problem! I solved it with DFS in 0.453 sec. When I was using STL, I always had TL on the first test but I was sure that this is the correct algo. Then I replaced all STL's strings with array of chars and I got ACC 0.078 . OMGWTF ?! First test is really large. Something of order 1e6. Its a simple substring search problem. 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 just cin every string and then solve using it. 0.156 accepted delete Edited by author 04.10.2020 16:38 At first,I got wa on test1,like many other authors.But later,I found it! All in one sentence,test the data below: 1 inputon Hello, The answer is YES and my program out puts YES, but I get WA1. Can you please help me what I am doing wrong. It passes all of my tests but gets wa 1. I'm confused too, maybe there are some design errors, like 'Yes' or 'yes'when you have to use "YES\n" I have the same problem and the reason of problem was: character '\r' at the end of test inputs string (at my PC i use Linux and there is no such problem). Then I start to check input for '\r' character and this code was accepted! it's good test. Thank you. outputon YES Edited by author 28.08.2018 23:32 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! 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 Maybe finite state automation. Don't use cin(TL1) and getc(WA1), use scanf and get AC: char s[(int)1e7]; scanf("%s", &s); length = strlen(s); #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). 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? Are you kidding? My dumb solution in python ACCed in 0.3 sec:D Edited by author 24.05.2014 01:07 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. May be this tests will help to some others. When my prog passed all of them , I'v get AC. 12 putone inputon outputoutputinputon inputone putin outputin puton inonputin oneputonininputoutoutput oneininputwooutoutput outpu utput Answers: NO YES YES YES NO YES YES NO YES NO NO NO "putin" is the best test. =) And you forgot to tell about copyrights of this test =)))) It is possible to read data without MLE (Thanks to Fyodor Menshikov) and TLE (Thanks to Alex Tolstov ). And make very-very-simple DFA by reading from end to the begining of data string. If you will read "As is" you will have some problems with creating DFA :) My AC program using this "back reading" in Java works 0.625 s And use 10 390 КБ Good luck! Edited by author 29.07.2009 19:37 Hello, how does your programm do back reading? Can you post that part of your program? Hello, how does your programm do back reading? Can you post that part of your program? Just one char array of 10^7 of chars with "reused" for reading lines of char. Use BufferedReader to read bytes from input. Not Scanner. Edited by author 19.07.2012 03:10Thanks, man. You helped me to fix some problems in my state/event table :) People, be afraid of mistyping! #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 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. |
|