Блог пользователя mzaferbooshi96

Автор mzaferbooshi96, история, 4 часа назад, По-английски

Ahmed loves the letter "Z" very much, and he loves the number of "Z" letters in each string s.

Input

The first line of input contains string s.

Output

Print an integer representing the number of occurrences of the letter "Z". If there is no "Z", type "NO" without the quotes. examples: input:

zzzz

output: 4

input:

codeforces

output:

NO

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).

»
4 часа назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

I think this can be solved with topological sorting and DP.

Notice that we can represent the string as a Directed Acyclic Graph (DAG), where each node has a character and an edge to the next node. I think that each node $$$i$$$ has a directed edge to node $$$i + 1$$$, but I don't know how to prove it. Now we topologically sort the graph and perform dynamic programming. Let $$$dp_i$$$ represent the number of letters Z at node $$$i$$$. The transitions are trivial.

Our answer is $$$dp_n$$$. If $$$dp_n$$$ is equal to $$$0$$$, we print "NO".

I hope this helped.

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    My implementation