Problem z rozwiązaniem zadania Python


(haker146) #1

Witam na zajęciach z programowania w języku Python otrzymałem do wyliczenia poniższe zadanie:

Uwagę Johna Smitha zwrócił neon reklamowy supermarketu. Miał dziwną treść. Ni mniej ni więcej, tylko 7.11. Zaintrygowany wszedł do obszernego hallu.

— O co chodzi? — zapytał, w gruncie rzeczy bez sensu, witającego go sprzedawcę.

— To proste. Od 7 rano do 11 wieczór. Tak handlujemy — usłyszał w odpowiedzi.

Istotnie, było to proste. Wiedział, co chciał wiedzieć i właściwie mógł już wyjść. Ale, skoro się już weszło do sklepu … Wybrał z obficie zaopatrzonych półek cztery produkty i niemal natychmiast usłyszał głos kasjera.

— Płaci pan 7.11.

— Co? Za to? — zapytał.

— 7 dolarów i 11 centów za zakupione towary — odpowiedź była precyzyjna.

— Bo takie są godziny otwarcia sklepu, co? — zdumiał się John.

— Nie. Po prostu odnotowałem ceny poszczególnych towarów, pomnożyłem i wyszło 7.11 — wyjaśnił kasjer.

— Panie, toż to trzeba dodać, a nie pomnożyć!

— Istotnie, przepraszam — palce kasjera znów zastukały w klawisze podręcznego komputerka — płaci pan 7.11.

— To są kpiny! — oburzył się John.

— Ale skąd, proszę sprawdzić.

Po sprawdzeniu okazało się, że kasjer, a właściwie jego komputerek, oba razy nie popełnił błędu. Jakie ceny miały towary zakupione przez Johna Smitha?

(Delta 12/1983)

Należy:

Załadować program napisany w języku Python rozwiązujący zadanie. Program nie powinien tym razem wykorzystywać żadnych dodatkowych pakietów oprócz pakietu time udostępniającego metody pozwalające na pomiar czasu wykonania programu.
W notatkach proszę podać rozwiązanie zadania, tj. ceny towarów, liczbę sprawdzonych pełnych czwórek liczb oraz czas wykonania programu w sekundach.
Najbardziej brutalne rozwiązanie wymaga sprawdzenia 255 551 481 441 czwórek liczb (za to 0 pkt.). Nieco mniej brutalne redukuje tę liczbę do 10 558 353 555 (za to 1pkt.). Kolejne udoskonalenie i mamy tyko 5 509 775 380 sprawdzeń (2 pkt.). Rozwiązanie, które zna prowadzący wymaga sprawdzenia 5435 czwórek liczb (5 pkt.).

Poprosiłbym o pomoc w jego rozwiązaniu, lub naprowadzenie na poprawne rozwiązanie. Z góry dziękuję.


#2

Napisz w którym momencie utknąłeś.


(haker146) #3

Utknąłem na ustaleniu takich warunków granicznych żeby nie liczyć całej kombinacji liczb.


(enedil) #4

Ok. Z równań abcd=7.11, a+b+c+d=7.11 przejdźmy do przyjaźniejszych, bo działających na liczbach całkowitych:
100a*100b*100c*100d=711*10^6, 100a+100b+100c+100d=711. Wprowadźmy nowe zmienne x, y, z, t = 100a, 100b, 100c, 100d. Jako, że t = 711-(x+y+z), to jeśli czwórka x, y, z, t ma spełniać układ równań, to t jest jednoznacznie wyznaczone przez pozostałe liczby - to prowadzi do rozwiązania, które jest pomiędzy 2 a 5 punktami (711^3 czwórek do sprawdzenia). Powodzenia, pobaw się dalej.


(angh) #5

Ciekawy sposob jest tutaj:
http://mathforum.org/library/drmath/view/55897.html
mozna to zrobic bez brute force :wink: