Laiko ribojimas: 1.0s

Atminties ribojimas: 128MB

Duomenų failas: lmio_2008_skambuciai_jau.in

Rezultatų failas: lmio_2008_skambuciai_jau.out

Jei norite pateikti savo sprendimą - prisijunkite.

Skambučiai (LMIO 2008)

Būrys draugų susitarė, kad kai tik pirmasis draugas sužinos tai, jis skambučiu apie tai praneš kitam draugui, tuomet jie abu skambins likusiems ir taip toliau, kol sužinos visi. Vienas skambutis užtrunka vieną laiko momentą. Tuo pačiu metu gali skambinti ir kalbėtis bet koks skaičius skirtingų draugų porų, tačiau vienu metu bet kuris draugas gali kalbėtis tik su vienu draugu.

Užduotis

Iš viso yra n draugų. Pirmasis draugas tai sužino nuliniu laiko momentu. Kiek mažiausiai laiko momentų prireiks, kol tai sužinos visi draugai?

Pradiniai duomenys

Pirmoje eilutėje įrašytas draugų skaičius n.

Rezultatai

Jūsų programa turi įrašyti mažiausią laiko momentų skaičių, kurio pakanka, kad apie tai sužinotų visi n draugų.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
5
 
3
 Galima tokia schema:
  • per pirmą laiko momentą pirmasis draugas informuoja antrąjį;
  • per antrąjį laiko momentą antrasis draugas informuoja trečiąjį;
  • o per trečiąjį laiko momentą pirmasis draugas informuoja ketvirtąjį, o antrasis – penktąjį draugą. 
11
 
4
 Šiuo atveju informacijai pasklisti reikia mažiausiai keturių laiko momentų. 
2
 
1