Se consideră un cub de dimensiune N. Acesta poate fi împărțit în N3 cubulețe cu latura egală cu unitatea. În fiecare dintre aceste cubulețe se află câte o literă mică a alfabetului latin.
Sarcina voastră este de a determina numărul de apariții ale unui cuvânt S de lungime K, format din litere mici distincte. Cuvântul apare în cub dacă prima sa literă apare într-un anumit cubuleț, cea de-a doua literă apare în unul dintre cele cel mult 26 de cubulețe învecinate, a treia literă apare în unul dintre cele cel mult 26 de cubulețe vecine cu cubulețul în care se află a doua literă și așa mai departe. Pentru un cubuleț de coordonate (x, y, z), cele 26 de cubulețe învecinate au coordonatele (x + dx, y + dy, z + dz), unde dx, dy și dz fac parte din mulțimea {-1, 0, 1} și |dx| + |dy| + |dz| > 0. Aparițiile cuvântului se pot suprapune parțial, în sensul că un anumit cubuleț poate apărea în două sau mai multe apariții ale cuvântului dat.
Pe prima linie a fișierului de intrare se află cuvântul S. Pe a doua linie se află un număr întreg N care reprezintă dimensiunea cubului.
Pe următoarele N2 linii se află câte N litere ale alfabetului latin neseparate prin spații. Considerăm că cele N3 cubulețe sunt identificate prin coordonatele (x, y, z), unde x, y și z variază între 1 și N. Pe primele N linii (dintre cele N2) se vor afla literele corespunzătoare cubulețelor pentru care z = 1. Pe prima dintre acestea se vor afla literele corespunzătoare cubulețelor pentru care y = 1. Prima dintre aceste litere va corespunde cubulețului pentru care x = 1, a doua va corespunde cubulețului pentru care x = 2 și așa mai departe. Pe a doua dintre cele N linii se vor afla literele corespunzătoare cubulețelor pentru care y = 2 și așa mai departe. Pe următoarele N linii se vor afla literele corespunzătoare cubulețelor pentru care z = 2 și așa mai departe.
Fișierul de ieșire va conține o singură linie pe care se va afla un singur număr, reprezentând numărul de apariții ale cuvântului S în cub.
· 1 <= N < 40;
· 1 <= K <= 26; · numărul soluțiilor nu depășește 2000000000.
CUBE.IN ab 2 aa aa bb bc CUBE.OUT 12
Cele 12 apariții ale cuvântului sunt:
|