Fişierul intrare/ieşire:basequery.in, basequery.outSursăInfoarena Monthly 2014, Runda 3
AutorMihai-Alexandru DusmanuAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Basequery

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).

Date de intrare

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.

Date de ieşire

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.

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 ≤ 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.

Exemplu

basequery.inbasequery.out
5
85 82 5 5515515 243
3
2 01
10 5
16 F3
33093757
27577665
243

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content