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

Help .. WA on an easy interesting GYM problem
Автор Seif, история, 9 лет назад, По-английски

My solution in 100651A - ALPHACODE - Alphacode got WA on test 2 .. and this is my code : http://ideone.com/GwzmWe can anyone provide me a test case to drop this? thanks on advance.

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

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

Can you please explain your solution's logic? I know only another solution.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ok , now i got why it was WA , because of zeros like 101 , 100 . it's accepted now :)) actually My idea comes due to some observations ! if we have something like that 25925925 .. let's call the number of possible chars to get from a segment X .. now it's cleat that 25 gives us 2 different chars {2 5 , 25} .. so by combinations ans = X * 3 = 2 * 2 * 2 so what about that 1111 ? it's fib[5] why ? i don't know ! so for n consecutive chars you have X = fib[n+1] the result becomes X1 * X2 * ... I'm trying to find a proof for that ! :( final code : http://ideone.com/nkIXN5

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      My solution is similar, may be it will help you to prove your:

      Let dp[i] be the answer for prefix of length i.

      At first dp[i] = 0. Then:

      if (a[i] > 0) dp[i] += dp[i - 1];;
if (10*a[i - 1] + a[i] <= 26 && ... > 0) dp[i] += dp[i - 2];

      You can see that this formulas has something similar to Fibbonacci numbers

      → Ответить