Гипер-устройство
Гипер-устройство
Гипер-устройство - это часто используемый термин в научно-фантастических рассказах. Хотя многие считают, что гипер-устройство не возможно, тем не менее существует большое количество теорий, описывающих черные дыры и гипер-устройства. Говорят, что гипер-устройство позволяет путешествовать в более высоких измерениях. В этой задаче Вас следует вычислить стоимость путешествия по большим измерениям согласно теории старого сумасшедшего друга Арифа. Я уверен, что вы знаете кто такой Ариф. Если нет, то можете спросить у своих товарищей по команде.
Пусть P и Q - две точки в n-мерном пространстве, координаты которых соответственно равны P (p1
, p2
, ..., pn
), и Q (q1
, q2
, ..., qn
). Универсальное n-мерное пространство разбито на маленькие единичные n-мерные гиперкубы. Для наглядного примера представленное ниже (5 x 4 x 3) трехмерное пространство разбито на 60 трехмерных единичных кубов (1 x 1 x 1).
Давайте обойдемся без визуализации примеров в больших размерностях. Стоимость путешествия от одной n-мерной точки P до другой n-мерной точки Q равна "количеству разных n-мерных единичных гиперкубов, которое пересекает отрезок, соединяющий эти две точки". Вам следует вычислить эту стоимость. Например, на рисунке сверху стоимость путешествия от C до E равно 10 единицам, так как отрезок EC проходит через 10 разных единичных трехмерных гиперкубов.
Входные данные
Первая строка содержит количество тестов n (n ≤ 501). Каждый тест начинается целым числом D (0 < D ≤ 10) - размерностью, в которой будет измеряться стоимость. Каждая из следующих двух строк содержит D целых чисел. D чисел первой строки задают координаты P, а D чисел второй строки задают координаты Q. Все числа не отрицательны и являются 32-битовыми знаковыми целыми.
Выходные данные
Для каждого теста вывести в одной строке стоимость путешествия из P в Q, которая является целым числом.
2 2 10 10 10 13 1 10 20
Case 1: 0 Case 2: 10
Şərh: В первом примере стоимость путешествия от (10, 10) до (10, 13) равно нулю потому что прямая, соединяющая єти точки, не пересекает ни одного единичного гиперкуба.