Fişierul intrare/ieşire:magnet.in, magnet.outSursăBaraj Yakuția 2015
AutorCatalin FrancuAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Magnet

Ion a colecţionat magneţi de frigider cu cuvinte pe ei, până când a făcut rost de toate cuvintele de K litere din mulţimea {A, B, C, D}. Apoi a aşezat aceste cuvinte într-un pătrat, astfel:

  • Cuvintele care încep cu litera A stau în sfertul din stânga-sus
  • Cuvintele care încep cu litera B stau în sfertul din dreapta-sus
  • Cuvintele care încep cu litera C stau în sfertul din stânga-jos
  • Cuvintele care încep cu litera D stau în sfertul din dreapta-jos
  • Fiecare din cele patru sferturi este dispus similar, împărţind cuvintele după a doua lor literă
  • Ion procedează similar pentru fiecare din cele K litere.

De exemplu, pentru K = 3, dreptunghiul rezultat este

AAA AAB ABA ABB BAA BAB BBA BBB
AAC AAD ABC ABD BAC BAD BBC BBD
ACA ACB ADA ADB BCA BCB BDA BDB
ACC ACD ADC ADD BCC BCD BDC BDD
CAA CAB CBA CBB DAA DAB DBA DBB
CAC CAD CBC CBD DAC DAD DBC DBD
CCA CCB CDA CDB DCA DCB DDA DDB
CCC CCD CDC CDD DCC DCD DDC DDD

Apoi Ion îşi pune Q întrebări de tipul: de câte ori apare litera X în dreptunghiul delimitat de magneţii (l1, c1) şi (l2, c2) inclusiv?

Date de intrare

Fişierul de intrare magnet.in conţine pe prima linie valorile întregi K şi Q. Următoarele Q linii descriu câte o întrebare sub forma unui tuplu X l1 c1 l2 c2.

Date de ieşire

În fişierul de ieşire magnet.out se vor tipări răspunsurile la cele Q întrebări, câte unul pe linie, în ordinea de la intrare.

Restricţii

  • 1 ≤ K ≤ 20
  • 1 ≤ Q ≤ 100.000
  • Pentru 30% din teste, 1 ≤ K ≤ 10 şi 1 ≤ Q ≤ 2.000
  • X ∈ { A, B, C, D } (întotdeauna litere mari)
  • 1 ≤ l1 ≤ l2 ≤ 2K
  • 1 ≤ c1 ≤ c2 ≤ 2K

Exemplu

magnet.inmagnet.out
3 2
A 2 3 5 4
C 5 5 5 8
8
0

Explicaţie

Dreptunghiul (2,3)-(5,4) conţine şirurile ABC ABD ADA ADB ADC ADD CBA CBB. În total, acestea conţin 8 litere A.

Dreptunghiul (5,5)-(5,8) conţine şirurile DAA DAB DBA DBB. Acestea nu conţin nicio literă C.

Trebuie sa te autentifici pentru a trimite solutii. Click aici