Page 10 - MATINF Nr. 11-12

10 D.A. Popescu, C. B˘alc˘au, D. Constantin

Locurile de parcare care au asociate numere prime se numesc locuri VIP, iar un hotel este
a
a
a
considerat norocos dac˘ nu exist˘ locuitori rezident , i care s˘ aib˘ locurile de parcare ˆın mult , imea
a
locurilor dorite de el.
Cerint , e
Cunoscˆand n - num˘arul locurilor de parcare, p - num˘arul de locuitori rezident , i ˆın stat , iune,
m - num˘arul de hoteluri, L 1 , L 2 , . . . , L p - numerele locurilor de parcare ale locuitorilor rezident , i
s , i [a 1 , b 1 ], [a 2 , b 2 ], . . . , [a m , b m ] intervalele cu locurile de parcare dorite de hoteluri, se cere:

1. num˘arul de hoteluri norocoase s , i numerele de ordine ale acestor hoteluri, ˆın ordine
cresc˘atoare;
2. num˘arul maxim de locuri parcare VIP solicitate de un hotel, care nu apart , in locuitorilor
rezident , i din stat , iune.

Date de intrare
Pe prima linie a fis , ierului de intrare parcare.in se afl˘a num˘arul C, num˘ar care poate fi 1
a
sau 2 s , i reprezint˘ cerint , a ce trebuie rezolvat˘a.
Pe cea de-a doua linie se afl˘a, separate prin cˆate un spat , iu, n, p s , i m, reprezentˆand num˘arul
locurilor de parcare, num˘arul de locuitori rezident , i ˆın stat , iune, respectiv num˘arul de hoteluri.

Pe linia a treia se afl˘a, separate prin cˆate un spat , iu, numerele locurilor de parcare ale
locuitorilor rezident , i: L 1 , L 2 , . . . , L p .

Pe urm˘atoarele m linii se afl˘a intervalele cu locurile libere dorite de hoteluri a i b i , i =
1, 2, . . . , m.

Date de ies , ire
Dac˘a C este 1, fis , ierul de ies , ire parcare.out va cont , ine numerele de la cerint , a 1, adic˘a
num˘arul de hoteluri norocoase s , i numerele de ordine ale acestor hoteluri, ˆın ordine cresc˘atoare,
separate prin cˆate un spat , iu.
Dac˘a C este 2, fis , ierul de ies , ire parcare.out va cont , ine num˘arul de la cerint , a 2, adic˘a
num˘arul maxim de locuri parcare VIP solicitate de un hotel, care nu apart , in locuitorilor rezident , i
din stat , iune.

Restrict , ii s , i preciz˘ari

• 1 ≤ p ≤ n ≤ 2000000;

• 1 ≤ L i ≤ n, i = 1, 2, . . . , p;

• 1 ≤ a i ≤ b i ≤ n, i = 1, 2, . . . , m;

• 1 ≤ m ≤ 10000, 1 ≤ p ≤ 10000.

• Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 20 de puncte.
a
a
• Pentru rezolvarea corect˘ a cerint , ei 2 se vor acorda 80 de puncte.