Вступление
Каждое рациональное число от 0 до 1 может быть представлено как конечная периодическая последовательность битов. Например, двоичное представление 11/40
0.010 0011 0011 0011 ...
где 0011
часть повторяется бесконечно. Один из способов найти это представление заключается в следующем. Начните с r = 11/40 , затем несколько раз удвойте его и возьмите дробную часть, записывая, когда она становится выше 1. Когда значение r повторяется, вы знаете, что вы вошли в цикл.
1. r = 11/40
2. 2*r = 11/20 < 1 -> next bit is 0, r = 11/20
3. 2*r = 11/10 >= 1 -> next bit is 1, r = 2*r - 1 = 1/10
4. 2*r = 1/5 < 1 -> next bit is 0, r = 1/5
5. 2*r = 2/5 < 1 -> next bit is 0, r = 2/5
6. 2*r = 4/5 < 1 -> next bit is 0, r = 4/5
7. 2*r = 8/5 >= 1 -> next bit is 1, r = 2*r - 1 = 3/5
8. 2*r = 6/5 >= 1 -> next bit is 1, r = 2*r - 1 = 1/5, same as in 4.
The loop 5. -> 6. -> 7. -> 8. now repeats.
Чтобы вернуться из двоичной строки обратно в 11/40, вы можете использовать формулу
(int(prefix) + int(suffix)/(2^len(suffix) - 1)) / 2^len(prefix)
где prefix
- начальная часть 010
, suffix
повторяющаяся часть 0011
, и int
преобразующая двоичную строку в целое число.
Имея два таких представления, мы можем выполнить над ними побитовую операцию XOR. Результирующая последовательность также будет периодической, поэтому она представляет собой рациональное число.
Для некоторых рациональных чисел существует два двоичных представления.
1/4 = 0.010000000...
= 0.001111111...
Выбор между ними может повлиять на результат побитового XOR. В этих случаях мы используем первое представление, которое имеет бесконечно много нулей.
Задание
Ваши входные данные представляют собой два рациональных числа в полуоткрытом интервале [0,1). Ваш вывод должен быть результатом побитовой операции XOR, примененной к входам, выраженной как рациональное число. Обратите внимание, что выход может быть 1, даже если ни один из входов не является.
Точные форматы ввода и вывода являются гибкими, но каждое рациональное число должно быть представлено двумя целыми числами, числителем и знаменателем (за исключением 0 и 1, которые могут быть представлены как 0
и 1
при желании). Вы можете предположить, что входные данные выражены в самых низких терминах. Выходные данные должны быть выражены в самых низких условиях. Встроенный рациональный тип чисел является приемлемым форматом, если он удовлетворяет этим ограничениям. Вы можете игнорировать любые ограничения на целые числа, наложенные вашим языком, но ваш алгоритм теоретически должен работать для всех рациональных чисел.
Побеждает самое низкое число байтов. Применяются стандартные правила игры в гольф .
пример
Рассмотрим входы 11/40 и 3/7. Мы пишем их представления друг над другом, разграничивая повторяющиеся части трубками |
. Затем мы извлекаем повторяющиеся части равной длины и применяем битовую XOR к ним и к частям перед ними.
11/40 = 0. 0 1 0|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 ...
3/7 = 0.|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|...
-> 0. 0 0 1|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 ...
Результирующее рациональное число равно 89/520.
Контрольные примеры
0 0 -> 0
1/2 1/2 -> 0
1/2 1/4 -> 3/4
1/3 2/3 -> 1
1/2 3/4 -> 1/4
5/8 1/3 -> 23/24
1/3 1/5 -> 2/5
15/16 3/19 -> 257/304
15/16 257/304 -> 3/19
3/7 11/40 -> 89/520
5/32 17/24 -> 59/96
16/29 16/39 -> 621001733121535520/696556744961512799
000...
в этих случаях (что также получается, если мы используем алгоритм сr
). Например, в случае, если5/8, 1/3
мы получаем,23/24
потому что мы выбираем расширение0.101000...
для5/8
. Если мы выберем вместо,0.10011111...
как5/8
, результат после XOR становится19/24
, так что это неправильно. Связано с Википедией: 0,999 ...(a ^ b) ^ b == a
не держится. Например(19/24 ^ 1/3) ^ 1/3 != 19/24
. Это заставило меня потерять немного волнения по этому поводу :(Ответы:
Python 3,
193164 байтаПринимает ввод как
fractions.Fraction
тип Python 3 , а также выводит его.Интересный факт (вы можете легко показать это с помощью генерирующих функций), если вы перейдете
(a<.5)^(b<.5)
к((a>=.5)and(b>=.5))
описанному выше, вы получите двоичное И между двумя рациональными числами. Назови этоnd(a, b)
. Тогда у нас естьa + b - 2*nd(a, b) = x(a, b)
!источник
JavaScript, 141 байт
Не будет работать для последнего контрольного примера (целочисленное переполнение). Введите 4 числа для
p/q xor r/s
, выведите массив с двумя числами. Для теста0, 0
, вы должны ввести0, 1, 0, 1
.Как:
(Все числа, описанные здесь, в двоичном виде.)
b
, котороеb = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s)
;x = p * b / q
,y = r * b / q
; Преобразованиеp / q
,r / s
кx / b
иy / b
;o = 10 ^ (p - q) - 1
; разделениеx
,y
чтобы[x % o, x / o]
,[y % o, y / o]
; получить xor для каждой части[x % o xor y % o, x / o xor y / o]
и присоединиться к(x % o xor y % o) + (x / o xor y / o) * o
; Пожертвуйте это какa
;a = 0
ответ0
(или0 / 1
); Иначе пустьu = gcd(a, b)
; ответ(a/u)
и(b/u)
.Показать фрагмент кода
источник