1781 - Intersectii

Enunt

Dreptunghiul ABCD are laturile de lungimi w şi h, numere naturale pare. Acest dreptunghi este desenat pe o foaie de matematică şi este descompus în w ∙ h pătrate de latură 1. Vârfurile A, B, C şi D sunt plasate în colţurile unor pătrate de latură 1. Se alege un punct P din interiorul dreptunghiului ABCD, situat în colţul unui pătrat de latură 1 şi se uneşte prin segmente de dreaptă cu cele patru colţuri ale dreptunghiului. Unele segmente intersectează pătrate de latură 1 în exact două puncte distincte, altele într-un singur punct. Numim pătrat 2-intersectat, un pătrat de latură 1 intersectat de un segment în exact 2 puncte distincte.

Cerinţa

Se dau două numere naturale w şi h reprezentând lungimile laturilor dreptunghiului ABCD, un număr natural n şi n numere naturale x1, x2,… xn cu propietatea din enunt. Punctul P se plasează, pe rând, în toate punctele interioare dreptunghiului ABCD care sunt colţuri ale unor pătrate de latură 1. Pentru fiecare valoare x[i] (1 ≤ i ≤ n), determinaţi numărul de segmente distincte care trec prin exact x[i] pătrate 2-intersectate.

Date de intrare

Fişierul de intrare intersectii.in conţine pe prima linie trei numere naturale w, h (reprezentând dimensiunile dreptunghiului) şi n. Următoarele n linii conţin câte un număr natural x[i] cu semnificaţia de mai sus.

Date de ieșire

Fişierul de ieşire intersectii.out va conţine n linii. Pe fiecare linie i va fi scris numărul de segmente care trec prin exact x[i] pătrate 2-intersectate, obţinute după plasarea punctului P în fiecare colţ al unui pătrat de latură 1 din interiorul dreptunghiului ABCD.

Restricţii şi precizări

• 2 ≤ w , h ≤ 2000 numere naturale pare;
• 2 ≤ n ≤ 100000;
• punctul P se alege doar în interiorul dreptunghiului;
• pentru 40% din teste 2 ≤ w, n, h ≤ 500.

Exemplul 1

intersectii.in

4 6 2

3 5

intersectii.out

12

4

Explicație

Se pot obţine 12 segmente care trec prin exact 3 pătrate 2-intersectate şi 4 segmente care trec prin exact 3 pătrate 2-intersectate.

Rezolvare

<syntaxhighlight lang="python" line> def count_intersected_squares(w, h):

   # Calculăm numărul de pătrate 2-intersectate pentru fiecare punct P
   return (w - 1) * (h - 1) * 2

def main():

   # Citim datele de intrare din fișier
   with open("intersectii.in", "r") as fin:
       w, h, n = map(int, fin.readline().split())
       x_values = [int(fin.readline()) for _ in range(n)]

   # Calculăm numărul de pătrate 2-intersectate pentru dreptunghi
   num_intersected_squares = count_intersected_squares(w, h)

   # Calculăm numărul de segmente care trec prin fiecare x[i] pătrate 2-intersectate
   results = [x * num_intersected_squares for x in x_values]

   # Scriem rezultatele în fișierul de ieșire
   with open("intersectii.out", "w") as fout:
       fout.write("\n".join(map(str, results)) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>