Люди добрые, помогите. Настрочил корявенький код на Java.
Эти тесты проходит.


При сдаче задачи на проверку на acmp.ru выдает ошибку на втором тесте "Wrong answer".
Может кто знает входные данные для этого теста? Не могу понять, где ошибся.

Dima T, Да, задача непростая. Но тем она и интересна. Пришлось вспомнить курс школьной алгебры. :)
Мыслей по поводу задачи куча, но как лучше впихнуть невпихуемое- хз. Были бы входные данные теста- было бы проще, сразу стало бы ясно, где недоглядел.
Но ничего, буду дальше думать.

Час от часу не легче. Алгоритм сравнения написал, второй тест прошло. Теперь не хватает времени на тест(2,15-2,20 вместо положенных 2 секунд). Бьюсь над сокращением времени. Пузырьковую сортировку заменил на быструю- результат не изменился.
На Java никто эту задачу не решил.
Тешу себя надеждой, что дело не во мне, а в Джаве )))

Время в третьем тесте победил, но теперь выдает "Wrong answer" в тесте №3.
Может кто подкинет еще данных для теста?

Или может подскажет, где поступаю неверно:
1)При чтении данных башню типа N .. y 1 z .. преобразую в N-2 .. y.

2)Нормализую верха башен N .. x y = N-1 .. z, где z=x^y, z<500.


3)Из метода сортировки передаю два массива(две башни) в метод boolean isBigger(short[] a, short[] b).
3.1) Сравниваю длину башен. Если одна из них длинней на 3 элемента, то она и больше. И наоборот. Иначе иду далее.

3.2) Добиваю меньшую башню единицами до размера больше башни.

3.3) Сравниваем башни.
3.3.1) Если этажность башен дополненных единицами равна
а)равна 0(0 x)- сравниваем башни по x.
б)равна 1(1 x y)- сравниваем по логарифму.

в)равна 2(2 x y z)- сравниваем по двойному логарифму.

г)больше либо равна 3(N .. u x y z)- считаем разность двойных логарифмов t.

г')если t>0, то башня (N .. u x y z) больше.
г'')если t<0, то башня (N .. a b c d) больше.
г''')если t=0, то сравниваем нижестоящие элементы башни. Где первым попадется больший элемент, та башня и больше.

Вот такой алгоритм. Полностью код не публикую, т.к. во-первых он сильно корявенький и в нем черт ногу сломит, а во-вторых он уже наверное близок к прохождению.

Дополню. Сразу после публикации предыдущего поста решил поиграться со значениями z из пункта 2.
При установке 10<=z<=160 третий тест проходит, но выдает "Wrong answer" в пятом тесте.

Dima T, нет, не в курсе. Просветите пожалуйста, если не сложно.
Плюс понял, почему z должен быть значительно меньше меньше 500. double хранит до 1,7е+308.
Число 10^1023 взял с конспекта переписанного с JavaRush.ru. Либо JR обманул, или я переписал не то.

Грубо говоря, должно быть так z<150

Dima T,
у меня в коде это выглядит так:


max- длина массивов дополненных единицами. Первых две позиции в массивах я выделил под грубый хэшкод(сейчас он в реализации не участвует, но лень код переписывать) и номер башни. На позициях>=3(с индексом >=2) находятся сами элементы башен. По-этому пусть Вас не смущает то, что длина массивов на 2 больше количества элементов башни.

Такой подход ошибочен?

Dima T,
Да, про мантиссу слыхал. Спасибо за подсказку. Погуглил, числа с плавающей точкой через > < = сравнивать нельзя.
Проверка должна быть вида (X-Y>эпсилон). Осталось определиться с вычислением "эпсилон" на основе X и Y.
Еще раз спасибо.

Бьюсь головой об стену.

Всё. 4 дня, 182 попытки(большая часть из них при подборе эпсилон). Теперь можно и выпить.
Переписал код, массив вместо short сделал int, нормализацию вел до 2e+9. Немного изменил метод нахождения большей из двух башен.
Dima T, боооольшущее спасибо.

Dima T, наверное не так меня поняли. Я решил ее. Трудности вызвало:

Время у меня не лучшее(хотя мог бы немного улучшить, если бы вернул идею с хэшкодом для башен одной высоты), памяти сожрал почти больше всех(можно решить изменив массив на byte, добавить в код массив с шапками башен и позицией этой шапки). Но теплит душу мысль о том, что я единственный решил задачу на Java. Мелочь, а приятно.

И да, я не школьник, не студент. Просто решил в свои 27 лет вникнуть в программирование.
Еще раз спасибо за подсказку про сравнение чисел с плавающей точкой.

Dima T, а по поводу рейтинга... Дурное это дело. Код должен быть в меру короток. Лучше будет на 20 символов больше, но переменные будут называться своими именами, а не "a", "b", "c", "x", "y", "z". Время выполнения и занимаемый объем памяти должен быть в приоритете.

Может пускай тест остается, вроде и не выдает решение задачи, но способствует пониманию некоторых нюансов.

В ближайшее время попробую немного оптимизировать код, верну массив ключей для быстрого сравнения. Думаю и время, и память немного снизятся.