basequery

Basequery

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

Poveste şi cerinţă...

Se da un numar natural $N$ si un sir de $N$ numere naturale: $A ~1~, A ~2~, ..., A ~N~$.
 
Se defineste $C(X, P, B)$ = numarul de aparitii al lui P ca subsecventa in reprezentarea in baza B a lui X.
 
Sa se raspunda la $Q$ intrebari de genul:
 
* Fiind date o baza $B$ si o secventa $P$, scrisa in baza $B$, sa se calculeze si sa se afiseze suma de $C(A ~i~, P, B) * A ~i~$.
 
*Atentie!* Secventa $P$ poate incepe si cu cifra $0(zero)$.

h2. Date de intrare

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

Fişierul de intrare $basequery.in$ contine pe prima linie numarul natural $N$. Pe cea de-a doua linie se afla $N$ numere naturale, $A ~1~, A ~2~, ..., A ~N~$, elementele sirului. Pe cea de-a treia linie se afla numarul $Q$. Pe fiecare dintre urmatoarele $Q$ linii se afla un numar natural $B$, si o secventa de cifre din baza $B$, definita ca $P$ in enunt.

h2. Date de ieşire

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

Fişierul de ieşire $basequery.out$ va contine $Q$ linii. Pe fiecare linie $i$ se va gasi un singur numar natural, reprezentand reprezentand raspunsul pentru intrebarea $i$.

h2. Restricţii

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

* $1 ≤ N ≤ 40.000$
* $1 ≤ Q ≤ 100.000$
* $1 ≤ A ~i~ ≤ 2.000.000.000, unde 1 ≤ i ≤ N$
* $2 ≤ B ≤ 16$
* $1 &le; P ~(10)~ < 1024, unde P ~(10)~ este valoarea reprezentata de secventa P in baza B, transformata in baza 10.$
* $P poate incepe si cu cifra 0(zero).$
* $Secventa P nu are mai mult de 40 caractere.$

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

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

| 5
85 82 5 5515515 243
3
2 01
10 5
16 F3
| 33093757
27577665
243

|

h3. Explicaţie

h3. Explicatie
 
Pentru primul query, avem $B = 2$ si $P = 01$. Transformand numerele din sir in baza $2$, avem:
 
85 ~(10)~ = 1010101 ~(2)~ - Secventa $01$ apare de $3$ ori
82 ~(10)~ = 1010010 ~(2)~ - Secventa $01$ apare de $2$ ori
5 ~(10)~ = 101 ~(2)~ - Secventa $01$ apare $1$ data
5515515 ~(10)~ = 10101000010100011111011 ~(2)~ - Secventa $01$ apare de $6$ ori
243 ~(10)~ = 11110011 ~(2)~ - Secventa $01$ apare $1$ data

...

In concluzie, raspunsul este: $3 * 85 + 2 * 82 + 1 * 5 + 6 * 5515515 + 1 * 243 = 33093757$.

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

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

9759