Fişierul intrare/ieşire:caps.in, caps.outSursăOJI 2017, clasa a 10-a
AutorGheorghe ManolacheAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Caps

Miruna a descoperit un nou joc. Ea dispune de litere mari şi mici ale alfabetului englez şi construieşte succesiv şiruri de litere din ce în ce mai lungi. Ea defineşte operaţia CAPS a unei litere, ca fiind transformarea literei respective din literă mare în literă mică sau invers, din litera mică în literă mare. Pentru fiecare şir S, Miruna asociază un nou şir Sc, numit şir CAPS, care se obţine aplicând operaţia CAPS asupra tuturor literelor din şirul S. Miruna a inventat o altă operaţie pentru un şir de litere S, numită NEXT, prin care obţine un nou şir SN care are structura SScScS (este format în ordine de la stânga la dreapta din literele lui S, apoi de două ori succesiv literele şirului Sc, iar apoi urmează din nou literele şirului S). De exemplu, şirului S = "Ham" îi corespunde şirul CAPS Sc = "hAM" şi dacă se aplică şi operaţia NEXT asupra şirului S, obţine şirul SN = "HamhAMhAMHam". Iniţial, Miruna construieşte un şir S de K litere. Apoi, ea construieşte un nou şir obţinut prin aplicarea operaţiei NEXT asupra şirului S. Miruna doreşte să obţină succesiv şiruri de litere din ce în ce mai lungi aplicând operaţia NEXT asupra şirului construit în etapa precedentă.
Astfel, pentru K = 3 şi S = "Ham", Miruna va construi şirurile "HamhAMhAMHam", "HamhAMhAMHamhAMHamHamhAMhAMHamHamhAMHamhAMhAMHam" şi aşa mai departe. Miruna continuă procedeul de construire până când obţine un şir final suficient de lung.

Cerinţe

Miruna vă roagă să răspundeţi la Q întrebări de tipul:
Dacă se dă un număr natural N, ce literă este în şirul final pe poziţia N şi de câte ori a apărut această literă în şirul final, de la începutul şirului final până la poziţia N inclusiv?.

Date de intrare

Pe prima linie a fişierului caps.in se află două numere naturale separate prin spaţiu reprezentând valorile K (lungimea şirului iniţial) şi Q (numărul de interogări). Pe linia următoare se află şirul iniţial S de lungime K. Pe următoarele Q linii se va afla câte un număr N, reprezentând cerinţa unei întrebări.

Date de ieşire

În fişierul de ieşire caps.out, se vor afla Q linii, iar pe fiecare linie câte două valori separate cu un spaţiu reprezentând răspunsul la o întrebare (litera de pe poziţia N în şirul final şi numărul său de apariţii până la poziţia N inclusiv).

Restricţii

  • 1 < K ≤ 100.000
  • 0 < Q ≤ 50.000
  • 0 < N ≤ 1018
  • Pentru fiecare test se acordă 40% din punctaj dacă toate literele interogărilor din test sunt corecte şi 60% din punctaj dacă toate numerele de apariţii ale literelor, până la poziţiile N din interogările testului, sunt corecte.
  • Pentru teste în valoare de 15 puncte: K ≤ 250, Q ≤ 1000, N ≤ 3000.
  • Pentru alte teste în valoare de 20 de puncte: N ≤ 100000.
  • Pentru alte teste în valoare de 20 de puncte: K ≤ 3000, Q ≤ 1000.
  • Miruna vă garantează că a construit un şir final de lungime mai mare decât N.
  • Prima poziţie în şir este considerată poziţia 1.

Exemplu

caps.incaps.out
3 1
Ham
5
A 1

Explicaţie

Pe poziţia 5 se va afla litera A, numărul de apariţii al ei de la poziţia 1 la poziţia 5 este 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?