W ramach projektu należy napisać program w języku Python rozwiązujący poniższe zadanie. Następnie program należy wysłać do oceny poprzez następujący kurs na platformie UPEL:
Projekt zostanie oceniony w następujący sposób:
Termin nadsyłania rozwiązań: 10 lutego 2026, 23:59
W królestwie Bajtycji zaczęły niedawno publicznie pojawiać się grupy tricytów - heretycznego odłamu Kościoła Shannona wyznającego wyższość obliczeń opartych o system trójkowy. W obawie przed potencjalnymi aktami antydwójkowego terroru, Biuro Bezpieczeństwa Bajtycji (BBB) postanowiło podjąć kroki zapobiegawcze. Infiltracja społeczności tricytów nie jest jednak sprawą prostą - dołączenie do ich szeregów wymaga zaproszenia “z wewnątrz”. Każdy neofita w momencie swojego dołączenia może zaprosić swoich przyjaciół. By nie osłabiać swojej pozycji społecznej w grupie, nikt nie chce zapraszać osoby bardziej popularnej od siebie. Ze względu na to, wszyscy tricyci przyjaźniący się z nowo zaproszoną osobą są zawsze również przyjaciółmi zapraszającego.
Zamiast próbować umieścić wśród wyznawców swoich agentów, BBB postanowiło sięgnąć po środki technologiczne. W celu inwigilacji społeczności tricytów na ich urządzeniach elektronicznych umieszczone zostaną wirusy pozwalające monitorować komunikację. Nie każdy cel jest równie łatwy - atak na niektórych bardziej technologicznie świadomych i ostrożnych tricytów będzie bardziej kosztowny. Celem BBB jest osiągnięcie sytuacji, w której żadna para członków nie może porozumiewać się pomiędzy sobą elektronicznie w sekrecie - jak najmniejszym kosztem. Twoim zadaniem jest wybrać osoby, których komputery zostaną zarażone.
Do zaimplementowanej funkcji solve przekazane zostaną następujące argumenty:
Przykładowe wywołanie może wyglądać następująco:
solve(
[(1, 2), (2, 3), (1, 3), (2, 4), (3, 4), (3, 5), (2, 6), (4, 6)],
[2, 5, 2, 3, 1, 4],
)
Dla takiego zestawu danych rozwiązanie to wybór osób 2, 3 i 4, o łącznym koszcie 10.
Infrastruktura do projektu dostępna jest w formie archiwum z plikami źródłowymi w języku Python
(link na dole). Szkielet rozwiązania znajduje się w pliku example.py - importuje on funkcję
runtests z modułu data i uruchamia ją, podając swoją funkcję rozwiązującą jako argument.
Przesyłane rozwiązania powinny mieć postać analogicznego pliku. Przetestować rozwiązanie można
uruchamiając ów plik, np.
python3 example.py
Na wyjście standardowe wypisane zostaną informacje o rezultatach poszczególnych testów, a także podsumowanie z ilością testów zakończonych sukcesem i przybliżonym łącznym czasie obliczeń.