Fişierul intrare/ieşire:tetris3.in, tetris3.outSursăLot Alba Iulia 2010, Baraj 1
AutorAndrei Paul PuniAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tetris3

Qwerty a inventat o nouă variantă a faimosului joc TETRIS. În varianta sa, jocul prezintă un şir de N boluri numerotate de la 1 la N care în momentul iniţial sunt goale. Qwerty vrea să facă M operaţii pe acest şir de boluri. O operaţie constă în alegerea unui interval continuu de boluri [A, B] şi adăugarea în fiecare bol din acest interval a unei bomboane de culoare C. De asemenea, dacă în orice moment de timp într-un anumit bol se află două bomboane de aceeaşi culoare C ele dispar, iar dacă C este mai mare decât 1 atunci în locul acestora apare o bomboană de culoare C-1.

Operaţiile pe care le va face Qwerty sunt definite prin relaţie recurentă. El începe cu numerele A1 B1 C1 şi pentru oricare i mai mare decât 1, utilizează apoi relaţiile:

  • Ai = Min(N, (Ai-1 * i) % 1008989)
  • Bi = Min(N, (Bi-1 * i) % 1008989)
  • Ci = (Ci-1*X + Y) % 47 + 1

Qwerty va pune câte o bomboană de culoare Ci în toate bolurile aflate între Min(Ai,Bi) şi Max(Ai,Bi).

Cerinţă

Deoarece Qwerty e mofturos din fire, doreşte ca înainte de a face operaţiile, să ştie care este numărul de bomboane care va ramane în boluri şi de aceea vă roagă să aflaţi acest număr pentru el.

Date de intrare

Pe prima linie a fişierului de intrare tetris3.in se vor afla şapte numere naturale N M A B C X Y având semnificaţiile din enunţ.

Date de ieşire

În fişierul de ieşire tetris3.out veţi afişa un singur număr reprezentând numărul bomboane ramase in boluri.

Restricţii

  • 5 ≤ N,M ≤ 400 000
  • 1 ≤ A, B ≤ N
  • 1 ≤ C ≤ 47
  • 1 ≤ X, Y ≤ 100 000
  • Modul de generare a datelor de intrare nu influenţează în nici un fel rezolvarea problemei!

Exemplu

tetris3.intetris3.out
5 5 2 4 30 2 10
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content