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.
@stephen Plz help, i do not
@stephen
Plz help, i do not get my fault. how can i get a test case ? atleast here we can get test cases, its not a contest.
You could get test cases; you
You could get test cases; you could also just have someone tell you the solution. The hardest part of solving a problem is coming up with your own test cases - but in this case it isn't too hard to do yourself at all. There are only a few test cases that you need to check; be systematic and you'll find one your program fails on.
@
@ admins
http://www.codechef.com/viewsolution/270509 getting wrong answer for this. can you give me a hint??
@admins i m not getting the
@admins
i m not getting the test cases for which my prog is failing to generate the reqd output.....can u plz help me out
import java.io.BufferedReader;
import java.io.InputStreamReader;
class str
{
public static void main(String args[])throws Exception
{
BufferedReader q=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(q.readLine());
for(int i=0;i<t;i++)
{
int n=Integer.parseInt(q.readLine());
String s[]=new String[n];
for(int j=0;j<n;j++)
s[j]=q.readLine();
char c[]=new char[n];
char e[]=new char[n];
for(int k=0;k<n;k++)
{
c[k]=s[k].charAt(0);
e[k]=s[k].charAt(s[k].length()-1);
}
int f=0,g=0;
for(int l=97;l<=122;l++)
{
char d=(char)l;
int tmp1=0,tmp2=0;
for(int j=0;j<n;j++)
{
if(c[j]==d)
tmp1++;
if(e[j]==d)
tmp2++;
}
if(tmp1>0 || tmp2>0)
if(tmp1!=tmp2)
f++;
else
g++;
}
//System.out.println("f = "+f);
//System.out.println("g = "+g);
if(f>=2&&g==0 || f>2)
System.out.println("The door cannot be opened.");
else
System.out.println("Ordering is possible.");
}
}
}
Hi, I have tried everything
Hi,
I have tried everything with this problem, I have always got Runtime Error. The Id is 289432.Could you tell me for which test case am I getting this error?. I have even tried giving 2 test cases and in each test case, 100000 plates and each word contains 1000 letters. And this works perfectly on my system. Could you please help me out.
Thanks,
Johnson
Hi, I had not checked for one
Hi,
I had not checked for one element test case and that gave me a segmentation fault, I rectified that but still getting the runtime error. Id of the rectified code is 289438
Thanks,
Johnson
i submitted the following
i submitted the following code.I m getting 'Tine Limit Exceede'.what is the problem?
using System;
class MainClass
{
public static void Main (string[] args)
{
int b=int.Parse(Console.ReadLine());
for(int i=0;i<b;i++)
{
int x=int.Parse (Console.ReadLine());
string [] input=new string [x];
int check=0;
for(int j=0;j<x;j++)
{
input[j]=Console.ReadLine();
}
for(int k=0;k<x;k++)
{
for(int l=0;l<x;l++)
{
if(l!=k)
{
if(input[k].Substring(0,1)==input[l].Substring(input[l].Length -1,1))
{
check++;
break;
}
else if(input[k].Substring(input[k].Length -1,1)==input[l].Substring(0,1))
{
check++;
break;
}
}
}
}
if(check==x)
{
Console.WriteLine("Ordering is possible");
check=0;
}
else
{
Console.WriteLine("The door cannot be opened");
check =0;
}
}
}
}
:( working pefectly on my
:( working pefectly on my system..On submission i am getting runtime error.. :(
some body else , Please try
some body else , Please try below code any find any bug if there ..thx
#include<iostream>
#include<vector>
using namespace std;
typedef std::vector<int> vecType;
const std::string NO("The door cannot be opened.n");
const std::string YES("Ordering is possible.n");
void func(char & input,vecType & allChars,bool first=true)
{
int a;
switch(input)
{
case 'a':
{
a=0;
break;
}
case 'b':
{
a=1;
break;
}
case 'c':
{
a=2;
break;
}
case 'd':
{
a=3;
break;
}
case 'e':
{
a=4;
break;
}
case 'f':
{
a=5;
break;
}
case 'g':
{
a=6;
break;
}
case 'h':
{
a=7;
break;;
}
case 'i':
{
a=8;
break;;
}
case 'j':
{
a=9;
break;
}
case 'k':
{
a=10;
break;
}
case 'l':
{
a=11;
break;
}
case 'm':
{
a=12;
break;
}
case 'n':
{
a=13;
break;
}
case 'o':
{
a=14;
break;
}
case 'p':
{
a=15;
break;
}
case 'q':
{
a=16;
break;
}
case 'r':
{
a=17;
break;
}
case 's':
{
a=18;
break;
}
case 't':
{
a=19;
break;
}
case 'u':
{
a=20;
break;
}
case 'v':
{
a=21;
break;
}
case 'w':
{
a=22;
break;
}
case 'x':
{
a=23;
break;
}
case 'y':
{
a=24;
break;
}
case 'z':
{
a=25;
break;
}
}
if(first)
allChars[a]=allChars[a]++;
else
allChars[a]=allChars[a]--;
}
int main()
{
short numTest;
vector<bool> results(numTest,true);
cin>>numTest;
for(int i=0;i<numTest;i++)
{
int numInput;
cin>>numInput;
vecType vec(26,0);
for(int j=0;j<numInput;j++)
{
std::string inString;
cin>>inString;
func(inString[0],vec,true);
func(inString[inString.size()-1],vec,false);
}
int minusOne=0;
int plusOne=0;
for(vecType::iterator itr=vec.begin(); itr!=vec.end();itr++)
{
if((*itr!=1) && (*itr!=-1) && (*itr!=0))
{
results[i]=false;
break;
}
if(*itr==-1)
minusOne++;
if(*itr==1)
plusOne++;
if(minusOne> 1 || plusOne>1)
{
results[i]=false;
break;
}
}
}
for( int i=0;i<numTest;i++)
{
(results[i])?(cout<<YES):(cout<<NO);
}
return 0;
}
Can someone tell me for
Can someone tell me for which test case is my program failing ?
my code works for test cases
my code works for test cases i can think of, the test case on the discussion forum also works fine......please help!!!!!
Ive got really tired....plz
Ive got really tired....plz give me a hint. I cant find where my sol fails?????????????????????