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ța
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
Fișierul de intrare caps.in conține pe prima linie 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 și precizări
1 < K ≤ 1000000 < Q ≤ 500000 < 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
Ndin interogările testului, sunt corecte. - Pentru teste în valoare de 25 puncte (în concurs 15):
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.in
3 1 Ham 5
caps.out
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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Caps:
#include <bits/stdc++.h>
using namespace std;
ifstream in("caps.in");
ofstream out("caps.out");
char s1[100010],s2[100010];
unsigned int f1a[27][100010],f1A[27][100010],f2a[27][100010],f2A[27][100010];
long long l1,q,n,cat,r,dif,w;
int main()
{
in>>l1>>q;in.get();
//in.get(s1,101);
in>>s1;
for(int i=0;i<l1;++i)
if(s1[i]>='a')
{s2[i]=s1[i]-32;f1a[s1[i]-'a'][i]=1;f2A[s2[i]-'A'][i]=1;}
else
{s2[i]=s1[i]+32;f1A[s1[i]-'A'][i]=1;f2a[s2[i]-'a'][i]=1;}
for(int i=0;i<26;++i)
for(int j=1;j<l1;++j)
{
f1a[i][j]+=f1a[i][j-1];
f1A[i][j]+=f1A[i][j-1];
f2a[i][j]+=f2a[i][j-1];
f2A[i][j]+=f2A[i][j-1];
}
long long d=2ll*l1;
char c;
for(;q;--q)
{
in>>n;
cat=n/d;//nr bucati duble complete
r=n%d;//rest de cautat
long long nr=n/l1;//nr bucati mici
if(n%l1) nr++;//nr de bucati simple;
w= __builtin_parityll(nr-1ll); //numerotare de la 0
if(!w)//incepe cu s1
if(r==0ll) //se termina la sf s1
{c=s1[l1-1];
dif=0ll;
}
else
if(r<=l1) //se termina pe bucata s1
{c=s1[r-1]; if(c>='a') dif=f1a[c-'a'][r-1]; else dif=f1A[c-'A'][r-1]; }
else //de termina pe s1 dar nu e luata si precedenta, care e evident s2
{c=s1[r-l1-1];if(c>='a') dif=f2a[c-'a'][l1-1]+f1a[c-'a'][r-l1-1]; else dif=f2A[c-'A'][l1-1]+f1A[c-'A'][r-l1-1]; }
else //incepe cu s2
if(r==0ll) //se termina cu s2
{
c=s2[l1-1];
dif=0ll;
}
else
if(r<=l1) //se termina pe bucata s2
{c=s2[r-1];if(c>='a') dif=f2a[c-'a'][r-1]; else dif=f2A[c-'A'][r-1]; }
else //se termina pe s2 dar e luata si precedenta care e s1
{c=s2[r-l1-1];if(c>='a') dif=f1a[c-'a'][l1-1]+f2a[c-'a'][r-l1-1]; else dif=f1A[c-'A'][l1-1]+f2A[c-'A'][r-l1-1]; }
unsigned long long sol=0ll;
if(c>='a')
sol=dif+1ll*cat*(f1a[c-'a'][l1-1]+f2a[c-'a'][l1-1]);
else
sol=dif+1ll*cat*(f1A[c-'A'][l1-1]+f2A[c-'A'][l1-1]);
out<<c<<' '<<sol<<'\n';
}
out.close();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1999 Caps
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1999 Caps de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!