Exploding SearchProblem code: INSOMA2 |
All submissions for this problem are available.
Magazines and newspapers often have letter matrices in which certain words need to be located. Umesh, a puzzle fanatic at IIT Roorkee, had an idea for a new kind of searching puzzle. In the letter matrix provided, words can be located along any set of diagonals, with repetition of past selected letters.
For example, in the letter matrix:
B X A X X
X A X X X
X B B X X
X A X A X
X X B X X
The string ABA can be found in 14 different ways – corresponding to the following locations:
A B A
(1,1) (0,0) (1,1)
(1,1) (2,2) (3,1)
(1,1) (2,2) (3,3)
(1,1) (2,2) (1,1)
(3,1) (2,2) (3,1)
(3,1) (2,2) (3,3)
(3,1) (4,2) (3,1)
(3,1) (4,2) (3,3)
(3,1) (2,2) (1,1)
(3,3) (2,2) (3,3)
(3,3) (2,2) (1,1)
(3,3) (2,2) (3,1)
(3,3) (4,2) (3,1)
(3,3) (4,2) (3,3)
So, given a matrix of size NxN, you need to find out the total number of locations of a particular string. The input and output formats are as follows:
Input
Line 1: N. 1 <= N <= 1000
Line 2 to N+1: Elements of the NxN matrix in row major order (separated by a space)
Line N+2: The string to search. Maximum length of this string will be N2.
Output
Line 1: The number of ways in which the string can be found in the matrix.
Example
Input:
5
B X A X X
X A X X X
X B B X X
X A X A X
X X B X X
ABA
Output:
14
| Author: | admin |
| Date Added: | 19-03-2009 |
| Time Limit: | 2 - 7 sec |
| Source Limit: | 50001 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.0.0-8, CS2, D, ERL, FORT, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, 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.
In the sample input, according to the size of the matrix, the value at the first line should be 5, instead of 8. I hope actual test cases are right!
Why this problem is not available?
i cant select language on the submission page for this problem, though for other problems its working.... please look into the matter
Fixed.
How is 4,2 a B? Looks like
Nevermind my last comment...
Please, fix the example
Please, fix the example input. It is incorrect. The size of the matrix should be 5 instead of 8. I am sure about that - I just submitted successful solution.
Fixed.
Fixed.
my program is working fine
"Maximum length of this
"Maximum length of this string will be N2."
This is N^2 or N*2 ?
I'd also like to know the
I'd also like to know the answer to Victor's question. There's an operator missing there.
did any body got the answer
did any body got the answer to N2 question?
Please Admin, can sombody
Please Admin, can sombody confirm that the input matrix will always contain just X,A,B and if so what should be the answer for ABBA?
N2 should be N^2. The problem
N2 should be N^2.
The problem does not say the matrix will only contain those 3 characters, so you should not assume so.
The answer for ABBA for the sample grid would be 0.
when i submit the answer it
when i submit the answer it shows me a result set that is probably the set of inputs that were tested and i get
(0.00s)
can somebody please explain me this... what does the no. -1336677216 stand for in this case?
admin please can you explain
admin please can you explain me the above question. it can help me a lot in getting the write solution becuase i am getting the correct answer for the given test case....
posting the query for the
posting the query for the third time please.... anybody help
@admin: While counting such
@admin:
While counting such possible strings, its possible to get a value which exceeds the range of long long. Solution should have been invited in some modulo form.
I can't figure out where this solution is failing.
http://www.codechef.com/viewsolution/460318
Please hint!
@admin What is the number
After several tries I figured