1781 - Intersectii

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

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>