Page 164 - MATINF Nr. 1

˘
164 PROBLEME DE INFORMATICA PENTRU CONCURSURI

• Pentru toate testele problemei exist˘a solut , ie, adic˘a exist˘a cel put , in un arici care poate
ajunge la c˘asut , a aricilor

• Dac˘a cei doi arici parcurg aceeas , i distant , ˘a pˆan˘a la c˘asut , a aricilor, este considerat cˆas , tig˘ator
primul arici
• Mere c˘azute din pom se pot g˘asi s , i ˆın locuri la care aricii nu au acces
• Pentru rezolvarea corect˘a a primei cerint , e se acord˘a 20% din punctaj, iar pentru cerint , a a
doua 80% din punctaj
• Pentru primele 30% dintre testele care verific˘a cerint , a 2) avem m ≤ 20 s , i n ≤ 20
• Pentru determinarea corect˘a a numerelor Nr s , i Dmin se acord˘a 80% din punctajul testului,
iar pentru determinarea corect˘a a num˘arului NrM se acord˘a 20% din punctaj

Exemple
arici.in arici.out Explicat , ie
1 24 p = 1
5 6 Exist˘a 24 de pomi ˆın livad˘a la care au
3 5 acces ambii arici, s , i anume tot , i pomii cu
1 2 12351 except , ia celor 6 pomi care au num˘arul de
5 1 46123 mere c˘azute 46, 78, 89 sau 96.

15 12 37 12 78 19
16 17 18 19 25 20
21 25 26 89 25 25
24 78 29 31 24 89
23 25 46 25 96 25

arici.in arici.out Explicat , ie
2 1 5 3 p = 2
5 6 Ariciul cu num˘arul de ordine 1 se afl˘a la
3 5 pomul de coordonate (1,2) s , i poate ajunge
1 2 12351 la c˘asut , a aricilor pe traseul:
5 1 46123 (1,2),(1,3),(1,4),(2,4),(2,5),(3,5),
15 12 37 12 78 19 parcurgˆand o distant , ˘a de 5 dam.

16 17 18 19 25 20 De asemenea mai exist˘a s , i alt , i doi pomi de
21 25 26 89 25 25 la care ar putea pleca ariciul 1 s , i ar parcurge
24 78 29 31 24 89 aceeas , i distant , ˘a de 5 dam pˆan˘a la c˘asut , a
23 25 46 25 96 25 aricilor, s , i anume pomii de coordonate (2,1)
s , i (3,2).
Ariciul 2 poate ajunge la c˘asut , a aricilor
parcurgˆand o distant , ˘a de 6 dam, pe traseul:
(5,1),(5,2),(5,3),(5,4),(5,5),(4,5),(3,5).

Timp maxim de execut , ie: 0.5 secunde/test.

Memorie total˘a disponibil˘a 8 MB, din care 2 MB pentru stiv˘a.

Adriana Oprea, Pites , ti