Page 119 - MATINF Nr. 7

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 119

Exemplu

fractii.in fractii.out
3 17 10
12 100 20 21
34 20 3 25
20 21

Doru Constantin, Pites , ti

I 98 (dist). Se dau n puncte ˆın plan prin coordonatele lor. Determinat , i punctele care s˘a aib˘a
suma distant , elor la celelalte puncte minim˘a.
Cerint , ˘a

Cunoscˆand coordonatele celor n puncte, determinat , i numerele de ordine ale punctelor cu
suma distant , elor la celelalte puncte minim˘a.

Restrict , ii

• 1 ≤ n ≤ 100000;

• Coordonatele punctelor sunt numere naturale ≤ 1000000.

Date de intrare

Fis , ierul dist.in cont , ine pe prima linie n, apoi pe liniile urm˘atoare coordonatele punctelor
separate printr-un spat , iu.
Date de ies , ire

Fis , ierul de ies , ire dist.out va cont , ine pe prima linie indicii punctelor cerute ˆın enunt , s , i
distant , a minim˘a separate prin cˆate un spat , iu. Indicii vor fi afis , at , i ˆın ordine cresc˘atoare.

Exemplu
dist.in dist.out
3 2 30
5 0
5 10
5 30

Doru Anastasiu Popescu, Pites , ti

I 99 (fotbal). Lotul unei echipe de fotbal este format din n fotbalis , ti identificat , i prin numerele
1, 2, . . . , n. Fiecare dintre aces , tia are alocat cˆate dou˘a numere de la 1 la 2n, pe care s˘a le
foloseasc˘a pe spatele tricourilor. Nu exist˘a doi fotbalis , ti care s˘a aib˘a alocat acelas , i num˘ar.
Antrenorul foloses , te ˆıntr-o echip˘a exact k juc˘atori s , i dores , te s˘a afle:

• Num˘arul de echipe pe care le poate forma cu k juc˘atori, notat cu Ne. Dou˘a echipe sunt
distincte dac˘a difer˘a prin cel put , in un juc˘ator;

• Num˘arul total Nt de variante de tricouri (identificate prin numerele de pe tricoul fiec˘arui
fotbalist) pe care le poate avea o echip˘a de k juc˘atori.