Zadanie:
Twój program ma odpowiednią , pozytywną, prostą część w formacie <numerator>/<denominator>
.
Dla tego wejścia musi znaleźć dwie frakcje.
- Ułamek, który jest mniejszy niż wkład.
- Ułamek większy niż wkład.
Obie frakcje muszą mieć niższy mianownik niż wkład. Ze wszystkich możliwych ułamków powinny mieć najniższą różnicę w stosunku do danych wejściowych.
Wydajność:
Wyjście twojego programu musi być:
- Ułamek mniejszy niż dane wejściowe w formacie
<numerator>/<denominator>
. - Po nim następuje spacja (kod ASCII 32).
- Po nim ułamek większy niż wejście, w formacie
<numerator>/<denominator>
.
Następująco:
«fraction that is < input» «fraction that is > input»
Zasady:
- Wszystkie wyprowadzane ułamki muszą być najniższe .
- Wszystkie wyprowadzane ułamki muszą być ułamkami właściwymi.
- Jeśli nie są możliwe żadne właściwe ułamki, które są dozwolone przez reguły, musisz podać dane wyjściowe
0
zamiast ułamka <wejście i1
zamiast ułamka> wejście. - Możesz wybrać, czy chcesz otrzymać ułamek jako argument wiersza poleceń (np
yourprogram.exe 2/5
), Czy monit o podanie danych przez użytkownika. - Możesz założyć, że twój program nie otrzyma nieprawidłowych danych wejściowych.
- Najkrótszy kod (w bajtach, w dowolnym języku) wygrywa.
Wszelkie niestandardowe argumenty wiersza polecenia (argumenty, które zwykle nie są wymagane do uruchomienia skryptu) są liczone do całkowitej liczby znaków.
Czego Twój program nie może robić:
- Zależy od wszelkich zasobów zewnętrznych.
- Zależy od posiadania określonej nazwy pliku.
- Wyprowadzaj cokolwiek innego niż wymagane wyjście.
- Uruchomienie zajmuje wyjątkowo długo. Jeśli program działa przez ponad minutę dla ułamków z 6-cyfrowym licznikiem i mianownikiem (np.
179565/987657
) Na komputerze przeciętnego użytkownika domowego, jest nieprawidłowy. - Frakcje wyjściowe z
0
jako mianownik. Nie możesz podzielić przez zero. - Wyprowadzaj ułamki
0
jako licznik. Twój program musi generować wyjście0
zamiast ułamka. - Zmniejsz ułamek wprowadzony. Jeśli ułamek podany jako dane wejściowe jest redukowalny, musisz użyć ułamka podczas wprowadzania.
- Twój program nie może być napisany w języku programowania, dla którego nie istniał publicznie dostępny kompilator / tłumacz przed opublikowaniem tego wyzwania.
Przykłady:
Wejście: 2/5
Wyjście: 1/3 1/2
Wejście: 1/2
Wyjście: 0 1
Wejście: 5/9
Wyjście: 1/2 4/7
Wejście: 1/3
Wyjście: 0 1/2
Wejście: 2/4
Wyjście: 1/3 2/3
Wejście: 179565/987657
Wyjście: 170496/937775 128779/708320
1/3 1/2
.Odpowiedzi:
Szałwia -
119117Szałwia jest potrzebna tylko w ostatnim wierszu, który dba o wynik. Wszystko inne działa również w Pythonie.
Wymień
raw_input()
sięsys.argv[1]
, że wejście odczytać z argumentem wiersza poleceń zamiast monitu. Nie zmienia to liczby postaci. (Nie działa w Pythonie bez wcześniejszego importowaniasys
).To zasadniczo rekurencyjnie konstruuje odpowiednią sekwencję Farey przy użyciu mediantów istniejących elementów, ale ogranicza się do tych elementów najbliższych wejściu. Z innego punktu widzenia uruchamia wyszukiwanie zagnieżdżone w odpowiednich sekwencjach Farey.
Prawidłowo przetwarza wszystkie przykłady w mniej niż sekundę na moim komputerze.
Oto wersja bez golfa:
źródło
exec
!Python 2.7 - 138
Zacząłem od oczywistego rozwiązania brutalnej siły, ale zdałem sobie sprawę, że ponieważ OP chciał być w stanie rozwiązać instancje za pomocą sześciocyfrowych liczników i mianowników w niecałą minutę, potrzebuję lepszego rozwiązania niż próbowanie trylionów możliwości. I znaleziono przydatny wzór na stronie Wikipedia na ciąg fareya: Jeżeli a / b, c / d, sąsiadują w jednej sekwencji Farey z
a/b<c/d
, a następnieb*c-a*b=1
. Pętla while wewnątrz mojego programu rozszerza ten fakt na liczby nieskrócone, używając gcd, którą oblicza druga pętla while.Grałem już w tę grę dość ciężko, ale bardzo chciałbym usłyszeć wszelkie sugestie.
Edycje:
166-> 162: Usunięto
a
ib
z programu zewnętrznego. Były niepotrzebne.162-> 155:
str()
-> ``155-> 154: Dodano
k
.154-> 152: Usunięto
x
z wnętrza funkcji, zamiast tego przekazano ją jako argument.152-> 150: Podał
a
wartość domyślną zamiast przekazać ją jako argument.150-> 146: Zmieniono inicjalizację
x
iy
.146–> 145: usunięto
k
.145-> 144: Zmieniono ... i ... lub ... na (..., ...) [...], oszczędzając w ten sposób miejsce.
144-> 138: Zmieniono (..., ...) [...] na ... + ... * (...). Dzięki @ mbomb007.
Przypadki testowe:
Przedostatni test trwał mniej niż sekundę na moim komputerze, a ostatni trwał około 5-10 sekund.
źródło
k=1
jest czysta niegodziwość.print`(a*n+p)/d`+('/'+`a`)*(a>1),
Mathematica, 163 bajty
Jest to poważnie ograniczone wymaganiem wejścia / wyjścia jako danych wejściowych i ciągów użytkownika. Radzenie sobie ze strunami jest naprawdę niewygodne w Mathematica (przynajmniej jeśli chcesz grać w golfa). Robiąc to w naturalny sposób w Mathematica (używając tylko liczb całkowitych i racjonalnych) prawdopodobnie zmniejszyłbym to do 50% wielkości.
Może wykonać 6-cyfrowe liczby w ciągu kilku sekund na moim komputerze.
Nieco bardziej czytelny (choć nie tak naprawdę niezamierzony):
Dla zabawy, robienie tego w „naturalny sposób”, tj. Jako funkcja przyjmująca licznik i mianownik i zwracająca dwie racjonalne wartości, to tylko 84 znaki (więc moje 50% oszacowanie było w rzeczywistości całkiem blisko):
źródło
Julia -
127125 bajtówPodszedłem do tego z matematycznego punktu widzenia, aby uniknąć potrzeby pętli, więc ten kod działa dość szybko dla dużych danych wejściowych (uwaga: jeśli a / b jest wejściem, to a * b musi mieścić się w Int64 (Int32 w systemach 32-bitowych) , w przeciwnym razie generowane są nonsensowne odpowiedzi - jeśli oba a i b są wyrażalne w Int32 (Int16 w systemach 32-bitowych), nie występują żadne problemy).
AKTUALIZACJA: Nie trzeba już przeciążać odwrotnego ukośnika dla div, używając ÷, oszczędzając 2 bajty netto.
Nie golfowany:
Podstawowa idea: znajdź największe d i f mniejsze niż b, które spełnia ad-bc = gcd (a, b) (następny najmniejszy) i be-af = gcd (a, b) (następny największy), a następnie oblicz c i e na podstawie tam. Wynikowe wyjście to c / de / f, chyba że albo d albo f wynosi 1, w którym to przypadku pominięto / d lub / f.
Co ciekawe, oznacza to, że kod działa również dla dodatnich niepoprawnych ułamków, o ile dane wejściowe nie są liczbami całkowitymi (to znaczy gcd (a, b) = a).
W moim systemie wprowadzanie danych
194857602/34512958303
nie zajmuje zauważalnego czasu171085289/30302433084 23772313/4210525219
źródło
55552/999999
daje mi-396/920632 486/936509
.int32(55552*999999)
daje-282630400
. Dla mnie z tym testem otrzymuję51143/920632 52025/936509
- zauważ, że mianowniki są takie same i że 52025-51143 = 486 - (- 396). Dodam notatkę, aby wspomnieć o tym problemie.1234567891234567/2145768375829475878
wyników w869253326028691/1510825213275018197 365314565205876/634943162554457681
. Ta zmiana dodaje tylko 3 dodatkowe postacie.JavaScript, 131
Z grubą notacją strzałek i
eval
połączeniami:Test
179565/987657
warunków skrajnych jest wykonywany w około 35 sekund przeglądarce Firefox , a dużo więcej w Chrome (~ 6 minut)Szybsza metoda bez
eval
oznaczenia grubej strzałyTest
179565/987657
warunków skrajnych jest wykonywany w około 5 sekund.Nie grał w golfa:
źródło
eval
. EEK2/6
daje1/3 2/5
jednak1/3
nie mniej niż, ale równe2/6
.perl, 142 bajty (155 bez CPAN)
Lub jeśli moduły CPAN są niedozwolone / potrzebny jest 3-4 razy szybszy kod:
Pierwsza wersja zajmuje 9,55 sekundy na moim komputerze, druga wersja 2,44 sekundy.
Mniej nieczytelne:
źródło