Fişierul intrare/ieşire:zumzi.in, zumzi.outSursăONI 2006, clasa a IX-a
AutorCarmen PopescuAdăugată depcinfoCarmen Popescu pcinfo
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zumzi

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.

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.

Date de intrare

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.

Date de ieşire

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.

Restricţii

  • 1 ≤ M < N ≤ 300
  • X ≠ 1
  • K ≤ 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.

Exemplu

zumzi.inzumzi.out
12 4 3 9
11 4 6 8
4
12 4 4 2
11 4 6 8
9

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:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content