.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » xor2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
xor2


Timp maxim de execuţie / test:
1.4s
Memorie totala disponibilă / stivă:
32MB / 1MB

Lui Hadrianus îi plac matricele infinite care sunt generate după o anumită regulă. Înainte de primul baraj, el se gândeşte la o astfel de matrice, în care elementul de pe linia i şi coloana j este egal cu i xor j. Hadrianus doreşte să determine suma elementelor pentru unele submatrici ale matricii formate după regula de mai sus.
Se numeşte submatrice de coordonate (L1, C1, L2, C2), cu 1 ≤ L1 ≤ L2 şi 1 ≤ C1 ≤ C2, o zonă dreptunghiulară din matrice care are colţul stânga-sus pe linia L1 şi coloana C1 şi colţul dreapta-jos pe linia L2 şi coloana C2.
Operaţia xor reprezintă operaţia de disjuncţie exclusivă realizată pe biţii operanzilor. În Pascal, operatorul corespunzător este xor, iar în C/C++ acest operator este ^. De exemplu, 20 xor 14 = 26. Matricea formată are primele elemente conform figurii alăturate.


Cerinţă

Scrieţi un program care citeşte coordonatele a T submatrice şi afişează pentru fiecare dintre aceste submatrice suma elementelor sale modulo P (restul împărţirii sumei la P), unde P este un număr prim.

Date de intrare

Fişierul de intrare xor2.in conţine pe prima linie T şi P, cu semnificaţia de mai sus. Fiecare din următoarele T linii conţine câte 4 numere naturale L1 C1 L2 C2, despărţite printr-un spaţiu, reprezentând coordonatele unei submatrice.

Date de ieşire

Fişierul de ieşire xor2.out conţine exact T linii. Linia cu numărul i conţine suma modulo P a elementelor celei de a i-a submatrice din fişierul de intrare.

Restricţii

1 ≤ T ≤ 20 000
• Pentru fiecare submatrice din cele T, 1 ≤ L1 ≤ L2 ≤ 108 şi 1 ≤ C1 ≤ C2 ≤ 108
P este număr prim mai mic sau egal decât 30 000.
• Liniile şi coloanele matricei sunt numerotate începând cu 1.

Exemple

xor2.inxor2.outExplicaţii
5 29473 1 3 2 4 2 2 12 15 10000 10000 11000 11000 123 51 54667341 1878099 1234567 1234567 1234678 1234678 14 1165 23799 18591 549 Prima submatrice este formată din elementele 2, 5, 1 şi 6. Suma modulo 29473 a acestor elemente este:
(2 + 5 + 1 + 6) % 29473 = 14.

autor: Stud. Filip-Cristian Buruiană
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, simetric1, cern, pesti, plaja, tango, arb1, v2d, cuiburi, telefon, teroristi
De acelaşi autor: forum, lac, acop, volei, standard, nori, simetric1
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre operaţii pe biţi: barfa, cod, gray, cartonase, plimbare, excursie, xor, vector, ro, nrbinar, radio, chimie2, dans, metro, caini, newcomp, viteza, bcast, aritma, pereti, morse, paritate, gradina, game1, efect, gxor, lgdrum, qtri, patrate7, panda, cript
surse trimise | ajutor