ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
208 сообщений из 208, показаны все 9 страниц
  все  
Алгоритмы
    #39161529
EatsFullLemons
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
EatsFullLemons
Гость
Всем привет.
Так вышло, что я работаю тестировщиком, но хочу быть ближе к разработке (иногда такие вакансии называют dev tools, автотесты и тд). Вот недавно наш технический директор сказал, что мне нужно подтянуть основы алгоритмов, т.к. мой код не всегда самый оптимальный, благодарен ему за советы.
Суть поста: что вы могли бы посоветовать из базового курса связанного с алгоритмами? образование не айтишное(физика была), многое упустил(
мб книги какие то или просто название... предмета, которое я смог бы загуглить.
заранее спасибо
...
Рейтинг: 0 / 0
02.02.2016, 23:20
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161532
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если физик то осилишь:

Никлаус Вирт - Алгоритмы и структуры даннх
Томас Кормен - Алгоритмы: построение и анализ
Роберт Седжвик - Алгоритмы (есть на C/C++/Java ) 2х томник.

Есть еще многотомник Д.Кнута но его читать нудно. Возможно
среди вышеперечисленного будет все что надо.
...
Рейтинг: 0 / 0
02.02.2016, 23:30
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161535
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
из перечисленного выше, плюсую именно Кормена.
...
Рейтинг: 0 / 0
03.02.2016, 00:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161537
EatsFullLemons
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
EatsFullLemons
Гость
спасибо комрады. надеюсь поможет)
...
Рейтинг: 0 / 0
03.02.2016, 00:42
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161542
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Кнут, Скиена, Кормен.
Приведите пожалуйста пример неоптимального кода, о котором вы пишите выше
...
Рейтинг: 0 / 0
03.02.2016, 01:44
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161547
Lepsik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lepsik
Участник
EatsFullLemonsСуть поста: что вы могли бы посоветовать из базового курса связанного с алгоритмами? образование не айтишное(физика была),

https://www.coursera.org/course/algs4partI
...
Рейтинг: 0 / 0
03.02.2016, 01:56
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161623
Триггерман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Триггерман
Участник
EatsFullLemonsтехнический директор сказал, что мне нужно подтянуть основы алгоритмов, т.к. мой код не всегда самый оптимальныйНу да, да, конечно. А что вы такое супер-важное разрабатывать будете, что позарез нужен оптимальный код? Пишете софт для атомных реакторов? Или для управления самолётами?
Ну будет ваша программа считать 0.2 сек вместо 0.1 сек, и бухгалтерша получит отчёт на 0.1 сек позже? И что?
Там где говорят про алгоритмы и оптимизацию, там налицо явное непонимание вектора развития разработки прикладного ПО.
...
Рейтинг: 0 / 0
03.02.2016, 09:25
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161635
Станислав С...кий
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Станислав С...кий
Гость
ТриггерманТам где говорят про алгоритмы и оптимизацию, там налицо явное непонимание вектора развития разработки прикладного ПО.
А если отчет за месяц будет строиться за 20 секунд вместо 20 минут? А?
...
Рейтинг: 0 / 0
03.02.2016, 09:39
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161661
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Станислав С...кийА если отчет за месяц будет строиться за 20 секунд вместо 20 минут? А?
на сколько больше денег станет у компании разработчика?
...
Рейтинг: 0 / 0
03.02.2016, 10:06
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161666
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Для практики можешь задачки олимпиадные порешать.
...
Рейтинг: 0 / 0
03.02.2016, 10:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161683
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ИзопропилСтанислав С...кийА если отчет за месяц будет строиться за 20 секунд вместо 20 минут? А?
на сколько больше денег станет у компании разработчика?

:D
...
Рейтинг: 0 / 0
03.02.2016, 10:34
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161691
EatsFullLemons
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
EatsFullLemons
Гость
Триггерман,

авторТам где говорят про алгоритмы и оптимизацию, там налицо явное непонимание вектора развития разработки прикладного ПО.

У нас хайлоад проект в авиа индустрии. То что мои скрипты не самые оптимальные не самые эффективные это не критично для проекта, просто компания не большая и норм отношения между коллегами, считаю что мне там оч помогают развиваться.
...
Рейтинг: 0 / 0
03.02.2016, 10:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161700
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
EatsFullLemonsУ нас хайлоад проект в авиа индустрии. То что мои скрипты не самые оптимальные не самые эффективные это не критично для проекта, просто компания не большая и норм отношения между коллегами, считаю что мне там оч помогают развиваться.
Ты не шути так. А то я больше в самолёт ни ногой...

Скрипты у него ...
...
Рейтинг: 0 / 0
03.02.2016, 10:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161704
EatsFullLemons
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
EatsFullLemons
Гость
mayton,

авторА то я больше в самолёт ни ногой...

Не очкуй) если самолет и упадет, то не из-за нас.
...
Рейтинг: 0 / 0
03.02.2016, 10:54
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161706
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Жемчужины проектирования алгоритмов. Функциональный подход хорошая книга. Но без спецподготовки не прочтешь.
...
Рейтинг: 0 / 0
03.02.2016, 10:57
| Ответить | Цитировать | Написать  
Алгоритмы
    #39161707
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да чур вас! Говнокодеры. Какая-мне разница из-за чьих скриптов я упаду!

Давай сменим пластинку... Фух пойду накапаю себе капель.
...
Рейтинг: 0 / 0
03.02.2016, 10:57
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162070
Триггерман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Триггерман
Участник
EatsFullLemonsУ нас хайлоад проект в авиа индустрии
ааа, ну тогда ладно ... это другой разговор
про самолёт это я что, угадал получается?
а я думал спервоначалу, что ты продуктовый ларёк автоматизируешь.
...
Рейтинг: 0 / 0
03.02.2016, 15:08
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162378
Фотография skyANA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
skyANA
Участник
Станислав С...кийТриггерманТам где говорят про алгоритмы и оптимизацию, там налицо явное непонимание вектора развития разработки прикладного ПО.
А если отчет за месяц будет строиться за 20 секунд вместо 20 минут? А?Чтобы допетрить до того, что гораздо быстрее одним махом заполнить Range в Excel, а не по одной ячейке, Кормена читать не обязательно :)
...
Рейтинг: 0 / 0
03.02.2016, 19:38
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162381
Фотография skyANA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
skyANA
Участник
Или чтобы провести денормализацию с целью ускорения построения отчётов. Или настроить логирование, чтобы понять к какому понедельнику предрасчитать какой отчёт, чтобы пользователь его быстренько распечатал и сдал куда надо.
...
Рейтинг: 0 / 0
03.02.2016, 19:40
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162388
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИзопропилСтанислав С...кийА если отчет за месяц будет строиться за 20 секунд вместо 20 минут? А?
на сколько больше денег станет у компании разработчика?
У компании разработчика буде потенциальный отток клиентов.
Если это говнокодеры в штате, то потенциальная потеря работы.

Не сразу конечно, постепенно, накопится критическая масса жалоб юзеров на тормоза и начальство начнет решать кардинально: разогнать собственный ИТ-отдел и уйти на аутсорс, или сменить софт на менее тормозной.
...
Рейтинг: 0 / 0
03.02.2016, 19:46
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162399
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TИзопропилпропущено...

на сколько больше денег станет у компании разработчика?
У компании разработчика буде потенциальный отток клиентов.
Если это говнокодеры в штате, то потенциальная потеря работы.

Не сразу конечно, постепенно, накопится критическая масса жалоб юзеров на тормоза и начальство начнет решать кардинально: разогнать собственный ИТ-отдел и уйти на аутсорс, или сменить софт на менее тормозной.
Ситуация при которой есть 20 минут и никто ничего не может сделать - маловероятна.
Что они там? Студенты? Есть-же какой-то априорный прогноз еще до разработки.
Олап-кубы для реляционок и гибридов. Облака от Гугл или Амазон или МС для
неструктурированных запросов. Ну вобщем есть направления.
...
Рейтинг: 0 / 0
03.02.2016, 20:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162604
Триггерман
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Триггерман
Участник
Dima T,
какой-то у вас идеалистический взгляд или даже наивный.
Если наизусть не выучил все тома Кнута - так прямо сразу и разгонят.
...
Рейтинг: 0 / 0
04.02.2016, 09:03
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162722
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima TДля практики можешь задачки олимпиадные порешать.
Оффтоп!
чета я в условия этой не въеду.
...
Рейтинг: 0 / 0
04.02.2016, 11:02
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162792
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВОффтоп!
чета я в условия этой не въеду.
Не зря там "Сложность: 95%"
Вроде все понятно. Дано: набор башен
НомерСодержимое11024^(2^(2^(2^(2^2))))3...
надо отсортировать по содержимому и вывести номера.
...
Рейтинг: 0 / 0
04.02.2016, 11:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162811
Станислав С...кий
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Станислав С...кий
Гость
Dima TЕвгенийВОффтоп!
чета я в условия этой не въеду.
Не зря там "Сложность: 95%"
Вроде все понятно. Дано: набор башен
НомерСодержимое11024^(2^(2^(2^(2^2))))3...
надо отсортировать по содержимому и вывести номера.

не так, немного:
Дано: набор башен
НомерСодержимое110 - число башен24-число показателей степени; (2^(2^(2^(2^2)))) - сама башня3...
...
Рейтинг: 0 / 0
04.02.2016, 12:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162812
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

осталось написать функцию сравнения башен )
...
Рейтинг: 0 / 0
04.02.2016, 12:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162822
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Aleksandr Sharahov,
А все допер.
Не учел это -"В первой строке входного файла INPUT.TXT задается число башен N ". Считал 10=0. Невнимательность.
...
Рейтинг: 0 / 0
04.02.2016, 12:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162830
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Станислав С...кийне так, немного:
точно, это студенческая классика: "введите кол-во наборов", "введите размер набора 1", "введите элемент 1 набора 1" и т.д.
...
Рейтинг: 0 / 0
04.02.2016, 12:20
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163006
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги. Я для удобства перепишу этот тесткейс. Добавлю номера строк в Given для удобства.
 

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
When:

10
1)4 2 2 2 2 2
2)1 2 2
3)1 3 2
4)1 2 3
5)3 2 2 2 2
6)2 2 2 2
7)1 3 3
8)3 3 3 3 3
9)2 4 3 3
10)2 2 3 4

Then:

2 4 3 6 7 5 9 10 1 8



В уже отсортированном виде. Сверху-вниз от меньших к большим.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1 2 2
1 2 3
1 3 2
2 2 (2 2)
1 3 (3)
3 2 2 2 2
2 4 3 3
2 2 3 4
4 2 2 2 2 2
3 3 3 3 3



Несколько мыслей.
1) Возвозить степень в степень - рискованно с точки зрения типов данных. Можно не влезть ни в какой
тип а даже если заюзать символьную арифметику - непродуктивно и долго. Ведь задача стоит не вычислить
а сравнить. Поэтому предлагаю до последнего не заниматься поиском лонг-арифметики ... ну или
в крайнем случае только для само-проверки или теста гипотезы. Вообще сама постановка почему-то
напомнила Числа Грэма.

2) Строки номер (1) и (2). Лексикографически отсортированны это плюс. По крайней мере тривиальные случаи
сравнения работают.

3) Между сроками (3) и (4) разница не-лексикографическая.

4) Надо поискать красивую изящную (возможно рекуррентную формулу) для сравнения
...
Рейтинг: 0 / 0
04.02.2016, 14:49
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163030
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Может логарифмы прикрутить? Если не путаю
Код: sql
1.
log(a^b) = log(a) * b
...
Рейтинг: 0 / 0
04.02.2016, 15:02
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163033
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм. Если



Тогда я наверное могу переписать табличку так. И осилить почему (9) и (10) строки стоят именно так.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1 2 2 1 1 1
1 2 3 1 1 1
1 3 2 1 1 1
2 2 2 2 1 1
1 3 3 1 1 1
3 2 2 2 2 1
2 4 3 3 1 1
2 2 3 4 1 1
4 2 2 2 2 2
3 3 3 3 3 1
...
Рейтинг: 0 / 0
04.02.2016, 15:04
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163037
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TМожет логарифмы прикрутить? Если не путаю
Код: sql
1.
log(a^b) = log(a) * b


А это мысль. Можно привязаться к монотонности. Тоесть если

A > B

и оба числа очень большие то

ln(A) > ln(B)

также будет справедливо. А сама функция может даст нам возможность чё-нить сократить.
...
Рейтинг: 0 / 0
04.02.2016, 15:06
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163057
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще там подвохи могут быть, типа
Код: sql
1.
3 2 1 2 2


что равно
Код: sql
1.
3 2 1 1 1
...
Рейтинг: 0 / 0
04.02.2016, 15:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163112
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нашел теорему. Возможно будет полезна.

Если a > 1, то неравенство
равносильно неравенству того же смысла: f(x) > g(x). Если 0 < a < 1, то показательное
неравенство равносильно неравенству
противоположного смысла: f(x) < g(x).

В нашем случае основание a либо равно 1 - тогда степени равны (башни одинаковы по рангу)
либо больше единицы (т.к. из условия задачи у нас только целые).
...
Рейтинг: 0 / 0
04.02.2016, 16:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163153
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
думаю, стоит попробовать приводить к виду e^e^e^e^e^e^e^e^e^x
...
Рейтинг: 0 / 0
04.02.2016, 16:27
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163160
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, но как?
...
Рейтинг: 0 / 0
04.02.2016, 16:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163206
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

справа налево, каждый раз переходя к новому основанию e.

возможно, идеальным был бы вид x^x^x^x^x^x^x^x^x, но неясно как его получить.
...
Рейтинг: 0 / 0
04.02.2016, 17:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163268
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
если есть n, k>=1, то
n^(k+1)>(n+1)^k
может отсюда как?
...
Рейтинг: 0 / 0
04.02.2016, 18:29
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163348
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonAleksandr Sharahov, но как?
mayton, ты тут кладезь алгоритмов. Напиши, порви студентов. Правда там оценка по количеству букав кода, но время тоже показывается.
...
Рейтинг: 0 / 0
04.02.2016, 20:26
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да какой кладезь? Болото скорее.

Вот если-б Сашик заскочил. Может чё и придумал а у меня кроме логарифмирования идей нет.
...
Рейтинг: 0 / 0
04.02.2016, 21:27
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163514
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
С большой долей вероятности, тут присутствует некое нечёткое сравнение. Быстрая сортировка даёт O(nlnn). Теперь нужно понять сколько времени будет выполняться одна операция сравнения, быстрое возведение в степень + некоторый формат хранения больших чисел, должен дать O(lnn) на одну операцию сравнения, таким образом имеем O(n(lnn)^2). Но всё это нужно очень аккуратно реализовать.

Кроме того, я сильно сомневаюсь в том что существует корректное решение данной задачи, т.к. нечёткое сравнение будет давать погрешность на высоких башнях, значения которых отличаются незначительно. Таким образом,1 вопрос должен быть такой: а можно ли за обозримое время сравнить две девятиэтажных, например, башни ?
...
Рейтинг: 0 / 0
05.02.2016, 09:12
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163516
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
И если процедуру сравнения нельзя провести однозначно, то эта задача неинтересна
...
Рейтинг: 0 / 0
05.02.2016, 09:13
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163524
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
С итоговой оценкой напутал, будет так O(nlgnlga), где n количество чисел, a- максимальное значение коэффициента в башне, что тоже константа, таким образом мы имеем O(nlgn), но на самом деле константа которая находится перед функцией nlgn должна быть скорее всего не меньше 1000
...
Рейтинг: 0 / 0
05.02.2016, 09:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163703
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury, подобного рода задачи (конкурсные, олимпиадные) обычно таят в себе
хинт или подсказку которая позволяет их решить в доступное время (1.5 - 2 часа).
...
Рейтинг: 0 / 0
05.02.2016, 11:42
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163993
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если числа A и B, такие что

Код: sql
1.
2.
A=a1^(a2^a3)....a9
B=b1^(b2^b3)....b9


и все основания и показатели больше либо равны 1 то
я предположил что в данном неравенстве

Код: sql
1.
A < B



можно логарифмировать обе части без потери смысла.



(Поскольку в Latex трудно работать с рядами я взял первые 3 цифры для удобства демонстрации)

получаем произведение с меньшей степенью



еще раз повторил логарифмирование. Раскрыл логарифм произведения.



Степень выражения понизилась но осталась сумма. Как дальше быть - не знаю.
В полном варианте условий у меня еще семь операций.
...
Рейтинг: 0 / 0
05.02.2016, 14:36
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164048
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Есть подозрение что ln(ln(A)) можно просто выкинуть при следующем логарифмировании как незначительную величину.
Как доказать не знаю, думаю как-то исходя из того что ln(ln(99)) < 1
...
Рейтинг: 0 / 0
05.02.2016, 15:08
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164052
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Любая короткая башня легко дополняется единицами до любого требуемого размера.
Потом разворачивается.
Вместо логарифма можно использовать извлечение корня.
В результате получается матрица, которую можно посчитать СЛАУ и стукнуть, например, методом Гаусса.
А вот дальше меня заклинило и критерий сортировки я не смог найти.
...
Рейтинг: 0 / 0
05.02.2016, 15:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164199
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonСтепень выражения понизилась но осталась сумма. Как дальше быть - не знаю.


Продолжать )

Нумеровать и вычислять удобнее справа налево:
x=a8^a7^a6^a5^a4^a3^a2^a1^a0;
b0=a0, b1=a1^b0, b2=a2^b1... b8=a8^b7.
Пытаемся свести к вычислению 8-ми вложенных логарифмов
всей башни log(log(log(log(log(log(log(log(x)))))))):
y1=log b1, y2=loglog b2, y3=logloglog b3...
Логарифм суммы вычисляется через произведение
log(u+v)=log(u*(v/u))=loglog u + log(v/u).
Идея в том, чтобы, повторяя это, свести вычисления к предыдущему y
(первое слагаемое) и добавки (второе). Оба небольшие.
...
Рейтинг: 0 / 0
05.02.2016, 16:22
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164212
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovЛогарифм суммы вычисляется через произведение
log(u+v)=log(u*(v/u))=loglog u + log(v/u).
Код: sql
1.
u+v = u*(v/u) = v


?
...
Рейтинг: 0 / 0
05.02.2016, 16:31
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164227
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovЛогарифм суммы вычисляется через произведение
log(u+v)=log(u*(v/u))=loglog u + log(v/u).
Код: sql
1.
u+v = u*(v/u) = v


?

Конечно, опечатка
u+v=u*(1+v/u)
log(u+v)=log(u*(1+v/u))=loglog u + log(1+v/u)
...
Рейтинг: 0 / 0
05.02.2016, 16:39
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164286
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не совсем хорошо. Выражение U степень понижает но в выражении V степень переходит
в знаменатель в одном из слагаемых ну вобщем дальше комплексность растёт
и я рискую просто допускать ошибки и опечатки.
...
Рейтинг: 0 / 0
05.02.2016, 17:19
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164366
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

да, там в знаменателе башня с предыдущим значением сверху
...
Рейтинг: 0 / 0
05.02.2016, 18:20
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164377
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
А вообще конечно довольно странная задача.
У меня совсем нет уверенности, что из-за округлений не совпадут значения для разных башен.
...
Рейтинг: 0 / 0
05.02.2016, 18:27
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164417
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahovmayton,

да, там в знаменателе башня с предыдущим значением сверху
Проделайте пожалуйста шаги с разложением логарифма суммы.
Я признаю что не силён в подобных преобразованиях. Навыка мало.
...
Рейтинг: 0 / 0
05.02.2016, 18:58
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164580
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonAleksandr Sharahovmayton,

да, там в знаменателе башня с предыдущим значением сверху
Проделайте пожалуйста шаги с разложением логарифма суммы.
Я признаю что не силён в подобных преобразованиях. Навыка мало.

 
как-то так, если нигде опять не ошибся )
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
     b0  = a0

     b1  = a1^b0
 log(b1) = b0*log(a1)

     b2  = a2^b1
 log(b2) = b1*log(a2)
log2(b2) = log(b1) + log2(a2)

     b3  = a3^b2
 log(b3) = b2*log(a3)
log2(b3) = log(b2) + log2(a3)
log3(b3) = log(log(b2) + log2(a3)) = log2(b2) + c12, c12 = log(1+log2(a3)/log(b2))

     b4  = a4^b3
 log(b4) = b3*log(a4)
log2(b4) = log(b3) + log2(a4)
log3(b4) = log(log(b3) + log2(a4)) = log2(b3) + c13, c13 = log(1+log2(a4)/log(b3))
log4(b4) = log(log2(b3) + c13)     = log3(b3) + c23, c23 = log(1+    c13/log2(b3))

     b5  = a5^b4
 log(b5) = b4*log(a5)
log2(b5) = log(b4) + log2(a5)
log3(b5) = log(log(b4) + log2(a5)) = log2(b4) + c14, c14 = log(1+log2(a5)/log(b4))
log4(b5) = log(log2(b4) + c14)     = log3(b4) + c24, c24 = log(1+    c14/log2(b4))
log5(b5) = log(log3(b4) + c24)     = log4(b4) + c34, c34 = log(1+    c24/log3(b4))

     b6  = a6^b5
 log(b6) = b5*log(a6)
log2(b6) = log(b5) + log2(a6)
log3(b6) = log(log(b5) + log2(a6)) = log2(b5) + c15, c15 = log(1+log2(a6)/log(b5))
log4(b6) = log(log2(b5) + c15)     = log3(b5) + c25, c25 = log(1+    c15/log2(b5))
log5(b6) = log(log3(b5) + c25)     = log4(b5) + c35, c35 = log(1+    c25/log3(b5))
log6(b6) = log(log4(b5) + c35)     = log5(b5) + c45, c45 = log(1+    c35/log4(b5))

     b7  = a7^b6
 log(b7) = b6*log(a7)
log2(b7) = log(b6) + log2(a7)
log3(b7) = log(log(b6) + log2(a7)) = log2(b6) + c16, c16 = log(1+log2(a7)/log(b6))
log4(b7) = log(log2(b6) + c16)     = log3(b6) + c26, c26 = log(1+    c16/log2(b6))
log5(b7) = log(log3(b6) + c26)     = log4(b6) + c36, c36 = log(1+    c26/log3(b6))
log6(b7) = log(log4(b6) + c36)     = log5(b6) + c46, c46 = log(1+    c36/log4(b6))
log7(b7) = log(log5(b6) + c46)     = log6(b6) + c56, c56 = log(1+    c46/log5(b6))

     b8  = a8^b7
 log(b8) = b7*log(a8)
log2(b8) = log(b7) + log2(a8)
log3(b8) = log(log(b7) + log2(a8)) = log2(b7) + c17, c17 = log(1+log2(a8)/log(b7))
log4(b8) = log(log2(b7) + c17)     = log3(b7) + c27, c27 = log(1+    c17/log2(b7))
log5(b8) = log(log3(b7) + c27)     = log4(b7) + c37, c37 = log(1+    c27/log3(b7))
log6(b8) = log(log4(b7) + c37)     = log5(b7) + c47, c47 = log(1+    c37/log4(b7))
log7(b8) = log(log5(b7) + c47)     = log6(b7) + c57, c57 = log(1+    c47/log5(b7))
log8(b8) = log(log6(b7) + c57)     = log7(b7) + c67, c67 = log(1+    c57/log6(b7))

нумерация справа налево, все логарифмы по основанию 2, log2(n)=log(log(n)), log3(n)=log(log2(n)) и т.д.

...
Рейтинг: 0 / 0
05.02.2016, 23:32
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164807
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я придумал алгоритм сравнения:
2^(2^(2^2)) = 65536 что больше максимального 99, поэтому сравнивать надо только три последних уровня башни.

Т.е. берем высоту большей башни, добиваем меньшую единицами и сравниваем верхушки.

Например:
башня1 a^(b^(c^(d^e)))
башня2 f^(g^(h^i))
сравнить надо только c^(d^e) и h^(i^1)
...
Рейтинг: 0 / 0
06.02.2016, 17:51
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164819
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЯ придумал алгоритм сравнения:
2^(2^(2^2)) = 65536 что больше максимального 99, поэтому сравнивать надо только три последних уровня башни.

Т.е. берем высоту большей башни, добиваем меньшую единицами и сравниваем верхушки.

Например:
башня1 a^(b^(c^(d^e)))
башня2 f^(g^(h^i))
сравнить надо только c^(d^e) и h^(i^1)

Конечно, нижние уровни башни имеют гораздо меньший вес по сравнению с верхними,
но трех верхних уровней мало для верного сравнения, например:

99^98^2^2 > 2^99^2^2
...
Рейтинг: 0 / 0
06.02.2016, 18:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164825
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TЯ придумал алгоритм сравнения:
2^(2^(2^2)) = 65536 что больше максимального 99, поэтому сравнивать надо только три последних уровня башни.
Ты что-то напутал в условии. Нам дано (максимум) 50 тысяч башен.
Каждая из которых может иметь высоту от 1 уровня до 10 уровней
максимум: 99^(99^(99^(99^(99^(99^(99^(99^(99^99))))))))
...
Рейтинг: 0 / 0
06.02.2016, 19:10
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164826
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahovнапример:

99^98^2^2 > 2^99^2^2
Хорошо. А если 4 уровня?

Я к тому чтобы не искать логарифм суммы. 4 уровня можно так обсчитать
Код: sql
1.
(ln(ln(a1)) + ln(a2) * a3) ^ a4


но пятый уже не полезет в double
...
Рейтинг: 0 / 0
06.02.2016, 19:13
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164829
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мне почему-то эта задача напоминает расчёты пределов или сходимости рядов.
Тоесть я хочу сказать что наша задача - не делать расчёт а эквивалентно преобразовать
две башни (две формулы) и оценить которая из них больше. Типа взять предел
соотношения. Там... или еще как-то.

А для оценки сойдет даже логарифм с его погрешностями. Думаю что это допустимо,
особенно когда речь идет не просто о больших а об астрономически-больших числах.
...
Рейтинг: 0 / 0
06.02.2016, 19:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164830
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

для 4х уровней надо сравнить числа:
99^99^99^99^99^98^2^2^2
и 2^2^2^2^2^99^2^2^2
...
Рейтинг: 0 / 0
06.02.2016, 19:28
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164836
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
да, похоже 4х достаточно, если откидывать сверху одинаковые (после уравнивания высот)
...
Рейтинг: 0 / 0
06.02.2016, 19:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164842
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov, опечатка:

да, похоже 4х достаточно, если НЕ откидывать сверху одинаковые (после уравнивания высот)
...
Рейтинг: 0 / 0
06.02.2016, 20:04
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164875
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Не взлетела идея с 4-мя последними. Ошибка на второй проверке.

 
Заслал туда код
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Test {
	public class Tower {
		public int num;
		public List<int> val = new List<int>();

		public double Head(int level) {
			if (level >= val.Count) return -1;
			double ret = Math.Log(Math.Log((double)val[level]));
			if (level + 3 < val.Count) {
				ret = ret + Math.Log(val[level + 1]) * Math.Pow(val[level + 2], val[level + 3]);
			}
			else if (level + 3 == val.Count) {
				ret = ret + Math.Log(val[level + 1]) * val[level + 2];
			}
			else if (level + 2 == val.Count) {
				ret = ret + Math.Log(val[level + 1]);
			}
			return ret;
		}

		public void Print() {
			Console.Write(num.ToString() + ": {");
			for (int i = 0; i < val.Count; i++) {
				if (i != 0) Console.Write(",");
				Console.Write(val[i]);
			}
			Console.WriteLine("}");
		}
	}

	public class TowerComparer : IComparer<Tower> {
		public int Compare(Tower t1, Tower t2) {
			int level = ((t1.val.Count > t2.val.Count) ? t1.val.Count : t2.val.Count) - 4;
			if (level < 0) level = 0;
			var h1 = t1.Head(level);
			var h2 = t2.Head(level);
			if(h1 > h2) {
				return 1;
			} else if(h1 < h2) {
				return -1;
			} else {
				return 0;
			}
		}
	}

	class Program {
		static void Main(string[] args) {
			var sr = new StreamReader("input.txt");
			int cnt = Int32.Parse(sr.ReadLine());
			var towers = new Tower[cnt];
			for(int i = 0; i < cnt; i++) {
				towers[i] = new Tower();
				towers[i].num = i + 1;
				var v = sr.ReadLine().Split(' ');
				for(int j = 0; j <= Int32.Parse(v[0]); j++) {
					int x = Int32.Parse(v[j+1]);
					if(x == 1) break;
					towers[i].val.Add(x);
				}
			}
			foreach(var t in towers) t.Print();
			Console.WriteLine("После сортировки");
			var tc = new TowerComparer();
			var sw = new StreamWriter("output.txt");
			foreach(var t in towers.OrderBy((s => s), tc)) {
				t.Print();
				sw.Write(t.num + " ");
			}
			sw.WriteLine("");
			sw.Close();
		}
	}
}


...
Рейтинг: 0 / 0
06.02.2016, 21:22
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164878
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TНе взлетела идея с 4-мя последними. Ошибка на второй проверке.


странно, а что не так сравнилось, известно?

Я тут набросал сравнение из интереса,
получилось довольно монструозно,
но отсылать не буду, чтобы не расстраиваться )

 
функция сравнения степенных башен
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
type
  TPowerTower= array of integer;

function ComparePowerTowers(a1, a2: TPowerTower): integer;
const
  epsilon= 1.0e-9;
var
  t1, t2: TPowerTower;
  i, j, len1, len2: integer;
  x1, x2: extended;
begin;
  len1:=Length(a1);
  len2:=Length(a2);
  if len1 or len2=0 then begin;
    Result:=0;
    exit;
    end;
  t1:=Copy(a1, 0, len1);
  t2:=Copy(a2, 0, len2);
  if len1<len2 then begin;
    SetLength(t1, len2);
    for i:=len1 to len2-1 do t1[i]:=1;
    len1:=len2;
    end;
  if len2<len1 then begin;
    SetLength(t2, len1);
    for i:=len2 to len1-1 do t2[i]:=1;
    len2:=len1;
    end;
  for i:=0 to len1-1 do if t1[i]<=1 then begin;
    for j:=i to len1-1 do t1[j]:=1;
    break;
    end;
  for i:=0 to len2-1 do if t2[i]<=1 then begin;
    for j:=i to len2-1 do t2[j]:=1;
    break;
    end;
  if (t1[0]=1) or (t2[0]=1) then begin;
    Result:=t1[0]-t2[0];
    exit;
    end;
  repeat;
    dec(len1);
    until (len1=0) or (t1[len1]<>t2[len1]);
  if len2-len1>=4 then len2:=len1+4
  else begin;
    len1:=len2-4;
    if len1<0 then len1:=0;
    end;
  if len1+4=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * exp(ln(t1[len1+2])*t1[len1+3]);
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * exp(ln(t2[len1+2])*t2[len1+3]);
    end
  else if len1+3=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * t1[len1+2];
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * t2[len1+2];
    end
  else if len1+2=len2 then begin;
    x1:=ln(t1[len1]) * t1[len1+1];
    x2:=ln(t2[len1]) * t2[len1+1];
    end
  else begin;
    x1:=t1[len1];
    x2:=t2[len1];
    end;
  if abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon then begin;
    if x1<x2 then Result:=-1 else Result:=1;
    exit;
    end;
  for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;
  Result:=0;
  end;

...
Рейтинг: 0 / 0
06.02.2016, 21:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164881
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahovстранно, а что не так сравнилось, известно?
не пишут.
Aleksandr SharahovЯ тут набросал сравнение из интереса,
получилось довольно монструозно,
но отсылать не буду, чтобы не расстраиваться )
...
Рейтинг: 0 / 0
06.02.2016, 21:58
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164889
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А есть пример INPUT/OUTPUT который подтвердит
что эти "рукописи" компилируются, работают и выдают
корректный резалт?

Просто не у всех тут есть компиллятор... Так ште...
...
Рейтинг: 0 / 0
06.02.2016, 22:20
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164893
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TНе взлетела идея с 4-мя последними. Ошибка на второй проверке.
Заслал туда код

Похоже не взлетела из-за того, что у тебя в коде нет понижения левела, когда верхние одинаковы.
Надо понижать до тех пор, пока среди 4х последних пар не будет найдена пара разных.
...
Рейтинг: 0 / 0
06.02.2016, 22:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164901
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonА есть пример INPUT/OUTPUT который подтвердит
что эти "рукописи" компилируются, работают и выдают
корректный резалт?

Просто не у всех тут есть компиллятор... Так ште...

 
Вот примеры выхода функции сравнения:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
a1 = 3 2 2 2 2 2 2 2 2
a2 = 2 2 2 2 2 2 2 2 2
Result = 1

a1 = 2 98 2 2 2 2 2 2 2
a2 = 2 99 2 2 2 2 2 2 2
Result = -1

a1 = 2 99 2 2 2 2 2 2 2
a2 = 2 99 2 2 2 2 2 4 1
Result = 0

a1 = 2 99 2 2 2 2 2 3 3
a2 = 2 99 2 2 2 2 2 27 1
Result = 0

a1 = 2 99 2 2 2 65536 1 1 1
a2 = 2 99 2 2 2 2 2 2 2
Result = 0

a1 = 99 99 98 2 2 2 2 2 2
a2 = 2 2 99 2 2 2 2 2 2
Result = -1

a1 = 2 2 3 2 2 2 2 2 2
a2 = 99 99 2 2 2 2 2 2 2
Result = 1



Могу прогнать любые предложенные варианты.
...
Рейтинг: 0 / 0
06.02.2016, 22:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164910
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovDima TНе взлетела идея с 4-мя последними. Ошибка на второй проверке.
Заслал туда код

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

Нет, это я погорячился, с понижением уровня, надо понижать только если верхние - единицы.
Возможно, ты попался в эту ловушку с хвостами из 4х единиц.
 
немного упростил свой код с учетом этого
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
function ComparePowerTowers(const a1, a2: TPowerTower): integer;
const
  epsilon= 1.0e-9;
var
  t1, t2: TPowerTower;
  i, len1, len2: integer;
  x1, x2: extended;
begin;
  len1:=Length(a1);
  len2:=Length(a2);
  for i:=0 to len1-1 do if a1[i]<=1 then begin;
    len1:=i;
    break;
    end;
  for i:=0 to len2-1 do if a2[i]<=1 then begin;
    len2:=i;
    break;
    end;
  if len1 or len2=0 then begin;
    Result:=0;
    exit;
    end;
  t1:=Copy(a1, 0, len1);
  t2:=Copy(a2, 0, len2);
  if len1<len2 then begin;
    SetLength(t1, len2);
    for i:=len1 to len2-1 do t1[i]:=1;
    len1:=len2;
    end;
  if len2<len1 then begin;
    SetLength(t2, len1);
    for i:=len2 to len1-1 do t2[i]:=1;
    len2:=len1;
    end;
  if (t1[0]=1) or (t2[0]=1) then begin;
    Result:=t1[0]-t2[0];
    exit;
    end;
  len1:=len2-4;
  if len1<0 then len1:=0;
  if len1+4=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * exp(ln(t1[len1+2])*t1[len1+3]);
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * exp(ln(t2[len1+2])*t2[len1+3]);
    end
  else if len1+3=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * t1[len1+2];
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * t2[len1+2];
    end
  else if len1+2=len2 then begin;
    x1:=ln(t1[len1]) * t1[len1+1];
    x2:=ln(t2[len1]) * t2[len1+1];
    end
  else begin;
    x1:=t1[len1];
    x2:=t2[len1];
    end;
  if abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon then begin;
    if x1<x2 then Result:=-1 else Result:=1;
    exit;
    end;
  for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;
  Result:=0;
  end;


 
добавил соответствующий тест
Код: pascal
1.
2.
3.
a1 = 2 3 1 1 1 1 1 1 1
a2 = 99 2 1 1 1 1 1 1 1
Result = -1

...
Рейтинг: 0 / 0
06.02.2016, 23:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164911
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr SharahovМогу прогнать любые предложенные варианты.
Давай краевые кейсы.
Код: sql
1.
2.
3.
4.
5.
6.
7.
a1 = 1 1 1 1 1 1 1 1 1 1
a2 = 99 99 99 99 99 99 99 99 99 99
Expected Result = 1

a1 = 99 99 99 99 99 99 99 99 99 99
a2 = 1 1 1 1 1 1 1 1 1 1
Expected Result = -1



И тест на точность

Код: sql
1.
2.
3.
a1 = 99 98 99 99 99 99 99 99 99 99
a2 = 98 99 99 99 99 99 99 99 99 99
Expected Result = 1
...
Рейтинг: 0 / 0
06.02.2016, 23:29
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164919
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

у меня ожидаемый результат противоположнный, я из первого параметра вычитаю второй:
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
a1 = 3 2 2 2 2 2 2 2 2
a2 = 2 2 2 2 2 2 2 2 2
Result = 1 Expected = 1

a1 = 2 98 2 2 2 2 2 2 2
a2 = 2 99 2 2 2 2 2 2 2
Result = -1 Expected = -1

a1 = 2 99 2 2 2 2 2 2 2
a2 = 2 99 2 2 2 2 2 4 1
Result = 0 Expected = 0

a1 = 2 99 2 2 2 2 2 3 3
a2 = 2 99 2 2 2 2 2 27 1
Result = 0 Expected = 0

a1 = 2 99 2 2 2 65536 1 1 1
a2 = 2 99 2 2 2 2 2 2 2
Result = 0 Expected = 0

a1 = 99 99 98 2 2 2 2 2 2
a2 = 2 2 99 2 2 2 2 2 2
Result = -1 Expected = -1

a1 = 2 2 3 2 2 2 2 2 2
a2 = 99 99 2 2 2 2 2 2 2
Result = 1 Expected = 1

a1 = 2 3 1 1 1 1 1 1 1
a2 = 99 2 1 1 1 1 1 1 1
Result = -1 Expected = -1

a1 = 2 3 1 1 1 1 1 1 1
a2 = 99 2 1 1 1 1 1 1 1
Result = -1 Expected = -1

a1 = 1 1 1 1 1 1 1 1 1 1
a2 = 99 99 99 99 99 99 99 99 99 99
Result = -98 Expected = -1

a1 = 99 99 99 99 99 99 99 99 99 99
a2 = 1 1 1 1 1 1 1 1 1 1
Result = 98 Expected = 1

a1 = 99 98 99 99 99 99 99 99 99 99
a2 = 98 99 99 99 99 99 99 99 99 99
Result = -1 Expected = -1

...
Рейтинг: 0 / 0
06.02.2016, 23:59
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164922
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, что такое TPowerTower?
...
Рейтинг: 0 / 0
07.02.2016, 00:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164923
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonAleksandr Sharahov, что такое TPowerTower?

это массив целых чисел:
Код: pascal
1.
2.
type
  TPowerTower= array of integer;



забыл скопипастить во второй исходник, в первом оно было.
...
Рейтинг: 0 / 0
07.02.2016, 00:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164942
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
а я тоже не поняла условие: например
УсловиеИзвестно, что среди башен во входном файле нет равных.

и далее даются башни файла

1 2 2 -> 1^2^2 = 1
1 3 2 -> 1^3^2 = 1
1 2 3 -> 1^2^3 =1
1 3 3 -> 1^3^3 = 1

что я неправильно делаю?
...
Рейтинг: 0 / 0
07.02.2016, 01:47
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164945
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mini.weblabа я тоже не поняла условие: например
УсловиеИзвестно, что среди башен во входном файле нет равных.

и далее даются башни файла

1 2 2 -> 1^2^2 = 1
1 3 2 -> 1^3^2 = 1
1 2 3 -> 1^2^3 =1
1 3 3 -> 1^3^3 = 1

что я неправильно делаю?

Возможно, имелось в виду, что нет двух башен, запись которых во входном потоке в виде строки совпадает?
...
Рейтинг: 0 / 0
07.02.2016, 02:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164949
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

терзают смутные сомнения, что и 4х уровней мало, завтра поэкспериментирую
...
Рейтинг: 0 / 0
07.02.2016, 02:44
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164956
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mini.weblabа я тоже не поняла условие: например
УсловиеИзвестно, что среди башен во входном файле нет равных.

и далее даются башни файла

1 2 2 -> 1^2^2 = 1
1 3 2 -> 1^3^2 = 1
1 2 3 -> 1^2^3 =1
1 3 3 -> 1^3^3 = 1

что я неправильно делаю?
первая цифра - количество степеней, или кол-во элементов в башне + 1, т.е.
1 2 2 -> 2^2
2 3 3 3 -> 3^3^3
...
Рейтинг: 0 / 0
07.02.2016, 07:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164992
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovDima T,

терзают смутные сомнения, что и 4х уровней мало, завтра поэкспериментирую

предчувствия его не обманули:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
a1 = 99 40 3 1 1
a2 = 2 2 16 1 1
Result = 1 Expected = 1

a1 = 99 40 3 1 1
a2 = 2 2 2 4 1
Result = 1 Expected = 1

a1 = 99 40 3 1 1
a2 = 2 2 2 2 2
ERROR!!!           Result = -1 Expected = 1
...
Рейтинг: 0 / 0
07.02.2016, 11:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164995
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я вчера написал что 4 не помогло 18782630

Надо как-то 5-й добавить. Может понятно станет как 6й и т.д.

Похоже логарифмы тут не в тему. Надо какую-то другую зависимость искать.
...
Рейтинг: 0 / 0
07.02.2016, 11:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164997
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЯ вчера написал что 4 не помогло 18782630

Надо как-то 5-й добавить. Может понятно станет как 6й и т.д.

Похоже логарифмы тут не в тему. Надо какую-то другую зависимость искать.

Я видел это. Надо хвост из единиц отсекать, а то и 6, и 7 не поможет ))

Выше я привел нормальный пример без единичного хвоста, когда не работает.
...
Рейтинг: 0 / 0
07.02.2016, 11:53
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165004
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Отсекал я хвосты. У меня меньшая добивается единицами до высоты большей. Дальше последние 4 от каждой.

Надо как-то к общему основанию или степени привести, чтобы эти правила заработали
Код: sql
1.
2.
3.
если a > b то
a^n > b^n 
n^a > n^b


только как?
...
Рейтинг: 0 / 0
07.02.2016, 12:18
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165010
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TОтсекал я хвосты. У меня меньшая добивается единицами до высоты большей. Дальше последние 4 от каждой.

Я о другом. В исходных данных могут подсунуть башни с длинными единичными хвостами.

Dima TНадо как-то к общему основанию или степени привести, чтобы эти правила заработали только как?

Проще подшаманить с последней парой элементов.
Если они в результате дают меньше 300,
то гарантированно переполнения не будет,
и можно сократить высоту.
 
типа такого
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
function ComparePowerTowers(const a1, a2: TPowerTower): integer;
const
  epsilon= 1.0e-9;
const
  MaxBaseForPower: array[2..8] of integer= (17,6,4,3,2,2,2);
var
  t1, t2: TPowerTower;
  i, len1, len2, pow: integer;
  x1, x2: extended;
begin;
  len1:=Length(a1);
  len2:=Length(a2);
  for i:=0 to len1-1 do if a1[i]<=1 then begin;
    len1:=i;
    break;
    end;
  for i:=0 to len2-1 do if a2[i]<=1 then begin;
    len2:=i;
    break;
    end;
  if len1 or len2=0 then begin;
    Result:=0;
    exit;
    end;
  t1:=Copy(a1, 0, len1);
  t2:=Copy(a2, 0, len2);
  if len1<len2 then begin;
    SetLength(t1, len2);
    for i:=len1 to len2-1 do t1[i]:=1;
    len1:=len2;
    end;
  if len2<len1 then begin;
    SetLength(t2, len1);
    for i:=len2 to len1-1 do t2[i]:=1;
    len2:=len1;
    end;
  if (t1[0]=1) or (t2[0]=1) then begin;
    Result:=t1[0]-t2[0];
    exit;
    end;
  if (len2>1)
  and (t1[len2-1]<=High(MaxBaseForPower)) and (t1[len2-2]<=MaxBaseForPower[t1[len2-1]])
  and (t2[len2-1]<=High(MaxBaseForPower)) and (t2[len2-2]<=MaxBaseForPower[t2[len2-1]])
  then begin;
    pow:=t1[len2-2]; for i:=2 to t1[len2-1] do pow:=pow*t1[len2-2]; t1[len2-2]:=pow;
    pow:=t2[len2-2]; for i:=2 to t2[len2-1] do pow:=pow*t2[len2-2]; t2[len2-2]:=pow;
    dec(len2);
    end;
  len1:=len2-4;
  if len1<0 then len1:=0;
  if len1+4=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * exp(ln(t1[len1+2])*t1[len1+3]);
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * exp(ln(t2[len1+2])*t2[len1+3]);
    end
  else if len1+3=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * t1[len1+2];
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * t2[len1+2];
    end
  else if len1+2=len2 then begin;
    x1:=ln(t1[len1]) * t1[len1+1];
    x2:=ln(t2[len1]) * t2[len1+1];
    end
  else begin;
    x1:=t1[len1];
    x2:=t2[len1];
    end;
  if abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon then begin;
    if x1<x2 then Result:=-1 else Result:=1;
    exit;
    end;
  for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;
  Result:=0;
  end;

...
Рейтинг: 0 / 0
07.02.2016, 12:39
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165025
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

эксперименты показывают, что 300 - сильно заниженная оценка,
переполнения не происходит даже при 2470,
т.е. при вычислении 99^99^99^2470
...
Рейтинг: 0 / 0
07.02.2016, 13:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165032
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
 
добавил склейку верхних этажей, пока результат меньше 2470
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
function ComparePowerTowers(const a1, a2: TPowerTower): integer;
const
  epsilon= 1.0e-9;
const
  //MaxBaseForPower: array[2..8] of integer= (17,6,4,3,2,2,2);       //MaxBaseForPower[i]^i<300
  MaxBaseForPower: array[2..11] of integer= (49,13,7,4,3,3,2,2,2,2); //MaxBaseForPower[i]^i<2470
var
  t1, t2: TPowerTower;
  i, len1, len2, pow: integer;
  x1, x2: extended;
begin;
  len1:=Length(a1);
  len2:=Length(a2);
  for i:=0 to len1-1 do if a1[i]<=1 then begin;
    len1:=i;
    break;
    end;
  for i:=0 to len2-1 do if a2[i]<=1 then begin;
    len2:=i;
    break;
    end;
  if len1 or len2=0 then begin;
    Result:=0;
    exit;
    end;
  t1:=Copy(a1, 0, len1);
  t2:=Copy(a2, 0, len2);
  if len1<len2 then begin;
    SetLength(t1, len2);
    for i:=len1 to len2-1 do t1[i]:=1;
    len1:=len2;
    end;
  if len2<len1 then begin;
    SetLength(t2, len1);
    for i:=len2 to len1-1 do t2[i]:=1;
    len2:=len1;
    end;
  if (t1[0]=1) or (t2[0]=1) then begin;
    Result:=t1[0]-t2[0];
    exit;
    end;
  while (len2>1)
    and (t1[len2-1]<=High(MaxBaseForPower)) and (t1[len2-2]<=MaxBaseForPower[t1[len2-1]])
    and (t2[len2-1]<=High(MaxBaseForPower)) and (t2[len2-2]<=MaxBaseForPower[t2[len2-1]])
    do begin;
    pow:=t1[len2-2]; for i:=2 to t1[len2-1] do pow:=pow*t1[len2-2]; t1[len2-2]:=pow;
    pow:=t2[len2-2]; for i:=2 to t2[len2-1] do pow:=pow*t2[len2-2]; t2[len2-2]:=pow;
    dec(len2);
    end;
  len1:=len2-4;
  if len1<0 then len1:=0;
  if len1+4=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * exp(ln(t1[len1+2])*t1[len1+3]);
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * exp(ln(t2[len1+2])*t2[len1+3]);
    end
  else if len1+3=len2 then begin;
    x1:=ln(ln(t1[len1])) + ln(t1[len1+1]) * t1[len1+2];
    x2:=ln(ln(t2[len1])) + ln(t2[len1+1]) * t2[len1+2];
    end
  else if len1+2=len2 then begin;
    x1:=ln(t1[len1]) * t1[len1+1];
    x2:=ln(t2[len1]) * t2[len1+1];
    end
  else begin;
    x1:=t1[len1];
    x2:=t2[len1];
    end;
  if abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon then begin;
    if x1<x2 then Result:=-1 else Result:=1;
    exit;
    end;
  for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;
  Result:=0;
  end;

...
Рейтинг: 0 / 0
07.02.2016, 13:39
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165036
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovЯ о другом. В исходных данных могут подсунуть башни с длинными единичными хвостами.
Эти тоже отсекал.

Aleksandr Sharahovэксперименты показывают, что 300 - сильно заниженная оценка,
переполнения не происходит даже при 2470,
т.е. при вычислении 99^99^99^2470
Скорее всего ты переполнение не заметил.
99^99 = 3,7 * 10^197
99^(10^197) ~ 10^(2 * 10^197) тут уже никаких стандартных типов не хватит.

Стандартный double (который в процессоре реализован) имеет предел 10^308.
...
Рейтинг: 0 / 0
07.02.2016, 13:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165041
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TСкорее всего ты переполнение не заметил.


Разумеется, я не вычислял башню непосредственно,
а вычислял двойной логарифм,
как это сделано и в твоем, и в моем исходниках.

Кроме того, я использую тип extended, а не double.
...
Рейтинг: 0 / 0
07.02.2016, 14:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165044
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Например, вот такой тест проходит сравнение 18783990

Код: pascal
1.
2.
3.
a1 = 99 98 99 99 99 99 99 99 99 2470
a2 = 98 99 99 99 99 99 99 99 99 2470
Result = -1 Expected = -1
...
Рейтинг: 0 / 0
07.02.2016, 14:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165115
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
оффтоп:

решил погуглить "сравнение числовых башен". прямого ответа не нашел, зато набрел на статью
http://lpgenerator.ru/blog/2014/12/10/zanimatelnaya-statistika-chast-vtoraya-gigantskaya/
в нем степенные башни с одинаковыми числами определяются как "тетрации".
Дочитал до места:
автор Операция пятого уровня — Пентация (^^^)

Пентация — это повторяющаяся тетрация, объединяет последовательности с двумя стрелками в одну операцию.
Гипероператор каждого последующего уровня сокращает последовательность предыдущего уровня, используя термин b для обозначения длины последовательности. Например:

пентация

Умножение сокращает последовательность сложения.
Возведение сокращает последовательность умножения.
Тетрация сокращает последовательность возведения в степень.

В каждом случае a — число в основании, b — длина последовательности.
Но что же сокращает пентация? Принцип работы этого гипероператора можно описать как «безумное поглощение степенных башен».

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

Вычисляем результат первой степенной башни и подставляем его вместо значения высоты (количества уровней) для следующей башни. Затем вычисляем и ее результат и подставляем его в количество уровней следующей степенной башни. И так далее. Каждая последующая башня «поглощает» результат предыдущей, используя её результат для собственного «безумного» роста... и голова начала болеть :)

во всяком случае, оставляю это здесь, вдруг кому пригодится :)
...
Рейтинг: 0 / 0
07.02.2016, 18:56
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165193
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Выше я уже описал возможно единственный способ решения данной задачи. Но способ неинтересный. Ибо ключевой вопрос такой: Можно ли сравнить 2 башни наверняка(даже если разница между ними 1-2 значения) ? Если нельзя, а скорее всего нельзя, то можно ли отсортировать множество башен не сравнивая их друг с другом ? При этом в данном конкретном случае bucket sort не подойдёт

Код ниже может быть решение, а может и нет (не разбирал). Сегодня совсем нет времени, да и задача мне пока не нравится.

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
{$O-,Q+,R+}
uses SysUtils, Math;

const MaxK=9;
      inf=1e239;
      inf2=1e100;
      eps=1e-6;
      MaxN=50000;
      MaxA=99;

procedure readr (var x:integer; a, b:integer);
begin
  assert (not seekeoln); read (x); assert ((a<=x) and (x<=b));
end;

procedure readl;
begin
  assert (eoln); assert (not eof); readln
end;

type ip=record
       l, o:integer;
       x:extended;
     end;
     tow=array [0..MaxK] of integer;


         
function pseudoeval (s, k:integer; const t:tow):extended;
var i:integer;
begin
  assert (s<=k);
  Result:=t[k];
  for i:=k-1 downto s do begin
    if t[i]=1 then Result:=1 else
    if Result>1000 then Result:=inf else begin
      assert (Result=round (Result));
      Result:=IntPower (t[i], round (Result));
      if Result>inf then Result:=inf;
    end;
  end;
end;


procedure convert (k:integer; const t:tow; var r:ip);
begin
  r.l:=0; r.x:=pseudoeval (0, k, t);
  while r.x>=inf2 do begin
    inc (r.l); r.x:=pseudoeval (r.l, k, t)*ln (t[r.l-1]);
  end;
end;

function myln (x:extended):extended;
begin
  if x<=eps then myln:=-inf else myln:=ln (x);
end;


function less (var a, b:ip):boolean;
var l1, l2:extended;
    i:integer;
begin
  if a.o=b.o then begin Result:=false; exit end;
  l1:=a.x; l2:=b.x;
  for i:=a.l+1 to b.l do l1:=myln (l1);
  for i:=b.l+1 to a.l do l2:=myln (l2);
  assert (abs (l1-l2)>eps);
  less:=l1<l2;
end;

var A:array [1..MaxN] of ip;


procedure qsort (l, r:integer);
var i, j:integer;
    x, y:ip;
begin
  if l>=r then exit;
  i:=l; j:=r; x:=A[(l+r) shr 1];
  repeat
    while less (A[i], x) do inc (i);
    while less (x, A[j]) do dec (j);
    if i<=j then begin
      y:=A[i]; A[i]:=A[j]; A[j]:=y;
      inc (i); dec (j)
    end
  until i>j;
  qsort (l, j);
  qsort (i, r);
end;



var tmp:tow;
    i, j, K, N:integer;


begin
  reset (input, 'towers.in');
  rewrite (output, 'towers.out');
  readr (N, 1, MaxN); readl;
  for i:=1 to N do begin
    readr (K, 1, 9);
    for j:=0 to K do readr (tmp[j], 1, MaxA);
    convert (k, tmp, A[i]);
    A[i].o:=i;
    readl;
  end;
  assert (eof);
  qsort (1, N);

  for i:=1 to N-1 do
    assert (less (A[i], A[i+1]) and not less (A[i+1], A[i]));

  for i:=1 to N do write (A[i].o, ' ');
end.

...
Рейтинг: 0 / 0
08.02.2016, 01:54
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165194
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Интересно. Это задача на тему "Сортировки и последовательности" возможно я был не прав в части логарифмов и экспонент.
...
Рейтинг: 0 / 0
08.02.2016, 02:06
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165200
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonИнтересно. Это задача на тему "Сортировки и последовательности" возможно я был не прав в части логарифмов и экспонент.
Одно не исключает другое. Задача звучит так: "есть набор последовательностей (башен) и надо их отсортировать". Осталась мелочь: придумать алгоритм сравнения двух башен.
...
Рейтинг: 0 / 0
08.02.2016, 07:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165206
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryВыше я уже описал возможно единственный способ решения данной задачи. Но способ неинтересный.
Не нашел. Тут 18775760 мельком какое-то нечеткое сравнение упомянул, а дальше про сложность алгоритма.

SashaMercury Ибо ключевой вопрос такой: Можно ли сравнить 2 башни наверняка(даже если разница между ними 1-2 значения) ? Если нельзя, а скорее всего нельзя, то можно ли отсортировать множество башен не сравнивая их друг с другом ?
Нельзя отсортировать если невозможно сравнить. Раз есть правильные решения - задача решаема.

SashaMercuryКод ниже может быть решение, а может и нет (не разбирал). Сегодня совсем нет времени, да и задача мне пока не нравится.
Много букав на непонятном паскале, магические числа (1e239, 1e100) и ни одного камента.

Ты бы лучше словами описал свой алгоритм сравнения двух башен.
...
Рейтинг: 0 / 0
08.02.2016, 07:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165217
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Использование bucket sort позволит провести сортировку не сравнивая элементы исходного множества друг с другом. Однако, в данном конкретном случае, такая сортировка не подойдёт. Может быть существует другой вариант по сортировке без сравнения элементов непосредственно друг с другом ?

Алгоритм такой:
Использовать быстрое возведение в степень, и свой формат хранения больших чисел. Но данный алгоритм не позволит сравнить две башни, разница между которыми очень маленькая. Тут аналогичная ситуация как с диапазоном long double, и покрытием множества действительных чисел. Асимптотика алгоритма O(nlgn), коэффициент перед функцией будет порядка 10^3
...
Рейтинг: 0 / 0
08.02.2016, 07:49
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165239
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryИспользование bucket sort позволит провести сортировку не сравнивая элементы исходного множества друг с другом. Однако, в данном конкретном случае, такая сортировка не подойдёт. Может быть существует другой вариант по сортировке без сравнения элементов непосредственно друг с другом ?
Не знаю почему ты решил что bucket sort не требует сравнения. Там элементы не сравниваются меж собой на первом шаге, но сравнивается элемент с границами корзины. На втором шаге каждая корзина сортируется обычной сортировкой, т.е. со сравнением элементов. ИМХУ это просто специфичный вид сортировки для очень больших последовательностей: сначала разбиваем на куски, которые гарантированно поместятся в памяти, затем сортируем каждый кусок.

SashaMercuryАлгоритм такой:
Использовать быстрое возведение в степень, и свой формат хранения больших чисел. Но данный алгоритм не позволит сравнить две башни, разница между которыми очень маленькая. Тут аналогичная ситуация как с диапазоном long double, и покрытием множества действительных чисел. Асимптотика алгоритма O(nlgn), коэффициент перед функцией будет порядка 10^3
Думаю тут достаточно порядок результата прикинуть с точностью до первых 10-15 десятичных разрядов. Но и порядок хранить проблематично:
99^99 = 3,7 * 10^197
99^(10^197) ~ 10^(2 * 10^197)
...
Рейтинг: 0 / 0
08.02.2016, 09:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165312
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Если правильно вижу, то решение 18785435 отличается от 18783990 следующим:

1) хранит башню в виде:
- количество уровней до шапки
- шапка
(а не только шапку)

2) вычисляет шапку,
2а) склеивая верхние уровни в один до тех пор, пока ее величина остается меньше 1000 (а не 2470)
2б) логарифмируя полученное значение и умножая его на значение предыдущего уровня,
чтобы учесть в шапке на 1 уровень больше (а не на 3 уровня)

3) для всех неучтенных уровней хранит их количество

4) для сравнения башен сравниваются их шапки,
однако, если уровни башен до шапок не совпадают,
то перед сравнением шапка меньшей логарифмируется
столько раз, какова разность уровней.
...
Рейтинг: 0 / 0
08.02.2016, 10:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165317
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
не совсем понимаю, как оно заметит разницу между
99 99 99 99 99 99 99 99 99 и
98 99 99 99 99 99 99 99 99
...
Рейтинг: 0 / 0
08.02.2016, 11:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165323
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Идея с логарифмированием на разность уровней очень хороша, можно своровать ))
И для большей строгости использовать правильное основание, а не просто e.
...
Рейтинг: 0 / 0
08.02.2016, 11:05
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165335
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, логарифм по правильному основанию всё равно
расчитывается через натуральные. Строгость мы получаем только
в суждениях но в численном методе остаётся тоже что и было.
...
Рейтинг: 0 / 0
08.02.2016, 11:12
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165345
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

я это типа знаю,
но почему бы не учесть множитель, если он сам идет в руки ))
...
Рейтинг: 0 / 0
08.02.2016, 11:16
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165351
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
РЕСДЭновцы тоже не решили .
...
Рейтинг: 0 / 0
08.02.2016, 11:22
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165352
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

а, понял о чем ты.

Здесь ситуация другая.
Если грубо, у него ошибка, которая слабо влияет на результат.
Он логарифмирует только одну сторону сравнения.
Надо логарифмировать по основанию, которое возводилось в степень с другой стороны
...
Рейтинг: 0 / 0
08.02.2016, 11:22
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165356
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Бррр. Не понял. С одной стороны... с другой. А можно формулой как-то?
...
Рейтинг: 0 / 0
08.02.2016, 11:26
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165357
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ЕвгенийВРЕСДЭновцы тоже не решили .

Почему тоже?
У нас уже есть почти решение (сравнение).
Но его можно еще улучшить, с учетом последних данных )
...
Рейтинг: 0 / 0
08.02.2016, 11:26
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165375
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonБррр. Не понял. С одной стороны... с другой. А можно формулой как-то?

Ну вот у него есть башни (Count1, Head1) и (Count2, Head2).
Пусть, для определенности Count2=Count1+1.
Он сравнивает башни как Ln(Head1) и Head2,
потому что он не хранит информацию о предыдущих уровнях башен.
Правильно было бы использовать логарифм по основанию,
равному уровню перед шапкой в башне 2.
...
Рейтинг: 0 / 0
08.02.2016, 11:36
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165548
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovmaytonБррр. Не понял. С одной стороны... с другой. А можно формулой как-то?

Ну вот у него есть башни (Count1, Head1) и (Count2, Head2).
Пусть, для определенности Count2=Count1+1.
Он сравнивает башни как Ln(Head1) и Head2,
потому что он не хранит информацию о предыдущих уровнях башен.
Правильно было бы использовать логарифм по основанию,
равному уровню перед шапкой в башне 2.

На самом деле не совсем так.
В качестве шапки у него уже хранится логарифм верхней башенки: Head1=Ln(Top1).
И, значит, верхняя башенка равна Top1=Exp(Head1).
После приведения башен к равной высоте получим новый Top1'=Log(a,Top1)=Log(a,Exp(Head1)).
Для сравнения нужен новый Head1'=Ln(Top1')=Ln(Log(a,Exp(Head1)))=Ln(Head1/Ln(a)).
...
Рейтинг: 0 / 0
08.02.2016, 14:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165577
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
А разве можно вычислить например
ln(ln(ln(ln(99))))
...
Рейтинг: 0 / 0
08.02.2016, 14:35
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165598
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ЕвгенийВА разве можно вычислить например
ln(ln(ln(ln(99))))

Вычисления логарифма нужны не сами по себе, а для сравнения башен.
Когда башни маленькие, сравниваем их непосредственно.
Когда башни большие, сравниваем их логарифмы.
Если при этом окажется, что у одной из них логарифм не существует, то она меньше.
...
Рейтинг: 0 / 0
08.02.2016, 14:43
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165603
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ЕвгенийВА разве можно вычислить например
ln(ln(ln(ln(99))))
А где у нас была такая формула?
...
Рейтинг: 0 / 0
08.02.2016, 14:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165636
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
maytonЕвгенийВА разве можно вычислить например
ln(ln(ln(ln(99))))
А где у нас была такая формула?
18777841
...
Рейтинг: 0 / 0
08.02.2016, 15:04
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165640
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ЕвгенийВmaytonпропущено...

А где у нас была такая формула?
18777841
Ну нет там такого. Смотри внимательнее. Под логарифмом - сумма. В последнем преобразовании.
Дальше просто не было преобразований.

Будь осторожнее с такими аналогиями. Конешно область определения уходит в минус.
Но твоя формула не равна моей.
...
Рейтинг: 0 / 0
08.02.2016, 15:06
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165791
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Есть идея.

Результат можно рассмотреть как
Код: sql
1.
f(a1, f(a2, f(a3, f(a4, f5))))


Для расчета конкретного значения f() это pow(), но для сравнения можно поискать функцию с такими же характеристиками, т.е. чтобы при
Код: sql
1.
pow(a, b) > pow(c, d)

всегда выполнялось
Код: sql
1.
f(a, b) > f(c, d)


Дополнительно можно ограничить что основание (а и с) всегда в диапазоне 2...99

Правда тут проблема что из-за вложенности погрешность большая может накопиться.
...
Рейтинг: 0 / 0
08.02.2016, 17:31
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165798
Cane Cat Fisher
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cane Cat Fisher
Участник
Станислав С...кийА если отчет за месяц будет строиться за 20 секунд вместо 20 минут? А?

Зато тот, что за 20 минут - правильный :)
...
Рейтинг: 0 / 0
08.02.2016, 17:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165809
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Aleksandr Sharahovдумаю, стоит попробовать приводить к виду e^e^e^e^e^e^e^e^e^xдумаю, очень хорошая идея. сравнение чисел можно производить по количеству "e", если оно разное, и по "x", если количесто одинаковое.


Aleksandr Sharahovсправа налево, каждый раз переходя к новому основанию e.
а почему не напрямую?

можно расписать это step-by-step.
введем обозначение:
пусть A 1.k = a 1 ^a 2 ^a 3 ...a k , A 2.k = a 2 ^a 3 ...a k , A k.k = a k .

согласно
A = e ln(A) , получается, что многократно логарифмуя, на каждом шагу получаем .. распишем пошагово:
первый шаг: ln( A 1.k ) = A 2.k * ln( a 1 )
второй шаг: ln(ln( A 1.k )) = ln(A 2.k * ln( a 1 )) = ln(A 2.k ) + ln(ln( a 1 )) =
A 3.k * ln( a 2 ) + ln(ln( a 1 ))
Так, здесь у нас появляется сумма, и уже нельзя так удобно логарифмовать с переносом остатка башни вниз в виде множителя. Однако, если мы перепишем верхнее выражение как
A 3.k * [ ln( a 2 ) + ln(ln( a 1 )) / A 3.k ] то есть вынесем за скобки башню (3.к), то вроде бы видно что членом с a 1 можно пренебречь, он будет практически нулем. и тогда
третий шаг: ln(ln(ln( A 1.k ))) =
A 4.k * ln( a 3 ) + ln(ln( a 2 ))
и аналогично четвертый шаг
ln(ln(ln(ln( A 1.k )))) =
A 5.k * ln( a 4 ) + ln(ln( a 3 ))
ну и вроде появляется алгоритм "факторизации" башни, то есть приведения ее в вид e^e^e^e^e^e^e^e^e^x

то есть что-то такое:
1. Просматриваем башню, и если где-то какой-то a i = 1, отбрасываем его и всю часть правее.
2. Делаем 'к' шагов (столько, сколько членов башни задано с учетом п.1)
3. Вычисляем x на последнем шагу.
4. Если оно большое (x>e), логарифмируем, столько раз, сколько надо, чтобы получилось 0 < x < e, при этом добавляя к нашему 'k' дополнительные шаги.
5. Теперь у нас есть оценка величины башни - это два числа - количество шагов и x.

ну пусть кто-нибудь проверит, не ошибся ли я:)
...
Рейтинг: 0 / 0
08.02.2016, 17:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165854
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
S.G.A 3.k * [ ln( a 2 ) + ln(ln( a 1 )) / A 3.k ] то есть вынесем за скобки башню (3.к), то вроде бы видно что членом с a 1 можно пренебречь
Нельзя им пренебречь. В этом и засада. Заходили немного с другой стороны 18782181 (не сработало), и также споткнулись на "вроде можно пренебречь".
...
Рейтинг: 0 / 0
08.02.2016, 18:28
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165870
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В продолжение 18789098
если взять
Код: sql
1.
f(a,b) = Log2(a^b)


тогда все отлично работает на башнях одинаковой высоты. Тестю в экселе. Но на разных не работает, т.к. Log2(1^1) = 0.
Логарифм по основанию 2 (минимально возможное) именно потому чтобы всегда было в результате >=1.
В общем мне эта идея кажется заманчивой, но надо ее допилить для сравнения башен разной высоты.
...
Рейтинг: 0 / 0
08.02.2016, 18:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165969
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
S.G., я имел в виду следующее:

Любая башня однозначно представима в виде:
e^e^...n раз...e^x, где 0<=x<1
Поэтому достаточно хранить и сравнивать только эти два числа.
Проблема в том, чтобы организовать циклический пересчет этих чисел сверху вниз.
Возможно, удобнее будет использовать основание 2 вместо e.

Я эту идею пока не бросаю, оставил на подумать при наличии времени.
Есть мысль, как ее развить, но пока занят.
...
Рейтинг: 0 / 0
08.02.2016, 20:26
| Ответить | Цитировать | Написать  
Алгоритмы
    #39165992
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Aleksandr SharahovS.G., я имел в виду следующее:

Любая башня однозначно представима в виде:
e^e^...n раз...e^x, где 0<=x<1
Поэтому достаточно хранить и сравнивать только эти два числа.
Проблема в том, чтобы организовать циклический пересчет этих чисел сверху вниз.
да, я понял.
(только условие для x должно быть 0 < x < e , как мне кажется)
просто попытался сделать это снизу вверх. (или слева направо).
На одном из шагов есть отбрасывание (как мне кажется незначительного) члена, но Dima T утверждает что его нельзя отбросить.
Мне сейчас немного сложновато сделать рабочий код для проверки (увы, основная работа мешает :) ) но через несколько дней я попробую.
...
Рейтинг: 0 / 0
08.02.2016, 20:58
| Ответить | Цитировать | Написать  
Алгоритмы
    #39166280
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не помню рассматривали такой подход или нет. Можно попробовать брать частное
двух башен и строить компаратор на основании этого свойства.
...
Рейтинг: 0 / 0
09.02.2016, 10:29
| Ответить | Цитировать | Написать  
Алгоритмы
    #39166558
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

все тоже самое в итоге получается.
...
Рейтинг: 0 / 0
09.02.2016, 13:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167000
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще одна мысль появилась про "отбросить незначительное", т.е. тут



выкинуть ln(ln(a 1 )) ln(ln(b 1 )) и получить



т.е. обсчитать только верх башни. Наигравшись в экселе с 4-5 этажными башнями из малых чисел вроде как вижу что должно работать, но надо то что выкинули все равно учесть, т.к.
{99,99,3,4,5} > {99,98,3,4,5}
а формула это игнорирует. Поэтому сделал просто: при совпадении шапок опускаюсь ниже и сравниваю значения одного уровня, если не совпали, то больше там где значение больше, т.е. в данном примере 99 > 98 поэтому считаю что башня больше. Но похоже неправильное сравнение. Заслал на тест, останавливается на 5-й проверке.

Дополнительно нормализовал башни. Сделал тип double и понижаю верхушку пока результат возведения в степень <10 50

Надо либо проверку нижних усовершенствовать при совпадении верхов, либо идея "отбросить незначительное" не подходит, т.е. отбрасывается что-то значительное.
...
Рейтинг: 0 / 0
09.02.2016, 18:16
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167065
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Есть сомнения что при любых A, B, C всегда выполняется условие
{2, 2, 2, 2, 2, 2, 99, A, B, C} > {99, 99, 99, 99, 99, 99, 98, A, B, C}

как проверить - не знаю.
...
Рейтинг: 0 / 0
09.02.2016, 19:26
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167096
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЕсть сомнения что при любых A, B, C всегда выполняется условие
{2, 2, 2, 2, 2, 2, 99, A, B, C} > {99, 99, 99, 99, 99, 99, 98, A, B, C}

как проверить - не знаю.

проверить, что в самом тяжелом случае (A=B=C=2)
99^A^B^C / 98^A^B^C > 7
...
Рейтинг: 0 / 0
09.02.2016, 20:19
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167102
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima TЕсть сомнения что при любых A, B, C всегда выполняется условие
{2, 2, 2, 2, 2, 2, 99, A, B, C} > {99, 99, 99, 99, 99, 99, 98, A, B, C}

как проверить - не знаю.

проверить, что в самом тяжелом случае (A=B=C=2)
99^A^B^C / 98^A^B^C > 7
Тут калькулятора достаточно:
99^16 / 98^16 = 8.514577711e31 / 7.237977206e31 = 1.176375314

Откуда магическое число 7?
...
Рейтинг: 0 / 0
09.02.2016, 20:29
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167106
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

логарифм по основанию 2 наибольшего значения этажа к наименьшему
...
Рейтинг: 0 / 0
09.02.2016, 20:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167112
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
log 2 (2 7 ) = 7
...
Рейтинг: 0 / 0
09.02.2016, 20:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167115
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima T,

логарифм по основанию 2 наибольшего значения этажа к наименьшему
log 2 (10) = 1,008600172
Это меньше, но откуда родилось данное утверждение?
...
Рейтинг: 0 / 0
09.02.2016, 20:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167118
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Логарифм по основанию 2 отношения наибольшего значения этажа к наименьшему берется отсюда.
Пусть b1=7 * b2
Тогда 2^b1 = 2^(7*b2) = (2^7)^b2 = 128^b2 > 99^b2,
2^2^b1 = 2^128^b2 > 99^99^b2, т.к. даже при b2=2 имеем 2^128^2 = 2^16k = (2^16)^1024 > 99^1000
ну и т.д.
...
Рейтинг: 0 / 0
09.02.2016, 20:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167124
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
7 это log(2,99) с некоторым запасом.
Можно доказать, что чем больше значения сравниваемых шапок, тем меньший запас нужен.
Т.е. как отношение шапок за 7 перевалило, так уже точно башня с большей шапкой больше.
...
Рейтинг: 0 / 0
09.02.2016, 21:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167202
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov2^2^b1 = 2^128^b2 > 99^99^b2, т.к. даже при b2=2 имеем 2^128^2 = 2^16k = (2^16)^1024 > 99^1000


тут неточность

2^2^b1 = 2^128^b2 > 99^99^b2, т.к. даже при b2=2^2^2 имеем 2^128^16 > 99^99^16 и снова (128/99)^16 > 7
и т.д.
...
Рейтинг: 0 / 0
10.02.2016, 01:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167210
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Берите натуральный. У него больше возможностей к преобразованиям.
...
Рейтинг: 0 / 0
10.02.2016, 01:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167426
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
А как вычисляют, что например
2^2^65536~10^10^21840?

Взято отсюда .
...
Рейтинг: 0 / 0
10.02.2016, 11:55
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167487
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ЕвгенийВА как вычисляют, что например
2^2^65536~10^10^21840?

Взято отсюда .

lglg(2^2^65536) = lg(2^65536*lg2) = 65536*lg2+lglg2 ~ 19728
значит 2^2^65536 ~ 10^10^19728
...
Рейтинг: 0 / 0
10.02.2016, 12:42
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167587
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Aleksandr Sharahovзначит 2^2^65536 ~ 10^10^19728
Значит там ошибка?
19728, а не 21840?
...
Рейтинг: 0 / 0
10.02.2016, 13:51
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167610
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
maytonНу нет там такого. Смотри внимательнее. Под логарифмом - сумма. В последнем преобразовании.
Дальше просто не было преобразований.

Будь осторожнее с такими аналогиями. Конешно область определения уходит в минус.
Но твоя формула не равна моей.
В моём первом варианте преобразований надо уйти от неопределённостей.
Например сдвинуть логарифму на 1 влево (или прибавить +1 к аргументу под логарифмом)

http://yotx.ru/#!1/3_h/ubWwf7Wwf7Rgzhf23/aP9g/2DfT0qt7RPgG3vQrd39g30SDbuxc8p4PN1iPG5dXuzub@0DBg==
...
Рейтинг: 0 / 0
10.02.2016, 14:13
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167614
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Четыре преобразования и всё ОК. Без выхода в отрицательную область определения.

y = ln(ln(ln(ln(x+1)+1)+1)+1)
...
Рейтинг: 0 / 0
10.02.2016, 14:16
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167639
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ЕвгенийВAleksandr Sharahovзначит 2^2^65536 ~ 10^10^19728
Значит там ошибка?
19728, а не 21840?

Человеку свойствинно ошебаться ))
...
Рейтинг: 0 / 0
10.02.2016, 14:37
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168792
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я решил

 
Описание алгоритма
1. Нормализовать верхи башень, т.е. считать верхи пока считаются, например 2^(2^(2^(2^2))) привести к 2^65536
2. Сравнивать три верхних уровня: ln(ln(a 3 )) + ln(a 4 ) * a 5 и ln(ln(b 3 )) + ln(b 4 ) * b 5
3. Если верхи совпали - сравнивать нижние сверху вниз: a 2 и b 2 если равны a 1 и b 1
...
Рейтинг: 0 / 0
11.02.2016, 16:55
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168808
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima T,
Сравни по своему алгоритму
99, 99, 78, 98, 99, 90, 99, 99
25, 34, 99, 75, 2, 99, 99, 92, 99
...
Рейтинг: 0 / 0
11.02.2016, 17:07
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168815
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЯ решил

 
Описание алгоритма
1. Нормализовать верхи башень, т.е. считать верхи пока считаются, например 2^(2^(2^(2^2))) привести к 2^65536
2. Сравнивать три верхних уровня: ln(ln(a 3 )) + ln(a 4 ) * a 5 и ln(ln(b 3 )) + ln(b 4 ) * b 5
3. Если верхи совпали - сравнивать нижние сверху вниз: a 2 и b 2 если равны a 1 и b 1


B 18783990 тот же самый алгоритм сравнения )
...
Рейтинг: 0 / 0
11.02.2016, 17:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168828
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
99, 99, 78, 98, 99, 90, 99, 99 < 25, 34, 99, 75, 2, 99, 99, 92, 99

Если кому сравнить - пишите, посчитаю, только запросы оформляйте в формате тестов
Код: sql
1.
2.
3.
2
7 99 99 78 98 99 90 99 99
8 25 34 99 75 2 99 99 92 99


Ответ
Код: sql
1.
1 2
...
Рейтинг: 0 / 0
11.02.2016, 17:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168838
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima T,
9 99
27 66
...
Рейтинг: 0 / 0
11.02.2016, 17:31
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168845
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
Алгоритм сравнения сразу правильный придумали 18772992 18773013 18777841

Но одного алгоритма сравнения мне не хватило. Думаю он не срабатывает из-за погрешностей логарифмирования на каких-то башнях с очень близкими значениями.
...
Рейтинг: 0 / 0
11.02.2016, 17:38
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168849
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima T,
9 99
27 66
они равны, что противоречит условию задачи.
...
Рейтинг: 0 / 0
11.02.2016, 17:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168855
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
ты тут перемудрил
Код: sql
1.
abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon


затестил ради интереса - не проходит мой код с такой проверкой.
у меня проще
Код: sql
1.
abs(x1-x2)>epsilon
...
Рейтинг: 0 / 0
11.02.2016, 17:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168859
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
Алгоритм сравнения сразу правильный придумали 18772992 18773013 18777841

Но одного алгоритма сравнения мне не хватило. Думаю он не срабатывает из-за погрешностей логарифмирования на каких-то башнях с очень близкими значениями.

Да, это понятно.

Но вся суть алгоритма в том, чтобы различать почти одинаковые башни (k<7),
при этом отбраковывая одинаковые.

Дело в том, что таких башен конечное число, и, похоже, что после склейки верхних уровней
не существует таких башен высотой более 4 (если считать склеенные уровни за 1).
Т.е. главная фишка алгоритма - именно склейка верхних уровней.
...
Рейтинг: 0 / 0
11.02.2016, 17:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168866
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima TЕвгенийВDima T,
9 99
27 66
они равны, что противоречит условию задачи.
нет равных разве не подразумевает например 2 3 2 и 2 3 2?
...
Рейтинг: 0 / 0
11.02.2016, 17:58
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168878
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima Tпропущено...

они равны, что противоречит условию задачи.
нет равных разве не подразумевает например 2 3 2 и 2 3 2?
Думаю что нет. Мой код на
Код: sql
1.
2.
9 99
27 66

и на
Код: sql
1.
2.
27 66 
9 99


дает ответ
Код: sql
1.
1 2


но ответ
Код: sql
1.
2 1


тоже правильный, что вызывает неопреденность.
...
Рейтинг: 0 / 0
11.02.2016, 18:04
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168926
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovДело в том, что таких башен конечное число, и, похоже, что после склейки верхних уровней
не существует таких башен высотой более 4 (если считать склеенные уровни за 1).
Т.е. главная фишка алгоритма - именно склейка верхних уровней.
c 10 до 4 не склеить даже если там одни двойки. 2^2^2^2 = 65536 а дальше не склеить.

Но т.к. по условию задачи исходные уровни не более 99, т.е. максимум склеиваются три верхних в один, например 2^2^2 = 16
Как следствие функция проверки должна работать без склеивания. А если она не работает, то значит должна существовать такая пара пятиуровневых башень A(a1^a2^a3^a4^a5) и B(b1^b2^b3^b4^b5) удовлетворяющих условию A<B при
a3^a4^a5>b3^b4^b5 или (a3^a4^a5=b3^b4^b5 и a2>b2) или (a3^a4^a5=b3^b4^b5 и a2=b2 и a1>b1)

Ломаю голову как найти такую комбинацию, т.е. доказать что без склейки никак не решить. Перебор тут на годы может растянуться.
...
Рейтинг: 0 / 0
11.02.2016, 18:43
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168940
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ЕвгенийВDima TДля практики можешь задачки олимпиадные порешать.
Оффтоп!
чета я в условия этой не въеду.
Редиска ты, Евгений.

Ты отсортировал задачи по сложности в выдал нам самую топовую из всех 700
http://acmp.ru/index.asp?main=tasks&str= &page=13&id_type=0

Ну неужели не мог найти чё-нить поприятнее ну йо-майо.
...
Рейтинг: 0 / 0
11.02.2016, 18:58
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168946
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Нашел пару, нерешаемую без склеивания уровней: 64^2^2^2 > 2^3^2^2 , тут недостаточно проверить 2^2^2 < 3^2^2

ЗЫ mayton, загляни в обсуждение задачи, три месяца назад она вообще была нерешаема
автор Беляев Сергей Николаевич, 02 ноября 2015 г. 7:18:37
В связи с тем, что ранее авторское решение и тесты были ошибочными, тесты изменены, все решения отправлены на перепроверку, а сложность задачи повышена с 71 до 95. В результате мы имеем 0 верных решений на текущий момент.
...
Рейтинг: 0 / 0
11.02.2016, 19:08
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168957
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот пускай этот Сергей Николаич нам расскажет как он тестировать это будет.
...
Рейтинг: 0 / 0
11.02.2016, 19:36
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168963
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВот пускай этот Сергей Николаич нам расскажет как он тестировать это будет.
и исходник проверялки пусть покажет, а то вдруг еще чего накосячено
...
Рейтинг: 0 / 0
11.02.2016, 19:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168970
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
ты тут перемудрил
Код: sql
1.
abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon


затестил ради интереса - не проходит мой код с такой проверкой.
у меня проще
Код: sql
1.
abs(x1-x2)>epsilon



Да нет, вроде верно все. Просто epsilon он на то epsilon, чтоб его подбирать при настройке алгоритма.
Задача тут отсечь равные с учетом накопившихся ошибок, не затронув при этом почти равные.



Dima TAleksandr SharahovДело в том, что таких башен конечное число, и, похоже, что после склейки верхних уровней
не существует таких башен высотой более 4 (если считать склеенные уровни за 1).
Т.е. главная фишка алгоритма - именно склейка верхних уровней.
c 10 до 4 не склеить даже если там одни двойки. 2^2^2^2 = 65536 а дальше не склеить.

Но т.к. по условию задачи исходные уровни не более 99, т.е. максимум склеиваются три верхних в один, например 2^2^2 = 16
Как следствие функция проверки должна работать без склеивания. А если она не работает, то значит должна существовать такая пара пятиуровневых башень A(a1^a2^a3^a4^a5) и B(b1^b2^b3^b4^b5) удовлетворяющих условию A<B при
a3^a4^a5>b3^b4^b5 или (a3^a4^a5=b3^b4^b5 и a2>b2) или (a3^a4^a5=b3^b4^b5 и a2=b2 и a1>b1)

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

Ты не понял.

У меня речь идет о 4х ВЕРХНИХ уровнях,
причем после того, как самый верхний их них был получен склейкой
(см. мой алгоритм сравнения 18783990 )


P.S.
Задачей этой почти не занимался, только в метро иногда размышляю, да слежу, что тут пишут )
Все на выходные откладываю удовольствие.
По-хорошему, про 5й уровень доказать надо, что там нету наших башенок, а то все решение коту под хвост.
Да и не особо теперь доверяю проверке от авторов задачи )
...
Рейтинг: 0 / 0
11.02.2016, 19:42
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168978
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonВот пускай этот Сергей Николаич нам расскажет как он тестировать это будет.
и исходник проверялки пусть покажет, а то вдруг еще чего накосячено
Я не думаю что создатели контестеров утруждают себя написанием исходника.
Скорее всего исходник это плод крауд-сорсинга. Или просто отбирается
на конкурсной основе самый компактный (или бысстрый) в своём классе ЯП.
И опять-же его никому не показывают.

Ну.. если-бы я организовывал подобные соревнования то ябы точно не осилил
700 олимпиадных задач решить да еще и без ошибок.
...
Рейтинг: 0 / 0
11.02.2016, 19:47
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169132
VestaBesta
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VestaBesta
Гость
Вирт в этом плане лучший. Все до мельчайших подробностей у него!
...
Рейтинг: 0 / 0
12.02.2016, 00:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169142
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Что у него? 700 олимпиадных задач?
...
Рейтинг: 0 / 0
12.02.2016, 02:30
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169200
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovТы не понял.

У меня речь идет о 4х ВЕРХНИХ уровнях,
причем после того, как самый верхний их них был получен склейкой
(см. мой алгоритм сравнения 18783990 )
Не сработает на такой
Код: sql
1.
2.
3.
2
4 2 99 99 99 99
4 3 98 99 99 99


99^99 это 197 десятичных знаков, а в double мантисса всего 15, т.е. хвост теряется из-за погрешностей.
...
Рейтинг: 0 / 0
12.02.2016, 07:53
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169207
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Если кому надо для отладки - можете взять мой тест с ответом
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
23
9 2 2 2 2 2 2 99 2 9 19
9 99 99 99 99 99 99 98 2 9 19
8 25 34 99 75  2 99 99 92 99 
7 99 99 78 98 99 90 99 99
5 98 99 99 8 2 34
5 99 99 99 2 2 35
5 98 99 99 16 2 33
4 2 2 4 5 4
3 98 99 98 98
4 4 4 4 4 4
3 3 3 3 3
4 2 2 2 2 2
3 64 2 2 2 
3 2 3 2 2
2 4 3 3
3 2 2 2 2
1 3 3
2 2 2 2
1 3 2
1 2 3
0 7
0 5
1 2 2


ответ
Код: sql
1.
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1


...
Рейтинг: 0 / 0
12.02.2016, 08:12
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169245
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovТы не понял.

У меня речь идет о 4х ВЕРХНИХ уровнях,
причем после того, как самый верхний их них был получен склейкой
(см. мой алгоритм сравнения 18783990 )
Не сработает на такой
Код: sql
1.
2.
3.
2
4 2 99 99 99 99
4 3 98 99 99 99


99^99 это 197 десятичных знаков, а в double мантисса всего 15, т.е. хвост теряется из-за погрешностей.

Да посмотри уж, наконец, мое решение 18783990 )
Все сработает.

Повторяю еще раз, твое решение полностью совпадает с моим.
Разница только в работе с epsilon, которую я не настраивал, т.к. пока не занимался этой задачей плотно.

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

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

Вопрос только во времени.
...
Рейтинг: 0 / 0
12.02.2016, 09:17
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169263
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima TНе сработает на такой
Код: sql
1.
2.
3.
2
4 2 99 99 99 99
4 3 98 99 99 99


Да посмотри уж, наконец, мое решение 18783990 )
Все сработает.
Сработает и ладно. Поверю на слово.

Смотрел неоднократно и уже несколько раз писал что китайской грамоте не обучен. Ну не знаю я паскаля с его нездоровым синтаксисом. И ни одного камента у тебя нет. ХЗ что такое High(MaxBaseForPower)
...
Рейтинг: 0 / 0
12.02.2016, 09:49
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169290
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Кажется понял, на что ты надеешься. Думаешь раз совпало, то досравнится тут:
Код: sql
1.
2.
3.
4.
for i:=len1-1 downto 0 do begin;
    Result:=t1[i]-t2[i];
    if Result<>0 then exit;
    end;


Тот пример пройдет, этот не должен.
Код: sql
1.
2.
3.
4.
3
4 5 2 49 4 5
4 3 2 7 2 11
4 2 2 49 32 2


Правильный ответ 3 2 1
...
Рейтинг: 0 / 0
12.02.2016, 10:19
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169342
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

да, думаю )

Твой пример показывает, что от схлопывания может быть не только польза, но и вред.
Чтобы все сработало правильно, надо подстроить жадность алгоритма схлопывания.
У меня она задается константой 2470, исходя из которой рассчитаны значения элементов MaxBaseForPower.
Значит, нужно изменить порог схлопывания так, чтобы оно не выполнялось в данном случае - и все сработает.

Я пробую обсуждать алгоритм, а не значения констант )
...
Рейтинг: 0 / 0
12.02.2016, 11:19
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169380
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

Кстати, там же в исходнике строчкой выше объявления массива MaxBaseForPower для константы 2470
закомментирован другой вариант объявления для константы 300.

Если его раскомментировать, то твой пример проходит.
...
Рейтинг: 0 / 0
12.02.2016, 11:43
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169387
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Можно попробовать зайти с другой стороны.
Если добить все короткие башни справа до 9 членов единицами, то получим всего
99^9 = 913517247483640899 вариантов, что сущий пустяк по сравнению с например с 2^65536!
...
Рейтинг: 0 / 0
12.02.2016, 11:46
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169412
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВМожно попробовать зайти с другой стороны.
Если добить все короткие башни справа до 9 членов единицами, то получим всего
99^9 = 913517247483640899 вариантов, что сущий пустяк по сравнению с например с 2^65536!
правильно 98^9 т.к. нули не используются.
...
Рейтинг: 0 / 0
12.02.2016, 11:56
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169480
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima Tправильно 98^9 т.к. нули не используются.
833747762130149888 - еще лучше :)
Можно ввести последовательность
1 1 1 1 1 1 1 1 1 ->1
1 1 1 1 1 1 1 1 2 ->2
......................
1 1 1 1 1 3 1 1 3 ->2910900
......................
99 99 99 99 99 99 99 99 99 -> 833747762130149888
которая задается формулой
k 9 *99^9+...k 1
где k i 0..9
...
Рейтинг: 0 / 0
12.02.2016, 12:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169494
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima Tправильно 98^9 т.к. нули не используются.
833747762130149888 - еще лучше :)
Можно ввести последовательность
1 1 1 1 1 1 1 1 1 ->1
1 1 1 1 1 1 1 1 2 ->2
......................
1 1 1 1 1 3 1 1 3 ->2910900
......................
99 99 99 99 99 99 99 99 99 -> 833747762130149888
которая задается формулой
k 9 *99^9+...k 1
где k i 0..9
И чем она будет отличаться от того как мы это сейчас пишем? Единичкой вместо пробела и записью слева направо?
...
Рейтинг: 0 / 0
12.02.2016, 12:56
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169560
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima TИ чем она будет отличаться от того как мы это сейчас пишем? Единичкой вместо пробела и записью слева направо?
Пусть то было множество M1.
Вычислим все возможные пирамиды и отсортируем, получим множество M2, точно такой же мощности как и первое.
Теперь осталось найти функцию, которая по каждому номеру элемента из M1 сопоставляет номер элемента из M2.
...
Рейтинг: 0 / 0
12.02.2016, 14:03
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169573
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВ, для начала прикинь сколько времени это будет считаться. Потом сколько места надо будет для хранения результата, потом обсудим "отсортируем"
...
Рейтинг: 0 / 0
12.02.2016, 14:10
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169579
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima TЕвгенийВ, для начала прикинь сколько времени это будет считаться. Потом сколько места надо будет для хранения результата, потом обсудим "отсортируем"
Если найти нужную функцию, то всего этого не потребуется :)
...
Рейтинг: 0 / 0
12.02.2016, 14:14
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169586
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Если выполнить первый пункт "Вычислим все возможные пирамиды", т.е. найти способ вычисления, то функция не потребуется.
...
Рейтинг: 0 / 0
12.02.2016, 14:18
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169909
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima T,

да, думаю )

Твой пример показывает, что от схлопывания может быть не только польза, но и вред.
Чтобы все сработало правильно, надо подстроить жадность алгоритма схлопывания.
У меня она задается константой 2470, исходя из которой рассчитаны значения элементов MaxBaseForPower.
Значит, нужно изменить порог схлопывания так, чтобы оно не выполнялось в данном случае - и все сработает.

Я пробую обсуждать алгоритм, а не значения констант )
Я так и не понял это ноу-хау с MaxBaseForPower. Понимаю что это какой-то результат твоих многоуровневых размышлений, но я не телепат. Будь проще - заработаешь больше.

Если честно - уже устал придумывать тесты (хотя в связи с этим появилось кое-какое понимание как делать тесты) и запости свое "итого" на проверку.
...
Рейтинг: 0 / 0
12.02.2016, 20:19
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169935
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЯ так и не понял это ноу-хау с MaxBaseForPower.


Да там примитивно все.
Пусть два самых уровня башни представляют собой башенку a^b.
Тогда мы заменяем их одним эквивалентным уровнем ("склеиваем"),
если в результате склеивания будет получено значение не больше
некоторой константы (например, 300), в противном случае не склеиваем.
Такое шаманство позволяет "улучшить" плохие башни с маленьким числом сверху.
Это улучшение позволяет сосредоточить основные вычисления на верхних 4х уровнях.
Как мы видели выше, слишком увеличивать эту константу опасно,
т.к. ошибки вычислений приводят к невозможности различить разные башни.

В общем, как раз этим мне и не нравится это решение.
Какие-то полуинтуитивные действия приводят к успеху.
Хочется не то чтобы строгого доказательства,
но хотя бы четкого обоснования, почему все работает.
Почти уверен, что если в условии 99 поменять на 255, алгоритм не сработает.

Ну, и хотелось бы иметь возможность проверить работу алгоритма автора задачи )
...
Рейтинг: 0 / 0
12.02.2016, 20:59
| Ответить | Цитировать | Написать  
Алгоритмы
    #39169938
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov, пропущено слово ВЫСОКИХ:

Пусть два самых ВЫСОКИХ уровня башни представляют собой башенку a^b...
...
Рейтинг: 0 / 0
12.02.2016, 21:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39170093
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Взял следующую по сложности задачку и опубликовал на скруле.

Тяпничные лампочки
...
Рейтинг: 0 / 0
13.02.2016, 01:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39170152
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima TЯ так и не понял это ноу-хау с MaxBaseForPower.


Да там примитивно все.
Пусть два самых уровня башни представляют собой башенку a^b.
Тогда мы заменяем их одним эквивалентным уровнем ("склеиваем"),
Понятно. Некоторые 3хуровневые тоже клеятся, Например 49^(2^2) = 7^(2^3) я такую тебе подсунул :)
...
Рейтинг: 0 / 0
13.02.2016, 07:41
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Алгоритмы
    #39414097
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Люди добрые, помогите. Настрочил корявенький код на Java.
Эти тесты проходит.
 

23
9 2 2 2 2 2 2 99 2 9 19
9 99 99 99 99 99 99 98 2 9 19
8 25 34 99 75 2 99 99 92 99
7 99 99 78 98 99 90 99 99
5 98 99 99 8 2 34
5 99 99 99 2 2 35
5 98 99 99 16 2 33
4 2 2 4 5 4
3 98 99 98 98
4 4 4 4 4 4
3 3 3 3 3
4 2 2 2 2 2
3 64 2 2 2
3 2 3 2 2
2 4 3 3
3 2 2 2 2
1 3 3
2 2 2 2
1 3 2
1 2 3
0 7
0 5
1 2 2

ответ
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

 
3
4 5 2 49 4 5
4 3 2 7 2 11
4 2 2 49 32 2

ответ
3 2 1

При сдаче задачи на проверку на acmp.ru выдает ошибку на втором тесте "Wrong answer".
Может кто знает входные данные для этого теста? Не могу понять, где ошибся.
...
Рейтинг: 0 / 0
04.03.2017, 16:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414139
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
SashaMercuryКнут, Скиена, Кормен.
Приведите пожалуйста пример неоптимального кода, о котором вы пишите выше


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

Корме, Лейзерсон Риверст, Штайн (если не переврал) - книга, которой хватит на всё.
разбита по главам, можно и нужно читать не все, а только общие темы и то, что конкретно сейчас нужно.
...
Рейтинг: 0 / 0
04.03.2017, 19:20
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414141
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
zitz1989, в этих случаях "помогите" не работает. Ты взялся за одну из самых сложных задач того ресурса, решать ее тебя никто не заставляет. Напрягай мозг, ищи что не учел в коде, топик почитай, может мысли какие появятся. Сам, сам, сам.
...
Рейтинг: 0 / 0
04.03.2017, 19:40
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414202
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Dima T, Да, задача непростая. Но тем она и интересна. Пришлось вспомнить курс школьной алгебры. :)
Мыслей по поводу задачи куча, но как лучше впихнуть невпихуемое- хз. Были бы входные данные теста- было бы проще, сразу стало бы ясно, где недоглядел.
Но ничего, буду дальше думать.
...
Рейтинг: 0 / 0
05.03.2017, 00:12
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414204
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
ТриггерманEatsFullLemonsтехнический директор сказал, что мне нужно подтянуть основы алгоритмов, т.к. мой код не всегда самый оптимальныйНу да, да, конечно. А что вы такое супер-важное разрабатывать будете, что позарез нужен оптимальный код? Пишете софт для атомных реакторов? Или для управления самолётами?
Ну будет ваша программа считать 0.2 сек вместо 0.1 сек, и бухгалтерша получит отчёт на 0.1 сек позже? И что?
Там где говорят про алгоритмы и оптимизацию, там налицо явное непонимание вектора развития разработки прикладного ПО.


как бы любой неоптимальный алгоритм на 0.2 вместо 0.1 на 10 миллионах будет работать два дня вместо одного, и чего ты нам тут будешь говорить про вектора развития?
...
Рейтинг: 0 / 0
05.03.2017, 00:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414397
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Час от часу не легче. Алгоритм сравнения написал, второй тест прошло. Теперь не хватает времени на тест(2,15-2,20 вместо положенных 2 секунд). Бьюсь над сокращением времени. Пузырьковую сортировку заменил на быструю- результат не изменился.
На Java никто эту задачу не решил.
Тешу себя надеждой, что дело не во мне, а в Джаве )))
...
Рейтинг: 0 / 0
05.03.2017, 21:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414527
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Время в третьем тесте победил, но теперь выдает "Wrong answer" в тесте №3.
Может кто подкинет еще данных для теста?
...
Рейтинг: 0 / 0
06.03.2017, 10:13
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414609
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Или может подскажет, где поступаю неверно:
1)При чтении данных башню типа N .. y 1 z .. преобразую в N-2 .. y.

2)Нормализую верха башен N .. x y = N-1 .. z, где z=x^y, z<500.
 
Брал 500, т.к. 99^500~(10^2)^500=10^1000<10^1023-вместимость типа double.


3)Из метода сортировки передаю два массива(две башни) в метод boolean isBigger(short[] a, short[] b).
3.1) Сравниваю длину башен. Если одна из них длинней на 3 элемента, то она и больше. И наоборот. Иначе иду далее.
 
N .. 2 2 2 2 2 == N-3 .. 2 65536 ~~ N-3 .. 99 9886 > N-3 .. 99 499.
Это пример граничного случая, когда верх длинной башни состоит из "2", а верх короткой башни- 99^z(где z взят максимальным из пункта 2).

3.2) Добиваю меньшую башню единицами до размера больше башни.
 
N-2 .. x y == N .. x y 1 1

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

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

г)больше либо равна 3(N .. u x y z)- считаем разность двойных логарифмов t.
 
Пусть даны башни (N .. u x y z) и (N .. a b c d). Тогда:
double t=(y^z*ln(x)-c^d*ln(b))+(lnln(u)-lnln(a))
Подсчет ведем именно в таком порядке, т.к. при double t=(y^z*ln(x)+lnln(u))-(c^d*ln(b)+lnln(a)) потеряем в точности, что приведет к ошибке.

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

Вот такой алгоритм. Полностью код не публикую, т.к. во-первых он сильно корявенький и в нем черт ногу сломит, а во-вторых он уже наверное близок к прохождению.
...
Рейтинг: 0 / 0
06.03.2017, 11:38
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414618
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Дополню. Сразу после публикации предыдущего поста решил поиграться со значениями z из пункта 2.
При установке 10<=z<=160 третий тест проходит, но выдает "Wrong answer" в пятом тесте.
...
Рейтинг: 0 / 0
06.03.2017, 11:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414657
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
zitz1989 б)равна 1(1 x y)- сравниваем по логарифму.
ln(x^y)=y*ln(x)
Ты в курсе что double надо совсем по другому сравнивать?
...
Рейтинг: 0 / 0
06.03.2017, 12:54
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414662
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Dima T, нет, не в курсе. Просветите пожалуйста, если не сложно.
Плюс понял, почему z должен быть значительно меньше меньше 500. double хранит до 1,7е+308.
Число 10^1023 взял с конспекта переписанного с JavaRush.ru. Либо JR обманул, или я переписал не то.

Грубо говоря, должно быть так z<150
...
Рейтинг: 0 / 0
06.03.2017, 13:02
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414667
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Dima T,
у меня в коде это выглядит так:
Код: java
1.
2.
if (max == 4)
            return a[3] * log(a[2]) > b[3] * log(b[2]);


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

Такой подход ошибочен?
...
Рейтинг: 0 / 0
06.03.2017, 13:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414678
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
zitz1989Dima T, нет, не в курсе. Просветите пожалуйста, если не сложно.
Плюс понял, почему z должен быть значительно меньше меньше 500. double хранит до 1,7е+308.
Число 10^1023 взял с конспекта переписанного с JavaRush.ru. Либо JR обманул, или я переписал не то.

Грубо говоря, должно быть так z<150
Да, double хранит до 1,7е+308, но не хранит все 308 десятичных разрядов, там только первые 15-16. Гугли про погрешности.

Тут можешь почитать . Про погрешности раздел 4.
...
Рейтинг: 0 / 0
06.03.2017, 13:24
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414689
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Dima T,
Да, про мантиссу слыхал. Спасибо за подсказку. Погуглил, числа с плавающей точкой через > < = сравнивать нельзя.
Проверка должна быть вида (X-Y>эпсилон). Осталось определиться с вычислением "эпсилон" на основе X и Y.
Еще раз спасибо.
...
Рейтинг: 0 / 0
06.03.2017, 13:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414870
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Бьюсь головой об стену.
 
Код: java
1.
2.
3.
4.
5.
6.
7.
        double aT= pow(a[max - 2], a[max - 1]) * log(a[max - 3])+ log(log(a[max - 4]));
        double t = pow(a[max - 2], a[max - 1]) * log(a[max - 3]) - pow(b[max - 2], b[max - 1]) * log(b[max - 3]) + log(log(a[max - 4])) -log(log(b[max - 4]));

        if (t > aT*1.0e-16)
            return true;
        else if (t < -aT*1.0e-16)
            return false;


При эпсилон =aT*1.0e-16 не проходит 5 тест. При =aT*1.0e-11 не проходит 10 тест. При промежуточных значениях =aT*1.0e-15..=aT*1.0e-12 не проходит 12.
...
Рейтинг: 0 / 0
06.03.2017, 16:44
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414957
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Всё. 4 дня, 182 попытки(большая часть из них при подборе эпсилон). Теперь можно и выпить.
Переписал код, массив вместо short сделал int, нормализацию вел до 2e+9. Немного изменил метод нахождения большей из двух башен.
Dima T, боооольшущее спасибо.
...
Рейтинг: 0 / 0
06.03.2017, 18:49
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414984
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
zitz1989Бьюсь головой об стену.
И дальше будешь биться. Ищи обход стены.
zitz1989Всё. 4 дня, 182 попытки(большая часть из них при подборе эпсилон). Теперь можно и выпить.
Я решил и мое время до сих пор лучшее. По количеству букав не на первом месте. Из-за их глупых рейтингов по количеству букав смотрю на свой код год спустя как на китайскую грамоту, я смутно вспоминаю как я это решил, 100500 оптимизаций, в итоге говнокод прошедший проверку. Да и не уверен я что на последний исходник смотрю, т.к. не было цели сохранить решение.
...
Рейтинг: 0 / 0
06.03.2017, 19:31
| Ответить | Цитировать | Написать  
Алгоритмы
    #39414991
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
zitz1989, я так понимаю ты не школьник и не студент, решаешь просто для себя. Если так, то или можешь или не можешь, третьего не дано, а вариант "могу, но с чужой помощью" - это вообще не вариант в реальной жизни, это означает "не могу" даже при положительном результате.

Мой совет: отложи эту задачку и порешай что-нибудь попроще. Со временем и на нее ответ найдешь. А под спойлер не заглядывай.
...
Рейтинг: 0 / 0
06.03.2017, 19:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39415015
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Dima T, наверное не так меня поняли. Я решил ее. Трудности вызвало:
 
-превышение времени выполнения программы. Перепробовал различные сортировки массива, ничего не помогло. В итоге, как говорится, дело было не в бобине, дол**еб сидел в кабине. Сортировка работала быстро. Медленно работал метод, выводящий порядок башни. Он в цикле для каждой башни из отсортированного массива искал ее индекс в неотсортированном.
-сравнение башен. Знал, что double обрезает дробное число, знал про мантиссу. Да почему-то как-то и не подумал. Сравнивал как целочисленные.
-погрешности. Сначала считал по одной формуле, где double умножается на double. Одно урезанное число умножаем на другое. Из-за этого и не проходил 12 тест.

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

И да, я не школьник, не студент. Просто решил в свои 27 лет вникнуть в программирование.
Еще раз спасибо за подсказку про сравнение чисел с плавающей точкой.
...
Рейтинг: 0 / 0
06.03.2017, 20:27
| Ответить | Цитировать | Написать  
Алгоритмы
    #39415018
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Dima T, а по поводу рейтинга... Дурное это дело. Код должен быть в меру короток. Лучше будет на 20 символов больше, но переменные будут называться своими именами, а не "a", "b", "c", "x", "y", "z". Время выполнения и занимаемый объем памяти должен быть в приоритете.
...
Рейтинг: 0 / 0
06.03.2017, 20:32
| Ответить | Цитировать | Написать  
Алгоритмы
    #39415022
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
zitz1989Я решил ее.
Молодец! Поздравляю! Честно. Важно что решил, неважно как. Java не С, есть свои накладные расходы, как по времени, так и по памяти.
...
Рейтинг: 0 / 0
06.03.2017, 20:38
| Ответить | Цитировать | Написать  
Алгоритмы
    #39415025
zitz1989
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zitz1989
Гость
Может пускай тест остается, вроде и не выдает решение задачи, но способствует пониманию некоторых нюансов.

В ближайшее время попробую немного оптимизировать код, верну массив ключей для быстрого сравнения. Думаю и время, и память немного снизятся.
...
Рейтинг: 0 / 0
06.03.2017, 20:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39430110
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Интересная задача. Я тоже попробовал.
Все упомянутые здесь тесты прошёл но пока 3й официалный не смог. неверный ответ.
Только для удовлетворения любопытства, поделитесь тайным знанием.
Тестовыми файлами или просто в ответами на пару вопросов в приватном канале littlesuspense эт live и в самом com.
...
Рейтинг: 0 / 0
30.03.2017, 13:56
| Ответить | Цитировать | Написать  
Алгоритмы
    #39430125
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
[quot Aleksandr SharahovПо-хорошему, про 5й уровень доказать надо, что там нету наших башенок, а то все решение коту под хвост.
Да и не особо теперь доверяю проверке от авторов задачи )[/quot]
A^x vs B^y, 1 < A,B,x,y < 100
Лемма:
Если 10 * x < y то всегда 10*A^x < B^y
Доказательство не сложно.
5 башен как следсвие.
...
Рейтинг: 0 / 0
30.03.2017, 14:11
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Алгоритмы
    #39654603
aleksandr421
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleksandr421
Гость
Dima T,

Я так не понял где ошибка в вашем коде.
в строках сделал long double val[11]; // содержимое
long double cache[11]; // кэш для ускорения расчета
Тут тоже
long double head(int level) {

попробывал взять вот такой логарифм (log2(log2(val[level])) + log2(val[level + 1]) * val[level + 2]);

while(height > 1 && (log2(val[height - 2]) * val[height - 1]) < 50) {
val[height - 2] = pow(val[height - 2], val[height - 1]);

всё ровно пятый тест))
...
Рейтинг: 0 / 0
03.06.2018, 23:30
| Ответить | Цитировать | Написать  
Алгоритмы
    #39654619
aleksandr421
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleksandr421
Гость
тест проходит когда поменял log10 на log2

...

Модератор: Удалил исходник. Просьба не выкладывать готовые решения целиком.
...
Рейтинг: 0 / 0
04.06.2018, 03:23
| Ответить | Цитировать | Написать  
Алгоритмы
    #39654669
aleksandr421
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleksandr421
Гость
Dima T,можно вам в лс где нибудь написать?
...
Рейтинг: 0 / 0
04.06.2018, 08:55
| Ответить | Цитировать | Написать  
Алгоритмы
    #39654688
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
aleksandr421Dima T,можно вам в лс где нибудь написать?
В этом форуме нет ЛС, да и не люблю я индивидуальные консультации устраивать.
Пиши сюда, а лучше топик отдельный создай со своим вопросом.
...
Рейтинг: 0 / 0
04.06.2018, 09:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39655219
aleksandr421
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleksandr421
Гость
Dima T,

не будет никакой консультации,просто есть предложение всего одно.
...
Рейтинг: 0 / 0
04.06.2018, 21:22
| Ответить | Цитировать | Написать  
Алгоритмы
    #39655431
aleksandr421
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleksandr421
Гость
Dima T,
просто мне её задали в вузе,не могли бы вы мне немного помочь естественно не безвозмездно.Можете мне на эмеил сами написать.
...
Рейтинг: 0 / 0
05.06.2018, 11:25
| Ответить | Цитировать | Написать  
Алгоритмы
    #39655483
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
aleksandr421Dima T,
просто мне её задали в вузе,не могли бы вы мне немного помочь естественно не безвозмездно.Можете мне на эмеил сами написать.
Ничем не могу помочь. Если тебе задали, то тебе и решать.
...
Рейтинг: 0 / 0
05.06.2018, 12:11
| Ответить | Цитировать | Написать  
208 сообщений из 208, показаны все 9 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]