Page 11 - MATINF Nr. 11-12

Concursul de Informatic˘ Programming Day 11
a

Exemplu

parcare.in parcare.out
1 3 1 3 5
40 4 5
1 36 17 13
5 12
35 38
3 6
15 18
21 33
2 3
40 4 5
1 36 17 13
5 12
35 38
3 6
15 18
21 33

Explicat , ii
Hotelurile cu numerele de ordine 1, 3, 5 nu cont , in locuri de parcare alocate rezident , ilor
stat , iunii. Num˘arul maxim de locuri VIP nealocate rezident , ilor s , i solicitate de un hotel este
3. Hotelurile care au solicitat num˘ar maxim de locuri de parcare VIP sunt 1 (cu locurile VIP
nealocate rezident , ilor: 5, 7, 11) s , i 5 (cu locurile VIP nealocate rezident , ilor: 23, 29, 31).
Timp maxim de execut , ie: 0.2 secunde/test.
Memorie total˘ disponibil˘a: 12 MB.
a
Solut , ie

Cerint , a 1 (20 puncte)

Varianta 1

Parcurgem intervalele hotelurilor s , i verific˘am dac˘ cont , in locuri de parcare alocate rezident , ilor.
a
Vom num˘ara s , i afis , a hotelurile care nu cont , in locuri de parcare alocate rezident , ilor.
Varianta 2

Vom construi un vector v de dimensiune n cu componente de tip bool, ˆın care v[i] =true,
dac˘a i este loc de parcare alocat rezident , ilor din stat , iune, respectiv v[i] =false, ˆın caz contrar.
Folosind acest vector, determin˘am ˆın vectorul s de dimensiune n num˘arul de locuri de parcare
repartizate rezident , ilor pe intervale de forma [1, i], i = 1, 2, . . . , n. Astfel:
s[0] = 0, iar pentru i = 1, 2, . . . , n dac˘a v[i] =false ⇒ s[i] = s[i − 1] + 1, altfel s[i] = s[i − 1].

Num˘arul de locuri de parcare ocupate de rezident , i pe segmente de forma [a[i], b[i]] va fi egal
cu s[b[i]] − s[a[i] − 1], i = 1, 2, . . . , m. Pentru a rezolva cerint , a 1 vom num˘ara s , i afis , a hotelurile
cu s[b[i]] − s[a[i] − 1] = 0.

Cerint , a 2 (80 puncte) Vom construi cu ciurul lui Eratostene vectorul v de dimensiune n
cu componente de tip bool, ˆın care v[i] =true, dac˘a i este neprim s , i v[i] =false in caz contrar.