Name ChoppingProblem code: INSOMA4 |
All submissions for this problem are available.
In the hidden country of Lapatrecta, an age old custom was followed to ensure that no outsider ever entered their country undetected. The security measure, though simple, was an effective one. Every person born in Lapatrecta had the initials of all his forefathers included in front of his name. Every once in a while, certain families became very famous and the initials of their ancestors were dropped from the names of all their descendants. Thus, there existed a nice homogeneity in the names of the people of Lapatrecta.
Now, a royal ball was organized at the behest of the Queen of Lapatrecta and all citizens were cordially invited to the event. The ball was being held to chop off the initials of the ancestors of the most distinguished family of the country. The Queen set the following 2 criteria for determining the most distinguished family from amongst the invitees:
1. The family must have more than 1 member living.
2. The length of the ancestor list of the family must be as long as possible.
For example:
For 3 people:
APJQ Ravi
APJRS Rahul
PJQ Bharat
The following observations hold:
APJQ Ravi was of the same family as APJ Rahul but PJQ Bharat was not of the same family.
The length of the ancestor list for Ravi and Rahul was 3 whereas Bharat has an ancestor length of 0 as there is no other member of his family living. However, if there existed a person named PJ Varun, Bharat and Varun would both have an ancestor list length of 2.
As a member of the Royal Court of Lapatrecta, you have been entrusted the task of determining the length of the ancestor list that will be chopped off by the Queen. You will be provided data in the following format:
Input
Line 1: N – The number of people coming to the ball
Line 2-N+1: The initials list of all the people coming to the ball. No initials list is longer than 100 characters.
Output
Line 1: The length of the longest ancestor list.
Example
Input: 3 APJQ APJRS PJQ Output: 3
| Author: | admin |
| Date Added: | 19-03-2009 |
| Time Limit: | 2 - 7 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
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.
the question isn't clear...pls giv an example with an explanation
is there any limit on the no
is there any limit on the no of people that attend the ball?
Is the input restricted to
Is the input restricted to CAPS or can it be small and miXeD case??
Can be mixed.
Can be mixed.
what is the maximum value of
what is the maximum value of N ?
For N=10000, my code has
For N=10000, my code has runtime well below 7 s.
so is it that N can be even higher than this, given it is being displayed as time limit exceeded.
Admin, I have solved this
Admin,
I have solved this problem. I could not see the submissions of others. This problem exists for many other problems also. Please fix this
Admin, Is there a way I can
Admin,
Is there a way I can know for what particular input it is a WA?
No. FAQ
No. FAQ
Hi My solution is giving
Hi
My solution is giving runtime error. Can I find out what type of error is it showing?
Hi My solution is giving
Hi
My solution is giving runtime error. Can I find out what type of error is it showing?
Are 'A' and 'a' same in mixed
Are 'A' and 'a' same in mixed case or different?
@Shwetanka: Consider them
@Shwetanka: Consider them different.
@Vivek: I believe N<=10^5. My program would give TLE outside that range but it got accepted. Therefore, I am sure N<=10^5
what is
My prog works fine on my
Can the characters in the
What is the output for APJQ,
why is it showing runtime