Code Crazy Minions
All submissions for this problem are available.
Coding in Sprout (a programming language) is very intuitive. Chef is giving his minions a demonstration in Sprout and wants you to
help him determine if they are not too difficult for them.
A program in Sprout is written using three kinds of instructions.
- Load Instruction: Load a value into buffer.
- Increment Instruction: Increment the value in buffer.
- Print Instruction: Print the value from buffer.
The buffer stores a single integer between 0 and 25, both inclusive. If the value in the buffer is x, the increment instruction
makes the value (x+1), if x < 25. At x = 25 the increment instruction makes the value 0.
Load Instruction can be used to load any value between 0 and 25 (inclusive) into the buffer.
Print from the buffer prints a lowercase English character based on the value in the buffer. Precisely, it prints the (x+1)th character
in the alphabet. Thus, for x = 0, 'a' is printed; x = 1, 'b' is printed and so on. For x = 25, 'z' is printed.
To keep his programs clear, he uses the load instruction only once in the beginning (before printing any character). Then
he proceeds instruction after instruction. A program is simple, if the number of instructions is not more than ELEVEN times the length
of the word that it prints.
Given the word Chef wants his program to print and assuming he will write the shortest code (i.e. use the fewest instructions)
to print it, will the program be simple?
The first Line contains a single number T, the number of test cases.
Each test case contains 1 word on a line by itself - the word that would be printed by Chef's program.
Assuming Chef writes the shortest code (with minimum instructions) to print the given word, output "YES" if this code is not more than
ELEVEN times the length of the word being printed; "NO" otherwise
1 ≤ T ≤ 100 1 ≤ length of word ≤ 1000
2 helloworld mississippi
The optimal program length for mississippi is 112 instructions and that is smaller than 121 (length of 'mississippi' * 11)
|Tags||cook25, gamabunta, greedy|
|Time Limit:||0.445 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.