Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-16 09:56:34.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:namlei.in, namlei.outSursăStelele Informaticii 2006, clasele 11-12
AutorTiberiu-Lucian FloreaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.3 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Namlei

Exista N + 1 orase dispuse in linie, numerotate in intervalul [0...N], fiecare avand cate K obiective strategice numerotate in intervalul [0...K - 1]. Astfel, orice obiectiv poate fi identificat printr-o pereche (i, j), i reprezentand numarul orasului in care se afla respectivul obiectiv, iar j numarul de ordine al obiectivului. Avand in vedere aceste notatii, pot exista muchii doar intre un obiectiv (i, x) si un obiectiv (i + 1, y) (adica din orase consecutive).

Intre doua obiective (i, x) si (i + 1, y) exista cel putin o muchie (posibil mai multe).

Operatiile care se pot face sunt urmatoarele:

  • U: Toate muchiile dintre orasele i si i + 1 sunt eliminate. Se introduc alte muchii, astfel incat sa se pastreze conditia precedenta.
  • Q: Se calculeaza si se afiseaza numarul de drumuri distincte formate din j - i muchii intre obiectivele (i, x) si (j, y).

Date de intrare si de iesire

Pe prima linie a fisierului namlei.in se afla numerele N si K, separate de un spatiu. Pe a doua linie a fisierului se afla numerele X si Y, separate de un spatiu. Pe fiecare din urmatoarele N linii se afla cate un triplet de numere (cnt, j, k). Acest triplet de pe linia a i-a (i intre 0 si N - 1) inseamna ca intre orasele i si i + 1 exista (in afara de cele K * K muchii obligatorii) cnt muchii dintre care prima este (i, j) - (i + 1, k). Daca a (w - 1)-a muchie este (i, j) - (i + 1, k), a w-a muchie (i, j') - (i + 1, k') se calculeaza dupa urmatoarea formula:

j' = (j * X + k * w * Y) % K
k' = (j * w * X + k * Y) % K.

Cele w muchii sunt numerotate 0 ... w - 1.

Pana la sfarsitul fisierului, fiecare pereche de doua linii reprezinta o operatie U sau Q. Pe prima dintre linii se afla tipul operatei, iar pe a doua parametrii care determina aceasta operatie.

In cazul unei operatii de tipul U:

A doua linie contine numerele i, cnt, j, k separate prin cate un spatiu. Acest cvadruplet inseamna ca (dupa eliminarea muchiilor care existau deja) intre orasele i si i + 1 exista (in afara de cele K * K muchii obligatorii) cnt muchii dintre care prima este (i, j) - (i + 1, k). Daca a (w - 1)-a muchie este (i, j) - (i + 1, k), a w-a muchie (i, j') - (i + 1, k') se calculeaza dupa urmatoarea formula:

j' = (j * X + k * w * Y + 1) % K
k' = (j * w * X + k * Y + 1) % K

Cele w muchii sunt numerotate 0 ... w - 1.

ATENTIE ! Din cauza unor considerente intim legate de natura problemei, aceste formule difera printr-un +1 de formulele precedente.

In cazul unei operatii de tipul Q:

A doua linie contine numerele i, x, j, y separate prin cate un spatiu. In acest caz trebuie afisat numarul de drumuri distincte de exact j - i muchii intre obiectivele (i, x) si (j, y). i este strict mai mic decat j. Toate rezultatele se vor afisa modulo 997. Raspunsurile vor fi afisate in fisierul namlei.out in ordinea in care sunt puse intrebarile, fiecare raspuns pe o linie separata.

Restrictii

  • 1 ≤ N ≤ 30 000
  • 3 ≤ K ≤ 8
  • 1 ≤ cnt ≤ 120
  • Exista cel mult 1 000 de operatii din fiecare tip

Exemplu

namlei.innamlei.out
4 3
17 19
3 1 0
3 2 2
4 0 2
4 2 2
Q
1 2 3 0
U
1 4 1 0
Q
0 2 3 0
4
21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?