Page 126 - MATINF Nr.2

˘
126 PROBLEME DE INFORMATICA PENTRU CONCURSURI

• 1 ≤ d ≤ 1000
• Distant , a dintre cei doi stˆalpi A s , i B este 30000
• Distant , ele de la stˆalpul A la puncte sunt numere naturale
• Distant , a minim˘a va fi afis , at˘a trunchiat˘a la primele 3 zecimale
• Toate punctele de pe un cablu sunt distincte
• Se acord˘a 40% din punctaj pentru determinarea corect˘a a minimului din cerint , ˘a

Exemplu

stalpi.in stalpi.out Explicat , ie
3 100 211.803 Sunt n = 3 perechi de puncte, k = 2 culori,
50 1 200 2 100 1 3 2 codificate cu 1 s , i 2.
250 2 100 1 300 2 2 1 Necesarul minim de sˆarm˘a este 211.803.
Se leag˘a punctul P3 de punctul Q2
(ambele au culoarea 1). Se leag˘a punctul P2
de punctul Q1 (ambele au culoarea 2).

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

Memorie total˘a disponibil˘a 4 MB.

Doru Anastasiu Popescu, Pites , ti (ONI 2011)

ˆ
I 28 (hoteluri). Intr-o stat , iune turistic˘a exist˘a n hoteluri apart , inˆand unui lant , hotelier. Pentru
a mics , ora costurile legate de comunicarea ˆıntre angajat , ii hotelurilor, managerul lant , ului hotelier
se hot˘ar˘as , te s˘a realizeze o ret , ea de comunicare telefonic˘a prin conectarea hotelurilor prin cablu.
Conexiunea trebuie f˘acut˘a astfel ˆıncˆat orice dou˘a hoteluri s˘a poat˘a comunica direct sau prin
intermediul altor hoteluri s , i ˆın plus s˘a existe dou˘a hoteluri ˆıntre care s˘a se realizeze leg˘atura
prin dou˘a modalit˘at , i diferite.

Cerint , ˘a

S˘a se scrie un program care pentru n dat s˘a determine num˘arul de modalit˘at , i de realizare a
conexiunii ˆıntre hoteluri, respectˆand cerint , ele din enunt , .

Date de intrare
Fis , ierul de intrare hoteluri.in va cont , ine num˘arul n.

Date de ies , ire
Fis , ierul de ies , ire hoteluri.out va cont , ine pe prima linie num˘arul din cerint , ˘a.