Bolt

Suntem la Lotul Național de Informatică de la Deva și, cum comisia este prea ocupată pregătind problemele, cei N concurenți se plictisesc. Ei au început să joace jocul Bolt, care se desfășoară după următoarele reguli:

• Toți cei N participanți se așază în cerc în ordine trigonometrică. Participantul 2 se așază la dreapta participantului 1, participantul 3 la dreapta participantului 2 și așa mai departe. Participantul 1 va fi la dreapta participantului N.
• Se alege o cifră specială C.
• Participantul cu numărul 1 începe numărătoarea (zice 1) și ceilalți continuă în sens trigonometric (spre dreapta). Numărătoarea se continuă cu participantul cu numărul 2, și așa mai departe.
• Atunci când un participant ajunge la un număr care este multiplu al lui C sau conține cifra C în scrierea sa în baza 10, acesta trebuie să spună cuvântul “fulger” în loc de acel număr.
• De fiecare dată când cuvântul “fulger” este spus, se inversează ordinea jocului (dacă se mergea în sens trigonometric, se va continua în sens orar și invers).

Primele 18 mutări ale unui joc cu N = 5 participanți și C = 7 este descris mai jos (cuvântul “fulger” este marcat prin litera F):

De fiecare dată când cineva greșește, respectivul trebuie să bea un pahar de lapte cald și jocul se continuă (pentru că după cum bine știți, laptele afectează viteza de reacție a participanților și face jocul mai amuzant).

Cum cei N participanți nu sunt suficient de încurcați de laptele cald, ei decid să facă jocul și mai interesant, alegând o mulțime S de cifre speciale distincte, în loc de o singură cifră, și aplicând regulile de mai sus simultan pentru toate cifrele din S. De exemplu, dacă S = {3, 7}, atunci participantul la rând trebuie să spună cuvântul “fulger” de fiecare dată când numărul curent este multiplu de 3 sau de 7 sau când conține cifrele 3 sau 7 în reprezentarea sa.

De asemenea, pentru a fi și mai buni la acest joc, majoritatea participanților calculează în avans ce numere urmează să zică și la care dintre acestea trebuie să spună “fulger”. Comisia, care acum stă și privește, vrea să știe ce concurent va spune un număr dat K (sau “fulger”-ul corespunzător numărului, după caz) și răsplătește cu puncte pe oricine va putea răspunde.

Detalii de implementare

Veți implementa funcția cu următorul antet:

int play_bolt(int N, std::string K, std::vector<int> S)

Funcția play_bolt va fi apelată exact o dată în cadrul unui test. N reprezintă numărul de participanți la joc, K este numărul de care este interesată comisia, reprezentat ca std::string (care poate fi foarte mare, deoarece e mult timp de pierdut la lot), iar S reprezintă mulțimea de cifre speciale. Se garantează că S va conține cifre distincte și nenule, în ordine strict crescătoare.

Funcția trebuie să returneze un număr natural cuprins între 1 și N, reprezentând soluția problemei. În caz contrar, graderul va termina programul și va nota testul ca fiind incorect.

Punctare

Subtask 1 (11 puncte)

• $3 \le N \le 10^5$
• $1 \le K < 10^6$
• $1 \le |S| \le 9$

Subtask 2 (50 puncte)

• $3 \le N \le 10^5$
• $1 \le K < 10^{12}$
• $|S| = 1$

Subtask 3 (20 puncte)

• $3 \le N \le 10^5$
• $1 \le K < 10^{2000}$
• $|S| = 1$

Subtask 4 (19 puncte)

• $3 \le N \le 10^5$
• $1 \le K < 10^{2000}$
• $1 \le |S| \le 9$

Model de grader

Graderul va citi de la consolă datele de intrare în următorul format:

• linia 1: N K (separate printr-un spațiu), cu specificațiile din enunț
• linia 2: M, reprezentând numărul de elemente ale mulțimii S
• linia 3: M cifre distincte cuprinse între 1 și 9, reprezentând mulțimea S

Grader-ul va afișa la consolă răspunsul vostru, pe o singură linie, ca pe un număr întreg în baza 10.

Exemple

stdin

5 10
1
7

stdout

4

stdin

5 14
1
7

stdout

5

stdin

9 1031214
1
1

stdout

9

stdin

21 410209
3
3 8 9

stdout

12

stdin

17 610305
1
7

stdout

9

stdin

17 820756190090
1
7

stdout

11

Explicație

Exemplele 1 și 2 sunt descrise în enunț. În exemplul 3, jocul va alterna între concurenții 1 și 9, deoarece fiecare va spune “fulger” (jocul se dovedește a fi destul de monoton pentru ceilalți 7 concurenți).

În celelalte cazuri, va trebui să ne credeți pe cuvânt.