Fişierul intrare/ieşire:afaceri.in, afaceri.outSursăLot Iasi 2008, Baraj 5
AutorAdrian AirineiAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test1.25 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Afaceri

Ana are o afacere cu un şir S format din N litere mici, memorate pe poziţiile 0, 1, ..., N-1. Şirul este considerat circular (adică după litera de pe poziţia N-1 se consideră că urmează litera de pe poziţia 0).
Asupra acestui şir Ana trebuie să efectueze eficient următoarele operaţii:

  1. Update( poz, c): schimbă litera de pe poziţia poz din şir în litera c
  2. Query( poz1, poz2, len): consideră subsecvenţa din şir care începe pe poziţia poz1 şi subsecvenţa care începe pe poziţia poz2, ambele secvenţe având lungimea len, şi determină distanţa Hamming dintre cele două subsecvenţe.

Distanţa Hamming dintre două subsecvenţe s1 şi s2 de lungime len este definită ca numărul de poziţii i pentru care s1[i] ≠ s2[i], 0 ≤ i < len.
Pentru că volumul datelor de intrare este mare, vom genera operaţiile asupra şirului pe baza unor valori date, după cum urmează:

  • M – numărul total de operaţii;
  • Q – frecvenţa operaţiilor Update (după fiecare Q-1 operaţii Query se execută un Update);
  • L A0 A1 A2 R – valori (iniţial date) în funcţie de care generăm operaţiile.
  • Vectorii X cu LX elemente naturale şi respectiv Y cu LY elemente naturale conţin valori utilizate de asemenea pentru generarea operaţiilor (vectorii X şi Y fiind indexaţi de la 0).
    Pseudocodul care descrie modul de generare a operaţiilor Update/Query:
for (i = 1; i <= M; i++)
    {if (i % Q == 0) // generez o operatie Update
         {poz=A1%N; c='a' + A2 % 26;	    
          S[poz] = c; }
	    else //generez o operatie Query
          { poz1 = A0%N; poz2=A1%N; len=L+A2%(N-L+1); }
      //recalculez A0 A1 A2 	     
      VAL = ((long long)A2*X[i%LX]+Y[i%LY])%R; A0 = A1; A1 = A2; A2 = VAL; 
    }

Cerinţă

Scrieţi un program care să efectueze operaţiile generate şi să determine suma răspunsurilor la operaţiile Query.

Date de intrare

Fişierul de intrare afaceri.in va conţine pe prima linie numerele naturale N, M, Q, L, A0, A1, A2 şi R. A doua linie va conţine numărul natural LX, apoi vor urma LX numere naturale X0 X1 ... XLX-1 reprezentând valorile vectorului X. A treia linie va conţine numărul natural LY, apoi vor urma LY numere naturale Y0 Y1 ... YLY-1 reprezentând valorile vectorului Y. A patra linie va conţine N litere mici reprezentând şirul dat. Valorile numerice aflate pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire afaceri.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând suma răspunsurilor la query-urile date.

Restricţii

  • 1 ≤ L < N ≤ 2000
  • 1 ≤ LX, LY ≤ 5000
  • 1 ≤ M ≤ 2.000.000
  • 1 ≤ [M/Q] ≤ 20 001
  • 1 ≤ Xi ≤ R ∀ i
  • 1 ≤ Yi ≤ R ∀ i
  • 1 ≤ A0, A1, A2, R ≤ 1.000.000

Exemplu

afaceri.inafaceri.out
7 15 4 3 5 6 7 8
3 5 4 1
3 7 2 6
lrqagor
65
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content