Fişierul intrare/ieşire:	intersectii.in, intersectii.out	Sursă	ONI 2012 - clasa a 9-a
Autor	Gheorghe Manolache	Adăugată de	Simoiu Robert •SpiderMan
Timp execuţie pe test	0.2 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Intersectii

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. În dreptunghiul din figura alăturată, segmentul PA trece prin 3 pătrate 2-intersectate, segmentul PB trece prin 9 pătrate 2-intersectate, segmentul PC trece prin 13 pătrate 2-intersectate, iar segmentul PD prin 7.

Cerinţă

Se dau două numere naturale w şi h reprezentând lungimile laturilor dreptunghiului ABCD, un număr natural n şi n numere naturale x₁, x₂, … x_n. 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

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

Exemplu

Cum se trimit solutii?