4134 - Raza 1

Pe planeta Quadratia, locuitorii folosesc forme pătrate în tot ceea ce construiesc. Ei au trimis pe solul planetei N mașini speciale de apărare, numite rovere, care se deplasează pe traiectorii ce descriu pătrate. Harta planetei poate fi privită ca un tablou bidimensional cu număr infinit de linii și coloane, numerotarea acestora începând cu 1. Fiecare element al acestui tablou se identifică prin numărul liniei, respectiv numărul coloanei pe care se găsește.

Fiecare rover este descris prin 3 numere naturale nenule L, C și R, reprezentând poziția (linia L și coloana C) elementului din colțul din stânga-sus al pătratului ce descrie traiectoria, respectiv lungimea R a laturii acestuia. Toate roverele pornesc inițial din elementul din colțul stânga-sus al pătratului ce descrie traiectoria, pe care o parcurg în sensul acelor de ceasornic, traversând câte un element pe secundă. Ele sunt programate să parcurgă această traiectorie fără a se opri. Este posibil ca mai multe rovere să se afle, la un moment dat, la aceeași poziție de pe hartă.

Rectilinienii sunt singurii dușmani ai quadratienilor, ei deosebindu-se de aceștia prin folosirea consecventă a liniilor drepte în tot ceea ce construiesc. Rectilinienii au construit o armă laser de mare putere, pe care vor să o folosească la distrugerea roverelor quadratiene. Arma a fost adusă în poziția (1,1) de pe harta planetei, adică elementul de pe prima linie și prima coloană.

Arma poate emite o singură rază distructivă, timp de o secundă, dezafectând în acest timp toate roverele aflate în secunda respectivă pe diagonala principală a tabloului care descrie harta planetei. Arma nu poate fi detectată în primele S secunde. Traiectoria roverelor poate trece prin poziția în care a fost amplasată arma, fără a o putea detecta în primele S secunde.

În imagine avem două rovere, acestea fiind identificate prin tripletele de numere 4, 2, 6, respectiv 6, 9, 4. Traiectoria primului rover începe din poziția (4, 2) și are latura 6. Numerele de pe traiectorie reprezintă secunda la care se parcurge respectivul element al tabloului. Roverul va ajunge din nou în poziția inițială la secundele 21, 41, 61, ... Primul rover intersectează, la prima sa trecere, diagonala principală în două puncte: (4, 4) la secunda 3 și (7, 7) la secunda 9. Al doilea rover intersectează diagonala principală într-un singur punct, (9, 9) la secundele 10, 22, 34, ...

Cerința

Scrieţi un program care să rezolve următoarele cerințe:

• Determină numărul roverelor a căror traiectorie se intersectează cu diagonala principală a tabloului ce descrie harta.
• Determină numărul maxim de rovere, care pot fi distruse simultan, într-o singură secundă, înainte de trecerea celor S secunde, precum și secunda minimă în care se poate realiza acest lucru.

Date de intrare

Datele de intrare se citesc din fișierul raza.in, care are următoarea structură:

• pe prima linie se află numărul natural T ∈ {1, 2}, semnificând numărul cerinței de rezolvat.
• pe a doua linie se află numerele naturale nenule N și S, separate printr-un spațiu, reprezentând numărul roverelor, respectiv numărul de secunde în care arma nu este detectată.
• pe următoarele N linii se află câte 3 numere naturale nenule, L C R, separate prin câte un spațiu, reprezentând coordonatele poziției inițiale, respectiv lungimea laturii traiectoriei fiecărui rover.

Date de ieșire

Datele de ieșire se vor afișa în fișierul raza.out, care are următoarea structură în funcție de cerință:

• dacă T = 1, pe prima linie se va afișa numărul roverelor a căror traiectorie se intersectează cu diagonala principală;
• dacă T = 2, pe prima linie se vor afișa două numere naturale, separate printr-un spațiu, reprezentând numărul maxim de rovere dezactivate și secunda minimă în care se poate realiza acest lucru.

Restricții și precizări

• 1 ≤ N ≤ 10.000
• 1 ≤ S ≤ 100.000
• 1 ≤ L, C ≤ 50.000
• 3 ≤ R ≤ 1000
• 1 ≤ Numărul maxim de rovere care se intersectează cu raza armei ≤ 1000.
• Pentru 28 de puncte, T = 1
• Pentru 72 de puncte, T = 2

Exemplu:

raza.in

1
2 100
4 2 6
6 9 4

raza.out

2

Explicație

Cerința este 1. Exemplul reprezintă desenul din enunț.

<syntaxhighlight lang="python" line="1"> from collections import defaultdict

def calculate_trajectory(L, C, R):

   trajectory = []
   for t in range(4 * R):
       if t < R:
           trajectory.append((L, C + t))
       elif t < 2 * R:
           trajectory.append((L + t - R, C + R - 1))
       elif t < 3 * R:
           trajectory.append((L + R - 1, C + R - 1 - (t - 2 * R)))
       else:
           trajectory.append((L + R - 1 - (t - 3 * R), C))
   return trajectory

def solve(N, rovers, S):

   diagonal_intersections = defaultdict(list)
   
   for rover in rovers:
       L, C, R = rover
       trajectory = calculate_trajectory(L, C, R)
       for i, (x, y) in enumerate(trajectory):
           if x == y:
               t = i + 1
               diagonal_intersections[t].append((L, C, R))
   
   count_per_second = defaultdict(int)
   for t, rovers_at_t in diagonal_intersections.items():
       if t <= S:
           count_per_second[t] += len(rovers_at_t)
   
   if not count_per_second:
       return 0, None, None
   
   max_destructions = max(count_per_second.values())
   min_time = min(t for t in count_per_second if count_per_second[t] == max_destructions)
   
   return len(diagonal_intersections), max_destructions, min_time

1. Example usage

N = 2 rovers = [(4, 2, 6), (6, 9, 4)] S = 10 print(solve(N, rovers, S)) </syntaxhighlight>