Průměr grafu
Na vstupu je dán prostý neorientovaný graf bez smyček, je třeba určit počet jeho komponent a velikost průměru komponenty s největším průměrem.Průměr grafu, pokud je souvislý, je roven vzdálenosti mezi dvěma navzájem nejvzdálenějšími uzly v grafu (takových uzlů může být případně v grafu více). Vzdálenost mezi dvěma uzly je délka nejkratší cesty mezi nimi, přičemž délka cesty je rovna počtu hran v cestě. Uvažujeme graf s alespoň dvěma uzly.
Vstup
Na vstupu jsou čtyři kladná celá čísla N1, N2, D a HD zapsaná na jednom řádku a oddělená navzájem vždy jednou mezerou. Vrcholy grafu jsou všechna přirozená čísla z množiny {N1, N1+1, N1+2, ..., N2}. Hrany grafu jsou konstruovány takto: Každý uzel reprezentujeme jako binární číslo zapsané pomocí přesně D znaků 0/1. Pokud je číslo dostatečně malé, jeho zápis obsahuje příslušný počet úvodních nul. Dva uzly jsou spojeny hranou, pokud Hammingova vzdálenost těchto jejich zápisů je menší nebo nejvýše rovna HD. Hodnota D je nejvýše 62, hodnota N2 je nejvýše 2D−1, hodnota N1 je vždy alespoň o 2 a nejvýše o 5000 menší než N2. Hodnota HD se pohybuje v rozmezí od 1 do 5.Výstup
Na výstupu jsou dvě čísla v jednom řádku oddělená mezerou. První určuje počet komponent zadaného grafu, druhé určuje maximální průměr ze všech komponent grafu (pokud je graf souvislý, je druhým číslem průměr celého grafu).Příklad 1
Vstup:2 7 4 1Výstup:
1 3
Příklad 2
Vstup:5 11 4 2Výstup:
1 2