zumzi

Zumzi

== include(page="template/taskheader" task_id="zumzi") ==

Poveste şi cerinţă...

Albinuţa **zumzi** locuieşte într-un stup format din $N$ celule de formă hexagonală. Cele $N$ celule numerotate de la $1$ la $N$ sunt dispuse sub formă de spirală ca în figura următoare.
 
!problema/zumzi?zumzi1.jpg!
 
Adică, celula din centrul stupului este numerotată cu $1$. Plecând de la această celulă spre sud şi apoi în spirală, în sensul acelor de ceasornic, sunt numerotate celelalte celule.
 
Iniţial **zumzi** se găseşte în celula din centru (cea numerotată cu $1$), şi doreşte să ajungă, trecând din celulă în celulă, la celula cu numărul de ordine $X$, unde se găseşte prietenul ei. zumzi se poate deplasa dintr-o celulă în oricare dintre celulele vecine, fără a părăsi însă stupul. Două celule sunt vecine dacă au o latură comună.
 
Unele celule ale stupului sunt ocupate de alte albine şi de aceea **zumzi** nu poate să treacă prin ele.
 
Problema vă cere să determinaţi câte variante are **zumzi** ca după **exact** $K$ paşi să ajungă la prietenul ei.

h2. Date de intrare

Fişierul de intrare $zumzi.in$ ...

Fişierul de intrare $zumzi.in$ conţine pe prima sa linie valorile naturale $N$, $M$, $K$ şi $X$ separate printr-un spaţiu, având următoarea semnificaţie:
 
* $N$ - numărul total de celule din stup;
 
* $M$ - numărul de celule din stup ocupate de alte albine
 
* $K$ - numărul de paşi pe care îi are la dispoziţie zumzi
 
* $X$ - numărul de ordine a celulei în care se găseşte prietenul lui zumzi.
 
Următoarea linie a fişierului de intrare conţine M numere naturale separate printr-un spaţiu reprezentând numerele de ordine ale celulelor ocupate din stup.
 

h2. Date de ieşire

În fişierul de ieşire $zumzi.out$ ...

Fişierul text zumzi.out va conţine pe prima sa linie un singur număr natural reprezentând numărul de variante pe care le are zumzi la dispoziţie de a ajunge la prietenul ei.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 &le; M < N &le; 300$
 
* $X &ne; 1$
 
* $K &le; 100$
 
* **zumzi** nu are posibilitatea de a părăsi stupul, iar în plus odată ajunsă la prietenul ei nu îl va mai părăsi.
 
* **zumzi** nu este o albină foarte inteligentă de aceea ea poate trece de mai multe ori printr-o celulă, cu exceptia celulei finale, in care se afla prietenul ei, celula in care va intra o singura data si nu o mai paraseste.
 

h2. Exemplu
table(example). |_. zumzi.in |_. zumzi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 12 4 3 9
11 4 6 8
| 4
|
| 12 4 4 2
11 4 6 8
| 9
|
 

h3. Explicaţie

...

Variantele avute la dispoziţie sunt în primul exemplu sunt:
$1-2-10-9$
$1-3-2-9$
$1-3-10-9$
$1-7-2-9$
 
iar pentru exemplul al doilea variantele sunt:
$1-3-10-9-2$
$1-7-1-3-2$
$1-5-1-7-2$
etc.
 
Ambele exemple corespund următoarei figuri:
 
!problema/zumzi?zumzi2.jpg!

== include(page="template/taskfooter" task_id="zumzi") ==

3911