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 |
   163   164   165   166   167   168   169   170   171   172   173