Rezultatul cerut este $I{~N~}$ modulo $666013$ pentru fiecare test.
O prima rezolvare, si cea mai simpla, este implementarea directa a relatiei de recurenta si conduce la o complexitate $O(N)$ pe set de date. Aceasta abordare ar fi obtinut {$50p$}.In continuare voi descrie o rezolvare $O(lg N)4 care foloseste matrici. Se construieste matricea:

== code(pas) |

p(pre).

    [0 1 0]
M = [0 0 1]
    [C B A]

==

care sta la baza relatiei:

p(pre).
    [I{~0~}]   [I{~N  ~}]
M * [I{~1~}] = [I{~N+1~}]
    [I{~2~}]   [I{~N+2~}]
 

[I(n) ] [I(n+1)]
M * [I(n+1)] = [I(n+2)]
[I(n+2)] [I(n+3)]
Din asta se deduce:

[I(0)] [I(N) ]
M^N * [I(1)] = [I(N+1)]
[I(2)] [I(N+2)]

p(pre).
     [I{~0~}]    [I{~N  ~}]
M^N^ * [I{~1~}] = [I{~N+1~}]
     [I{~2~}]    [I{~N+2~}]
 

astfel problema se reduce la a calcula M^N in O(lg N). Algoritmul de ridicare la putere in timp logaritmic este clasic si nu-l mai mentionez aici.

astfel problema se reduce la a calcula $M^N^$ in {$O(lg N)$}. Algoritmul de ridicare la putere in timp logaritmic este clasic si nu-l mai mentionez aici.

h3. Barbar

Problema este de nivel mediu si necesita cunostiinte elementare de teoria grafurilor. Se considera matricea initiala un graf cu R*C noduri, mai putin zidurile. Se face o parcurgere BF pentru a determina pentru fiecare casuta din matrice distanta pana la cel mai apropiat dragon. Astfel, se incepe BF-ul cu toate nodurile care corespund dragonilor inserate in coada (deci nu va fi doar un nod in coada la inceput). Complexitatea acestui pas este O(R*C). Se observa daca exista un traseu valid care trece prin casute situate la distanta >=x fata de cel mai apropiat dragon, atunci exista in mod evident un traseu valid care trece prin casute situate la distanta >=x-1 fata de cel mai apropiat dragon. Aceasta observatie duce la folosirea cautarii binare a rezultatului (vezi articolul de pe site pentru alte aplicatii). Pentru a verifica daca exista un traseu valid care trece doar prin casute situate la o anumita distanta fata de cel mai apropiat dragon se foloseste tot o parcurgere BF, astfel rezolvarea fiind

Problema este de nivel mediu si necesita cunostiinte elementare de teoria grafurilor. Se considera matricea initiala un graf cu $R*C$ noduri, mai putin zidurile. Se face o parcurgere BF pentru a determina pentru fiecare casuta din matrice distanta pana la cel mai apropiat dragon. Astfel, se incepe BF-ul cu toate nodurile care corespund dragonilor inserate in coada (deci nu va fi doar un nod in coada la inceput). Complexitatea acestui pas este O(R*C). Se observa daca exista un traseu valid care trece prin casute situate la distanta >=x fata de cel mai apropiat dragon, atunci exista in mod evident un traseu valid care trece prin casute situate la distanta >=x-1 fata de cel mai apropiat dragon. Aceasta observatie duce la folosirea cautarii binare a rezultatului (vezi articolul de pe site pentru alte aplicatii). Pentru a verifica daca exista un traseu valid care trece doar prin casute situate la o anumita distanta fata de cel mai apropiat dragon se foloseste tot o parcurgere BF, astfel rezolvarea fiind

O(R*C*lg(R*C)).
h3. ADN