DUCKS - Here be ducks

no tags 

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.


hide comments
Darky: 2012-04-14 19:12:04

Nice Problem! Recursion is the best approach.

anksanu: 2012-04-12 23:15:49

there is a small thing that i believe that every one is missing
took me many silly submitions

Sarthak Narang: 2012-04-12 18:02:48

Why am I getting WA?
SRC ID:6831379

Last edit: 2012-04-12 18:07:15
Ahmed AKram: 2012-04-12 15:26:49

No need for the extra clarifications, nice problem though :)

CarloSz: 2012-04-12 04:49:54

Finally got AC bro, i was in my moments of boredom to implement the solution jeje

__AAA__: 2012-04-12 00:58:59

@Problem Setter any hints to where submission id 6823632 keeps failing?? Thanks

Giorgos Christoglou: 2012-04-12 00:58:59

why my solution is wrong ???
ID:6820254

Min2: 2012-04-12 00:58:59

rubbish problem with no information about test case

Edit: solution to the problem is really easy, so to don´t let it to be tutorial the problem has many tricky cases and you have to read problem carefully

if you want to validate cases like DDDDucky or Duccckyy meanless cause there is no test cases with those kind of things.

Read the problem, all traps are there... sorry xD

Last edit: 2012-04-11 02:27:14
Daniel Ampuero: 2012-04-12 00:58:59

It should be "Jhonny's here!" :D

Suraj D: 2012-04-12 00:58:59

@Problem Setter any hints to where submission id 6815994 keeps failing?? Thanks

Edit: i suggest you to read the problem carefully :D

Last edit: 2012-04-11 02:40:14

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