Page 168 - MATINF Nr. 1
P. 168
˘
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 |