ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1102. Strange Dialog

Olzhas2dy For those who dont know how to solve it [7] // Problem 1102. Strange Dialog 12 Jun 2007 19:47
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:36
Boris Strandjev Re: For those who dont know how to solve it // Problem 1102. Strange Dialog 19 Oct 2007 19:47
I 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.
Entheogen Re: For those who dont know how to solve it [2] // Problem 1102. Strange Dialog 14 Nov 2007 05:12
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.
Romko [Lviv NU] Re: For those who dont know how to solve it [1] // Problem 1102. Strange Dialog 14 Nov 2007 17:52
It's Not DFS problem!!!!! It's DFA(Deterministic finite automaton) problem!
Sergey Kazakov Re: For those who dont know how to solve it // Problem 1102. Strange Dialog 18 Apr 2008 21:08
I solved it with DFS in 0.453 sec.
PersonalJesus Re: For those who dont know how to solve it [2] // Problem 1102. Strange Dialog 24 Jun 2008 21:06
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 ?!
Nikita Mogilevets Re: For those who dont know how to solve it [1] // Problem 1102. Strange Dialog 11 May 2017 16:41
First test is really large.  Something of order 1e6.
Its a simple substring search problem.