Fișierul intrare/ieșire magnet.in, magnet.out Sursă Baraj Yakuția 2015
Autor Cătălin Frâncu Adăugată de avatar AlexandruValeanu Alexandru Valeanu AlexandruValeanu
Timp de execuție pe test 0.5 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty

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.in magnet.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii