1162 - Rox

Enunţ

Părinții lui Rox au cumpărat de curând un teren care are N metri lățime și M metri lungime, pe care l-au împărţit în pătrate cu latura de un metru, denumite celule. Văzând planul terenului, lui Rox i-a venit o idee. Ea s-a decis să semene florile ei preferate în etape, pe U dintre parcele de teren. Denumirile florilor sunt litere mari ale alfabetului englez. O parcelă este un dreptunghi inclus în teren, cu laturile paralele cu ale terenului și care conține doar celule complete.

În fiecare etapă în care Rox seamănă flori, procedează astfel: alege o parcelă pentru care reține indicii celulelor din stânga sus și dreapta jos, stabilește tipul florii pe care dorește să o semene peste tot în parcelă, apoi scrie aceste informații pe o foaie de hârtie. Documentându-se pe Internet, Rox ajunge la concluzia că apare următorul fenomen ciudat: dacă într-o celulă se seamănă același tip de floare într-un număr par de etape, semințele de acel tip pur și simplu dispar.

Când finalizează semănatul, Rox le povesteşte părinților despre isprava ei. Entuziasmați, părinții fetei îi pun mai multe întrebări de tipul ”Câte tipuri de flori au rămas semănate în celula de pe linia L și coloana C?”

Cerinţă

Deoarece Rox a plantat foarte multe flori, ea nu poate să răspundă rapid întrebărilor părinților, așa încât vă cere ajutorul și vă va răsplăti efortul cu maxim 100 de puncte.

Date de intrare

Pe prima linie a fișierului rox.in se află 3 numere: N, M și U, separate prin câte un spațiu și având semnificația din enunț. Pe fiecare din următoarele U linii se află: L1 C1 L2 C2 T, separate prin câte un spațiu și reprezentând datele scrise de Rox pe foaie, corespunzătoare unei etape de semănat (coordonatele colțurilor din stânga sus și dreapta jos ale parcelei și T, tipul florii).

Pe linia U+2 se află Q, numărul de întrebări puse de părinții lui Rox.

Pe fiecare din următoarele Q linii se află L C (coordonatele celulei despre care părinții lui Rox vor informații).

Date de ieşire

Fișierul de ieșire rox.out va conține Q linii. Pe fiecare dintre cele Q linii se vor afla răspunsurile la întrebările părinților lui Rox, în ordinea în care acestea au fost puse.

Restricţii şi precizări

• 1≤N,M≤1000
• 1≤U≤100.000
• 1≤Q≤100.000
• L1≤L2; C1≤C2
• Inițial pe teren nu era semănată nicio floare.
• T reprezintă o literă mare a alfabetului englez.
• Întrebările se pot repeta.
• La fiecare a (2*k+1)-a semănare într-o celulă a unui anumit tip de floare va rămâne o singură floare de acel tip în celulă
• Datele de intrare nu necesită validare.
• Pentru 35% din teste U * Q ≤ 30.000.000
• Pentru 35% din teste N, M ≤ 100, U ≤ 300
• Pentru 60% din teste N, M ≤ 800

Exemplu

rox.in

14 17 6

3 3 8 10 A

5 6 11 14 B

8 2 11 3 W

6 8 12 17 B

8 5 14 8 A

2 13 2 14 Z

4

4 5

7 9

5 10

8 3

rox.out

1

1

2

2

Explicație

În celula (4,5) se seamănă floarea A care rămâne acolo. În celula (7,9) se seamănă floarea A, apoi B, apoi iar B (la a doua semănare a florii de tipul B dispare floarea B). În final rămâne doar A. În celula (5,10) se seamănă A și B care rămân acolo. În celula (8,3) se seamănă A și W care rămân acolo. În figura de mai jos sunt marcate cu ? celulele corespunzătoare întrebărilor.

Rezolvare

<syntaxhighlight lang="python" line>

1. 1162 Rox

def validate_input(N, M, data, questions):

   for L1, C1, L2, C2, T in data:
       if not (1 <= L1 <= L2 <= N and 1 <= C1 <= C2 <= M):
           return False
       if not ('A' <= T <= 'Z'):
           return False
   for L, C in questions:
       if not (1 <= L <= N and 1 <= C <= M):
           return False
   return True

def read_input(file_path):

   with open(file_path, 'r') as file:
       N, M, U = map(int, file.readline().split())
       data = []
       for _ in range(U):
           L1, C1, L2, C2, T = file.readline().split()
           data.append((int(L1), int(C1), int(L2), int(C2), T))
       Q = int(file.readline())
       questions = [tuple(map(int, file.readline().split())) for _ in range(Q)]
   return N, M, data, questions

def count_remaining_flowers(N, M, data, questions):

   board = {}
   for L1, C1, L2, C2, T in data:
       for i in range(L1, L2 + 1):
           for j in range(C1, C2 + 1):
               if (i, j) not in board:
                   board[(i, j)] = {}
               if T in board[(i, j)]:
                   board[(i, j)][T] += 1
               else:
                   board[(i, j)][T] = 1

   results = []
   for L, C in questions:
       remaining_flowers = 0
       if (L, C) in board:
           for flower_count in board[(L, C)].values():
               if flower_count % 2 == 1:
                   remaining_flowers += 1
       results.append(remaining_flowers)
   return results

def write_output(file_path, results):

   with open(file_path, 'w') as file:
       for result in results:
           file.write(str(result) + '\n')

def main():

   input_file = "rox.in"
   output_file = "rox.out"
   
   # Citire date de intrare
   N, M, data, questions = read_input(input_file)

   # Validare date de intrare
   if not validate_input(N, M, data, questions):
       print("Date de intrare invalide!")
       return

   # Calculare numar de flori ramase pentru fiecare intrebare
   results = count_remaining_flowers(N, M, data, questions)

   # Scriere rezultate
   write_output(output_file, results)

if __name__ == "__main__":

   main()

</syntaxhighlight>