Page 127 - MATINF Nr.2

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 127

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 1000
• Dou˘a leg˘aturi de comnunicare ˆıntre dou˘a hoteluri sunt diferite dac˘a au cel put , in un cablu
de leg˘atur˘a diferit
• Dou˘a conexiuni ale lant , ului hotelier sunt diferite dac˘a au cel put , in un cablu care apare
ˆıntr-o singur˘a conexiune
• Comunicarea dintre dou˘a hoteluri printr-o leg˘atur˘a direct˘a este ˆın ambele sensuri

Exemplu
hoteluri.in hoteluri.out Explicat , ie
4 22 Dac˘a se codific˘a hotelurile cu numerele 1, 2, 3, 4
trei dintre variantele de conexiune sunt urm˘atoarele:
1) [1,2];[2,3];[1,3];[3,4]
2) [1,2];[2,3];[1,3];[3,4];[1,4]
3) [1,2];[2,3];[1,3];[2,4];[1,4]

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 4 MB.

Doru Anastasiu Popescu, Pites , ti

I 29 (asezare). Un restaurant dispune de n mese s , i 4n scaune. Mesele sunt numerotate cu
numerele 1, 2, . . . , n, iar scaunele cu numerele 1, 2, . . . , 4n. Se dores , te s˘a se as , eze toate scaunele
la mese, astfel ˆıncˆat la fiecare mas˘a s˘a fie cˆate exact 4 scaune, ordinea de as , ezare a scaunelor la
mas˘a nu are important , ˘a.
Cerint , ˘a

S˘a se scrie un program care pentru n dat determin˘a toate modalit˘at , ile de as , ezare a scaunelor
modulo 9973.
Date de intrare

Fis , ierul de intrare asezare.in va cont , ine pe prima linie num˘arul n.
Date de ies , ire

Fis , ierul de ies , ire asezare.out va cont , ine num˘arul din cerint , ˘a, modulo 9973.
Restrict , ii s , i preciz˘ari

• 0 < n < 2001
• Dou˘a modalit˘at , i de as , ezare a scaunelor sunt diferite dac˘a exist˘a o mas˘a cu cel put , in un
scaun diferit
• n modulo k ˆınseamn˘a restul ˆımp˘art , irii lui n la k
Exemplu

asezare.in asezare.out Explicat , ie
2 70 Cˆateva as , ez˘ari posibile: M1: 1, 2, 3, 4; M2: 5, 6, 7, 8
M1: 1, 2, 3, 5; M2: 4, 6, 7, 8 M1: 1, 2, 6, 4; M2: 5, 3, 7, 8

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 4 MB.
Doru Anastasiu Popescu, Pites , ti