Witam czytających!
Nie mogę rozwiązać jednego z zadań II etapu I OIG(wiem że niby to byy proste zadania i trochę mi wsytd z tego powodu) - http://main.edu.pl/pl/archive/oig/1/bie
Wpadłem na pomysł aby utworzyć graf w którym dana bierka(a) będzie połączona tylko z bierkami(b) z którym może utworzyć trójkąt( wymyśliłem taki warunek (a >= 3b i a < b) lub (b>=a i a> b)), a następnie usuwam te wierzchołki, które mają najmniej krawędzi aż dojdę do momentu w którym wszystkie wierzchołki będą miały dokładnie m-1 krawędzi(dla wielkości tego zmniejszanego grafu równej m). Niestety to nie działa. Czy wie ktoś dlaczego? Pzdr bartek
0
0
Nie będę się tu rozpisywał tylko po prostu dam ci linka do oficjalnego omówienia. Jest tam opis rozwiązania, sama implementacja jest bardzo prosta, gdzieś chyba nawet na dysku mam kod do tego zadania, więc jakbyś nie mógł sobie poradzić to pisz:
http://oi.edu.pl/old/html/zadania/oig1/Etap2/bie.pdf
0
A co tu omawiać? Posortować według długości, najdłuższa bierka musi być krótsza niż suma długości dwóch najkrótszych, więc jedyny problem to wyznaczanie ile odrzucić najdłuższych i ile najkrótszych by ten warunek był spełniony.
Nie rozumiem po co bardziej kombinować.