Page 168 - MATINF Nr. 1

˘
168 PROBLEME DE INFORMATICA PENTRU CONCURSURI

ˆ
egal˘a cu k. In cazul ˆın care veverit , a vrea s˘a se deplaseze de la un pom la altul mai ˆındep˘artat,
aceasta trebuie s˘a ris , te s˘a fie alergat˘a de cˆaini.

Veverit , a dores , te s˘a afle:

- de cˆate ori trebuie s˘a ris , te s˘a fie alergat˘a de cˆaini pentru a se deplasa ˆın fiecare pom;

- distant , a cea mai mic˘a pe care trebuie s˘a o parcurg˘a pe jos pentru a se deplasa ˆın tot , i pomii
din parc.

Cerint , ˘a
Cunoscˆand numerele n, k s , i coordonatele pomilor, determinat , i:

1. de cˆate ori trebuie s˘a ris , te veverit , a s˘a fie alergat˘a de cˆaini pentru a se deplasa ˆın fiecare
pom;

2. distant , a cea mai mic˘a pe care trebuie s˘a o parcurg˘a pe jos veverit , a pentru a se deplasa ˆın
tot , i pomii din parc.

Date de intrare

Fis , ierul de intrare veverita.in cont , ine pe prima linie un num˘ar natural p. Pentru toate testele
de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe linia a doua se afl˘a n si k, separate printr-un spat , iu, iar pe urm˘atoarele n linii perechi de
numere naturale de forma x y, ce reprezint˘a coordonatele pomilor.

Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire veverita.out se va scrie un singur num˘ar natural repre-
zentˆand de cˆate ori trebuie s˘a ris , te s˘a fie alergat˘a de cˆaini veverit , a pentru a se deplasa ˆın fiecare
pom.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire veverita.out se va scrie distant , a cea mai mic˘a pe care
trebuie s˘a o parcurg˘a pe jos veverit , a pentru a se deplasa ˆın tot , i pomii din parc.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 500

• Coordonatele punctelor sunt numere naturale mai mici sau egale cu 1000000

• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj
• 20% din testele cu p = 2 au n ≤ 20

• Pentru distant , a dintre dou˘a puncte se va folosi distant , a Manhattan, adic˘a distant , a dintre
P(x 1 , y 1 ) s , i Q(x 2 , y 2 ) este
|x 1 − x 2 | + |y 1 − y 2 |