[SMWP_106] Diament Bez Skazy

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_106/

Opis problemu:
Musisz pomóc Jasiowi sprawdzić czy podany diament jest warty zakupu. Wartym określamy go wtedy, gdy konstrukcja przyjmijmy dla ułatwienia fizyczna diamentu jest grafem pełnym, a więc takim, który zawiera każde możliwe połączenie z innym wierzchołkiem. Zakładając, że graf jest spójny, a relacje są różne i wzajemne tak naprawdę musimy tylko sprawdzić, czy dana liczba połączeń może być konstrukcją grafu pełnego. Jeśli może wypisujemy „TAK”, gdy na pewno nie może wypisujemy „NIE”.

Rozwiązanie:
Aby rozwiązać ten problem musimy najpierw zastanowić się jaka ilość połączeń może występować w grafie pełnym. Odpowiedz brzmi: n(n-1)/2, dla n będącego liczbą wierzchołków grafu. Teraz pozostaje nam jedynie utworzyć odpowiednie równanie: n(n-1)/2=K, gdzie K jest liczbą połączeń podaną w zapytaniu. Jeśli podane równanie posiada takie n naturalne, dla którego równanie jest prawdziwe wówczas istnieje taki graf pełny o n wierzchołkach i K połączeniach. W bardzo łatwy sposób możemy to także sprawdzić korzystając z obserwacji Diofantosa. Mianowicie jeśli sqrt(K*8+1) jest liczbą wymierną to wtedy z danej liczby połączeń różnych i wzajemnych możemy zbudować graf pełny. Warto również zauważyć, że kolejne liczby będące ilością połączeń w grafach pełnych o n wierzchołkach są tak naprawdę kolejnymi liczbami trójkątnymi, gdzie grafpełny(n)=trójkatne(n-1).

Print Friendly

Dodaj komentarz

Wymagane pola są oznaczone *.