Play on WordsProblem code: WORDS1 |
Some of the secret doors contain a very interesting word puzzle. The team of
archaeologists has to solve it to open that doors. Because there is no
other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one
word written on it. The plates must be arranged into a sequence in such a way that
every word begins with the same letter as the previous
word ends. For example, the word acm'' can be followed by the word
motorola''. Your
task is to write a computer program that will read the list of words and
determine whether it is possible to arrange all of the plates in
a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T, equal to about 500) is given on
the first line of the input file.
Each test case begins with a line containing a single integer number N that indicates the number of plates
(1 <= N <= 100000). Then exactly Nlines follow,
each containing a single word. Each word contains at least two
and at most 1000 lowercase characters, that means only letters 'a'
through 'z' will appear in the word. The same word may appear several
times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in
a sequence such that the first letter of each word is equal to the last
letter of the previous word. All the plates from the list must be used, each
exactly once. The words mentioned several times must be
used that number of times.
If there exists such an ordering of plates, your program should print
the sentence "Ordering is possible.". Otherwise, output
the sentence "The door cannot be opened.".
Example
Sample input: 3 2 directi codechef 3 skenzo logicboxes orderbox 2 ok ok Sample output: The door cannot be opened. Ordering is possible. The door cannot be opened.
Warning: large Input/Output data, be careful with certain languages
| Date: | 2008-12-01 |
| Time limit: | 7s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.

Fetching successful submissions 
Can i get the input for which the program failed?
I would like to know to which test case the program failed. Please facilitate that.,
Please read the FAQ at http://blog.codechef.com/2009/06/29/frequently-asked-questions/
Hi, I keep getting a "Time
You might want to try with a
You might want to try with a large set of strings for which the door can be opened. If you keep getting TLE, then you either need to improve your algorithm or optimize it.
can i get the test cases for
can i get the test cases for this program. my program is running absolutely fine on my pc
Currently it is not possible
Currently it is not possible to give test cases as then it would be possible to hardcode the values and submit the code.
Can we know how much time our
Can we know how much time our problem took, when it exceeds the time limit?
That way we would know how much improvements we must make in our programs..
Currently this is not
Currently this is not possible because as soon as the program exceeds the time limit, it is terminated. Some programs take an infinite amount of time to execute, so such an approach wouldn't really help.
i keep getting wrong asnwer
i keep getting wrong asnwer wrong answer :(
help needed....i m fed up.....
what should be the output
what should be the output when only one word is entered???
This should be evident from
This should be evident from the problem statement :)
i tried both the things still
i tried both the things still not working ...!!!!
can u provide some more sample cases..I can't detect the flaw!!!!!
It should be easy to create
It should be easy to create large random samples and test by first creating a very large sample which is correct in a greedy fashion and then using a random permutation of it as the test input.
i need some test cases where
i need some test cases where the program is failing.
i have even corrected the earlier error..changed everything
still couldn't figure out what is happening...
There's a very useful test
There's a very useful test case for this problem on the forum.
Unfortunately, it ruins my algorithm completely.
can any one please mail me
can any one please mail me the solution of this problem????
I'm execute in Borland c++,
I'm execute in Borland c++, but i could not code for the above given languages,,,, can any one help me ???????
Though this may sound very
Though this may sound very noobish, here i go. Im new to all this, gcc and stdin/stdout. Ive submitted my soultiona nd am getting a segmentation fault. When i executed it on my own machine (in gcc) by taking in inputs whenever required i could arrive at the desired results, which forces me to think that im making a mistake in taking in input. I will post my code segment wherin i take in input and any suggestions or tweaks would be greatly appreciated.
#include <stdio.h>
#include <string.h>
int main ()
{
int tc=0;
scanf("%d",&tc); //take in test cases
while(tc--)
{
scanf("%d",&count); //take in word count
while(count--)
{
//code segment
}
return 0;
}
Sorry, the correct code for
Sorry, the correct code for the above comment is as follows
#include <stdio.h>
#include <string.h>
int main ()
{
int tc=0;
scanf("%d",&tc); //take in test cases
while(tc--)
{
scanf("%d",&count); //take in word count
while(count--)
{
//code segment
}
}
return 0;
}
Vignesh
can you plz let me know where
can you plz let me know where m i going wrong??? it seems correct on my part...
a) You aren't reading input
a) You aren't reading input correctly. Read the FAQ.
b) Your code will fail on cases like aa bb.
Doesn't the problem reduce to
Doesn't the problem reduce to determining the existence of a Hamiltonian path (chain) in a directed graph? And the latter is an NPC problem.
The problem is solvable. That
The problem is solvable. That answers your question.