Fișierul intrare/ieșire | magnet.in, magnet.out | Sursă | Baraj Yakuția 2015 |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Alexandru Valeanu • AlexandruValeanu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.