DUCKS - Here be ducks

Ducky the Duck was walking by and he had a little idea, he wanted to see if making a line of dots with his pencil and throwing the letters of his name randomly at it he would be able to pick up the letters again and write his name perfectly, but some times when he throws them they fall out of the path. Ducky also throwed random characters to replace some of the dots, when he reaches a random character before he find his name he gets mad and scream NO DUCKY!, task is simple, just find Ducky´s name on the path he made.

Clarifications:

  1. Ducky starts looking for his name from the beginning of the string.
  2. Ducky want to find the letters of his name that means 'D' 'u' 'c' 'k' 'y' another letter even the letter 'd' is considered a random character.
  3. When he steps a dot he will keep searching for the name, if he steps a letter of his name and hasn´t found them all he will keep searching, when he finds a random character he will stop.

Input

T = Number of test cases, which are less than 20.

Then T lines will follow, each of them having a string representing the Ducky´s path.

Output

Output NO DUCKY! If you cannot find his name, otherwise print DUCKY IS HERE!

Example

Input:
5
Ducky...
.D...ucky
...Duck...
..D...uck!y
..u.c..ky.D

Output:
DUCKY IS HERE!
DUCKY IS HERE!
NO DUCKY!
NO DUCKY!
DUCKY IS HERE!

Extra: time limit reduced because there are fewer than 20 test cases and there is people getting 0.45 seconds on their answer, which for Ducky is unacceptable.


Added by:Rocker3011
Date:2012-04-07
Time limit:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2012-04-12 00:58:59 Rocker3011
never thought my problem was going to have so many comments and submissions... i really thinked it was a very easy problem :D
2012-04-12 00:58:59 Rajkiran Rajkumar
Its working fine for the many test cases that I tried. But why WA? :(
2012-04-12 00:58:59 nishaanth
hey i am getting WA again and again..can u check this submission and throw some light id = 6814689
2012-04-12 00:58:59 Nnavneetsinha
got acc. very nice problem.

Last edit: 2012-04-09 13:55:49
2012-04-12 00:58:59 ~
funny question nothing to tense...:D
2012-04-12 00:58:59 Nnavneetsinha
please check the id 6812204.what is wrong with it. please tell me is there any specific/corner test case left.

Edit: Again, read the problem carefully, your WA are all around the same test case. Read carefully the problem

Last edit: 2012-04-09 04:40:26
2012-04-12 00:58:59 (^_^)
heyii I am getting wrong answer again and again for this problem.
can you give me one test case where my code if failing
id 6812039

Edit: you need to read more carefully the problem, take your time, answer to your WA´s is there.

Last edit: 2012-04-09 03:28:53
2012-04-12 00:58:59 sikandar
output for ..D...uck!y. please

Last edit: 2012-04-08 22:17:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.