algograf

Projekt 1: Szczęśliwe dzielniki

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ń: 20 grudnia 2025, 23:59

Treść zadania

W Królestwie Bajtycji zapanowała moda na astronumerologię - osobliwe połączenie interpretacji nieba i przypisywania nadprzyrodzonych własności liczbom naturalnym. Nowym trendem wśród bajtycjan stało się noszenie ubrań i akcesoriów z nadrukowanymi “szczęśliwymi liczbami”. Każda liczba naturalna ma dla każdej osoby pewną indywidualną miarę szczęścia, zależną od jej dzielników oraz długości. Dla każdej osoby astrologowie wyznaczają pewien skończony zestaw szczęśliwych dzielników, wraz z ich miarą szczęścia. Ponadto, im dłuższa jest liczba, tym mniej jest szczęśliwa, proporcjonalnie do jej długości (przybliżanej jako jej logarytm dziesiętny). Konkretnie, dla wyznaczonego zbioru dzielników d_1,...,d_k i ich miar szczęścia c_1,...,c_k, szczęście L(n) danej liczby n jest równe

L(n) = suma {po i takich, że d_i dzieli n} c_i - 5 log10 n

Jako sprawny algorytmik z żyłką do biznesu, postanawiasz nieco zarobić pomagając ludziom wyznaczać swoje szczęśliwe liczby. Obserwację nieba i wyznaczanie szczęścia dzielników pozostawiasz astrologom: Twoim zadaniem będzie na podstawie danych od nich otrzymanych, wyznaczyć dla każdego najszczęśliwszą możliwą liczbę. Przepełniony zapałem, siadasz przed pustą kartką papieru, chwytasz w dłoń długopis i zaczynasz projektować algorytm, który już wkrótce przyniesie Ci sławę i bogactwo…

Dane wejściowe

Do zaimplementowanej funkcji solve przekazane zostaną następujące argumenty:

Przykładowe wywołanie może wyglądać następująco:

solve([
    (6, 5),
    (9, 1),
    (10, 6),
    (15, 7),
    (13, 6),
    (17, 5)])

Funkcja solve powinna zwracać liczbę naturalną $n$ maksymalizującą szczęście L(n). Dla powyższych danych najbardziej szczęśliwą liczbą jest n = 390. Dzielą ją liczby 6, 10, 15 oraz 13, co daje jej szczęście 5 + 6 + 7 + 6 = 24, natomiast nieszczęście z jej długości to 5 log10 390 ~ 12.955, zatem jej łączne szczęście to ~ 11.045.

Instrukcja

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ń.

Warunki techniczne

Pliki