Как стать автором
Обновить

Комментарии 18

Можно было дать прямую ссылку на страницу с условиями. А то ожидаешь, что условие будет понятно из вашего текста, а оно для многих задач непонятно.
Спасибо, поправил
Есть ощущение, что формула для вычисления объема тетраэдра не работает для отрезков, из которых невозможно составить этот самый тетраэдр. То есть, применив её к такому набору отрезков, получим множество false positives.
Формально это фраза дает следствие не в ту сторону: если объем мнимый, то тетраэдра не существует. Обязательно ли он существует при действительном объеме, не сказано. Хотя контрпримера сходу найти не удалось.
Вы правы, действительный объем не является достаточным условием, надо еще требовать выполнения неравенств треугольника для граней. Пример, когда объем действительный, но тетраэдра не существует:
d12 = 32
d13 = 297
d14 = 332
d23 = 450
d24 = 48
d34 = 900
V2 = 32933194970324
Теперь понятно, почему мое решение не проходило. А я на переполнение грешил.
НЛО прилетело и опубликовало эту надпись здесь
Да я из тестов первый взял, на котором у меня неправильный ответ был.
Да, надо проверять еще неравенства треугольника для все граней. Если выполняются, то проверки объема хватит.
Спасибо за разбор. В задаче «Тетраэдр», если считать по, приведенной в первом способе, формуле, то вроде наступает переполнение даже на long long, т.к. величины порядка (10^3)^6 = 10^18 получаются.
Максимальное значение формулы в скобках — 2*10^18 < 2^61. Так что в long long умещается.
Спасибо за статьи. Обнаружил у вас опечатку.
Вместо
==
p[i] = p[i-1] + 1, если i>0 и s[0] = s[l — i — 1]
==
в описании решения задачи «Ключ» должно быть
==
p[i] = p[i-1] + 1, если i>0 и s[i] = s[l — i — 1]
==
спасибо, поправил, действительно опечатка )
Еще есть один вопрос по решению задачи D «Задачи». Там у вас в коде фигурирует двумерный массив P, одно измерение которого представляет собой уровни задач, а другое — маски тем, как я понял. В первой части программы, которая отвечает за получение/неполучение решения, есть обращение к этому массиву: P[i].length, P[i][mask]. Присутствует, например, сравнение на неравенство элемента массива значению "-1". Но нигде в коде нет установки элементов этого массива в значение, отличное от "-1" ("-1" устанавливается на этапе инициализации). Если можно, проясните, пожалуйста, назначение этого массива?
Тут не полностью исходник, конечно. Весь массив инициализируется -1 по умолчанию.

for (int[] t : P) {
			Arrays.fill(t, -1);
		}
		
		P[0][0] = -2;


И вот с (0,0) и начинается путь.
Вы не могли бы выложить куда-нибудь полный исходник, если можно? Просто здесь присваивание идет только в первый элемент массива P, а сравнение выполняется для совершенно произвольных элементов:
===
P[i][mask]
===
где i — номер текущего уровня, а mask — текушая маска уровней сложности задач.
То есть, не видно, где эти значения устанавливаются.
Поправлю и в статье, чтобы было яснее
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.