Бампец
Бумп
Бампер
B U M P
Бамп
БЭМБ
Бамп
Бамп
Б А М П
А
М
П
А
М
П
Ответ: твоя мамка шлюха
а по сабжу - успшнокодеры не сидят на дваче
а по сабжу - успшнокодеры не сидят на дваче
оставь мыло есть вопрос по кодингу
Разве только успешнокодер сможет ее решить?
ничо не понимаю в спортивном кодинге, но вкотилсо
в условии намек на то что сортировка должна осуществляться без вычисления самой башни, по каким то признакам?
Но я в основном занимаюсь именно спортивным программированием
ну на пшп передать массив из файла или xargs'om
оставь мыло, бабок подкину если поможешь
оставь мыло, бабок подкину если поможешь
Раньше условие было немного иным, и можно было посчитать полный размер башни через тип Extended на Паскале, у меня даже имеется этот код, но там были неточности при округлении. Сейчас уже считать напрямую нельзя, только по признакам.
> пшп
Тут я не смогу помочь.
а на чем кодишь вообще? зачем ты нужен не зная даже пшп
Жавапитуг на слоте ОПа.
Ну например, можно однозначно сказать что одна башня больше другой, если все числа равны или больше всех чисел другой башни
мимо капитан очевидность
мимо капитан очевидность
А как быть с башнями
7 2
2 7
например?
Могу решить это, но работать за бесплатно это привилегии школьников-олимпиадников.
мимо шарподебил
мимо шарподебил
дать каждому числу какой то условный ранг, который показывает степень влияния на общую сумму?
Ну, конкретно я хочу понять хотя бы принцип решения, уж очень интересно.
По моему на числовой оси они и так находятся в порядке влиятельности..
Знающий анон сегодня не на борде?
ну типа для твоего примера было бы
71 + 22<21 + 72
только вместо 1,2 должна быть какая то формула
бджада, разметка
Балдежно.
как то так
•дарю тебе сивол для умножения •••••• вот тебе ещё отсыпал
зачем, если можно скринить
дальше можно развивать формулу и например учитывать в коэффициенте числа которые стоят перед конкретным числом в башне
То есть предлагаешь вычислять коэф каждого числа относительно того, перед каким числом оно стоит?
например, коэф каждого числа это его порядковый номер умноженный на произведение всех чисел, стоящих перед ним
но это как то слишком наивно
Мне кажется слишком много надо будет высчитывать в таком случае.
При большом количестве "высоких" башен не зайдет.
Думаю надо чтото типа системы очков сделать.
Чем выше порядок числа тем больше строка получает очков и потом сравнить очки всех строк и построить по порядку.
Чем выше порядок числа тем больше строка получает очков и потом сравнить очки всех строк и построить по порядку.
давайте сначала рассмотрим башни длиной в 2
их можно сравнивать только при одинаковых основаниях или при одинаковых степенях
то есть сначала надо будет сводить как то
их можно сравнивать только при одинаковых основаниях или при одинаковых степенях
то есть сначала надо будет сводить как то
Инетересная задача. Я бы ее стал решать так:
надо приводить все башни к одному основанию, например, к 2. То есть a0^a1^a2=2^2^(lg(lg a0)+a2 lg(a1))
Тогда, например, два числа a0^a1^a2 и b0^b1^b2 уже не надо сравнивать напрямую, надо сравнивать показатели lg(lg a0)+a2 lg(a1) и lg(lg b0)+b2 lg(b1), а логарифмы уже без проблем влезают в память. Понятно, что алгоритм надо чуть усложнить с учетом разной длины башен, но я думаю, это можно сделать. Например, с помощью логарифмов можно выровнять длины башен так, чтобы самые короткие удлинились. Если длина башни больше трех, алгоритм можно повторять рекурсивно для a2 и b2. Ну это идея, которая у меня возникла за 5 минут.
Но чтобы свести к одинаковому основанию, нужно предварительно вычислить степень.
Это, конечно, тупо и напролом, но почему бы не юзать BigInteger?
Для начала у всех башен нужно удалить всё, что находится правее 1. Далее отфильтровать простые еденицы - то есть если в основании 1, то всё правее отфильтруется и эти еденицы автоматом в самой жопе находятся и их сравнивать смысла нету.
На одимпиадах обычно вроде нельзя пользоваться подобными расширениями. Только самый базовый набор типов, только хардкор. Раньше был целый класс задач на большие числа, и алгоритм надо было реализовывать всегда самому. Как сейчас, не знаю.
Там по умолчанию нет единиц. Очевидно, что когда в башне стоит единица, башня на ней обрывается.
>Раньше был целый класс задач на большие числа
Больше всяких longint'ов и прочей стандартной числовой чепухи, но такие задачи были на целые числа и решались с помощью строк.
>Каждое из aij - целое число в пределах от 1 до 99
И в примерах есть основания еденицы.
Сам думал о чем то подобном, но в итоге ни к чему не пришел. Интересно.
В задачах на большие числа обычно используют массивы, где в каждую ячейку пихают отдельный разряд.
>еденицы
Сука, заебал.
Ок, но с единицами - это тривиальное место.
>И в примерах есть основания еденицы
Это не основания, а величина башни.
>Сам думал о чем то подобном, но в итоге ни к чему не пришел. Интересно.
Просто очевидно, что лучше свести задачу в вычислению логарифмов, так расходуется минимум памяти, надо придумать, как к этому свести задачу.
Вообще, что-то мне подсказывает, что большие числа в этой задаче использовать не нужно. Судя по результатам, лучшие решения используют совсем мало памяти, я думаю там какое-то похожее решение. Задача больше математическая, чем кодерская.
>Задача больше математическая, чем кодерская.
Ну это понятно. Ключевой момент - создание математической модели алгоритма сравнения чисел с кучей степеней.
>a0^a1^a2=2^2^(lg(lg a0)+a2 lg(a1))
Что то мне подсказывает, что не равно. Кто то проверял?
a^b^c = 2^(lg(a))^b^c = 2^(lg(a)b^c) = 2^2^[lg(lg(a)b^c)] = 2^2^[lg(lg(a))+lg(b^c)] = 2^2^[lg(lg(a))+c lg(b)]
На самом деле для решения задачи достаточно
a^b = 2^2^[lg(lg(a))+lg(b)], и рекурсии для b
И как будет работать эта рекурсия?
Заместо b разве не будет тогда число с основанием двойки и прочим дерьмом?
У тебя есть два числа, a0^a1 и b0^b1, благодаря этой формуле тебе надо сравнить двойной логарифм от a0 и b0 и повторить процедуру для a1, b1.
Я вот сейчас посчитал на калькуляторе некоторые значения. Формула не робит чота.
5^2 = 25
2^2^( lg(lg(5)) + lg(2) ) = 2.1526
lg в калькуляторе по какому основанию? По умолчанию 10 обычно, я подразумевал основание 2
>>> 22(np.log2(np.log2(5))+np.log2(2))
24.999999999999993
блядская разметка в макабе
>>> 2^2^(np.log2(np.log2(5))+np.log2(2))
24.999999999999993
Я просто увидел lg и сразу десятку накрутил.
Сори, думал, что очевидно, что должно быть 2.
Теперь все встает на свои места!
>a^b = 2^2^[lg(lg(a))+lg(b)]
Погоди, я все еще не понимаю, как работает эта рекурсия. Можешь разжевать?
Кажись работает: https://ideone.com/y87Rdp
Почти
2 4 3 7 6 10 9 5 8 1 - у тебя
2 4 3 6 7 5 9 10 1 8 - в ответе
Уверен? 3^3 = 27, 2^2^2 = 2^4 = 16. А у тебя 16 стоит после 27
Давай ка еще разок
Походу все проебались
2. 1 2 2 = 4
4. 1 2 3 = 8
3. 1 3 2 = 9
6. 2 2 2 2 = 16
7. 1 3 3 = 27
5. 3 2 2 2 2 = 256
10. 2 2 3 4 = 4096
1. 4 2 2 2 2 2 = 65536
9. 2 4 3 3 = 262144
8. 3 3 3 3 3 = 7625597484987
Билять!
2. 1 2 2 = 4
4. 1 2 3 = 8
3. 1 3 2 = 9
6. 2 2 2 2 = 16
7. 1 3 3 = 27
5. 3 2 2 2 2 = 256
10. 2 2 3 4 = 4096
1. 4 2 2 2 2 2 = 65536
9. 2 4 3 3 = 262144
8. 3 3 3 3 3 = 7625597484987
Ну да, бля. Вот только 2^2^2^2 = 2^2^4 = 2^16 = 65536
А 2^2^2^2^2 = 2^2^2^4 = 2^2^16 = 2^65536
Я не понимаю, как это твоя хрень работает
Ты в лоб считаешь чтоли?
Да, обосрался, не с той стороны считать начал.
>2^2^2^2
>не с той стороны
What?
Погоди, ты 2 возводил в 2, потом это в два и так далее?
((2^2)^2)^2 шоли?
И получил 2^(222)
Так?
Ну как тебе сказать, это просто лексиграфическое сравнение списков. На тестовом примере получилось почти правильно, но на самом деле это хуета.
Да, задание читать надо было внимательнее.
Мимокрокодил, не буду отвлекать.
Может тоже попробуешь решить адекватно? Интересная же задачка.
Рабочий день заканчивается, как-нибудь в следующий раз, анон.
С логарифмами вполне адекватный вариант, на мой взгляд.
Ладно. Как думаешь, стоит ли почаще подобные треды пилить, чтоб разбавить фап-треды, вебм-парашу и прочее?
Неа, найди себе кодерский чатик или ещё что-нибудь и забудь харкач.
Так то полезно иногда мозги размять и интересно.
В бредаче скорее всего утонет.
Не совсем понимаю, как вам простое взятие логарифма поможет. Даже логарифм от искомых чисел не вместится ни в какой тип данных (или, если какой-нибудь BigDecimal в Java юзать с бесконечной точностью, всё равно не полезет в память компьютера). И даже логарифм от логарифма не полезет.
Можно исхитриться, и делать так: пишем компаратор для сортировки. Даны два числа. Если какое-либо из них не лезет, например, в long double, сравниваем логарифмы. Если опять не лезет - сравниваем логарифмы логарифмов. Потом логарифмы логарифмов лоагрифмов, ну и так далее, пока оба числа не полезут. Какое-то из них уже на каком-то этапе может в ноль превратиться - тогда можно сразу сказать, что оно меньше.
Не факт, что пройдёт по точности. Но это ещё написать надо, что не так просто, а мне лень сейчас.
Можно исхитриться, и делать так: пишем компаратор для сортировки. Даны два числа. Если какое-либо из них не лезет, например, в long double, сравниваем логарифмы. Если опять не лезет - сравниваем логарифмы логарифмов. Потом логарифмы логарифмов лоагрифмов, ну и так далее, пока оба числа не полезут. Какое-то из них уже на каком-то этапе может в ноль превратиться - тогда можно сразу сказать, что оно меньше.
Не факт, что пройдёт по точности. Но это ещё написать надо, что не так просто, а мне лень сейчас.
Если на вход будет дано 5000 башен, то времени не хватит с такой сортировкой.
Почему не хватит? Ты пишешь компаратор. Стандартная сортировка Java или из stl с++ вызывает его n log n раз. Сам компаратор будет не более 9 раз брать логарифм у каждого числа.
>Сам компаратор будет не более 9 раз брать логарифм у каждого числа.
> не более 9 раз
Чому?
Потому что чисел в каждой башне не более 9. Очевидно, что если 9 раз прологарифмировать такую башню, получится число, которое лезет в стандартный тип данных.
Добавлю, если ты захочешь это писать, что логарифмировать нетривиально.
На каждом этапе логарифмирования придется поддерживать что-то вида a + b x^y^z. Если x^y^z достаточно маленькое, то считаем в тупую. Если нет, то отбрасываем старую a (очевидно, что точности вычислений все равно не хватит, чтобы эта a вообще что-то значила). После чего говорим, что теперь new_a = log(b), new_b = log(x) - и переходим к new_a + new_b y^z.
Да, но изначальное число, которое надо прологарифмировать не влезет ни в один тип.
Выше расписал, как делать. Изначальное число не нужно.
Сначала берем a = 0, b = 1.
Говнокод? Говнокод!
https://ideone.com/8h3rwH
https://ideone.com/8h3rwH
На сайте тесты прогонял?
Да, не будет работать при сравнениях типа 1 и 99^99^99, в данном случае могут помочь проверки, типо: если a0<b0, a1<b1...ak<bk, то вторая башня больше, но я ебал это добавлять
решил за 20 минут.
Нет, не пройдет. Я просто показал, что вариант с логарифмами может сработать, а дальше ума не хватает
Wrong answer на втором тесте.
Wrong answer? Значит код нерабочий, ну и хуй с ним, я пытался
лучше бы вы девственность теряли, Дауны
Лучше бы помог, неДаун.
>2к17
>турниры по программированию
Может знает кто - турниры по маханию киркой проводятся?
А что тебя не устраивает?
Как тебе помочь? Во всём интете дохуя курсов пикапа, дерзай.
Не, у меня то всё заебись.
А почему у тебя тригернуло на турниры по программированию?
Мне они не нужны, и без них все получается.
Вангую что щас дебс начнёт что-то втриать про галеры. Зоонаблюдаем.
Удивляет как можно так бесцельно прожигать свою жизнь.
Лол. И меня тригернутым называете?
>нет нужды
>тратит время на давлю кнопок
>нет нужды
Кому ты пиздишь, хокага ебаная?
Научи, как "цельно".
Ну, это деньги приносит и бесплатные поездки по городам.
А что нет чтоли? В каждом подобном треде появляется подобный отбитый чувачёк и начинает лезть со своим бредом. Одна и та же хуйня каждый раз.
А могли бы баб ебать. Дауны аз ис.
Оп, а в чем прикол спортивного программирования?
«…я был взят на судно „Северный“, потому что я обнаружил храбрость. Когда осаждали город Хат-Уарит [Аварис, столица гиксосов], я обнаружил храбрость в пешем бою перед лицом царя. Я был назначен на корабль „Сияющий в Мемфисе“. Сражался на воде, на канале Па-джел-ку около Авариса. Я участвовал в рукопашном бою. Я взял руку [убил врага, вероятно знатного, военачальника или богатыря]. Сообщили об этом царскому вестнику. Пожаловали мне „Золото храбрости“. Снова сражались на этом месте. Я снова участвовал в рукопашном бою. Я взял руку. Мне пожаловали „Золото храбрости“ во второй раз.»
«…После того, как его величество разгромил азиатов ментиу-сатет, он поднялся по реке [прошёл вверх по Нилу] до Хентхеннофера для того, чтобы уничтожить нубийские племена лучников иунтиу-сетиу … Его величество поплыл вниз по реке, сердце его радостно, переполнено мужеством и силой. Он схватил южан и северян.»
«И я вез на гребном судне царя Верхнего и Нижнего Египта, покойного Джосеркара, когда он плыл вверх по Нилу в Нубию с целью расширить границы Египта.»
Тебе пояснить за то что там происходит или за профиты?
А я и так ебу, и соревнованиями по программированию занимаюсь. Одно другому не мешает.
Ну, благо, с этим проблем нет.
Т.е. каждый раз в любом треде, где какие то долбоёбы тратят время на непойми что, приходит мудрец, поучает вас жизни, а вы его называете "отбитым чувачком"? Хера себе вы ебанутые.
Я не думал, что человек который называет себя вангой, а потом проёбывается имеет право говорить что-то
Проецируешь, небось, сам с себя орешь?
Девственность потеряй, ебло.
Кекаю с тебя, мамкин недевственник.
>Проецируешь
>небось, сам с себя орешь
ооо психологи комнатные подъехали.
Я баб с 14 лет ебу, и жизнью живой нормальной, а не кнопки давлю и наруту смотрю как некоторые...
Т.е. давить кнопки и ебать баб - это взаимоисключающие вещи? У меня для тебя плохие новости (ты сейчас кнопки давишь).
За Наруто и двор стреляю в упор.
>Т.е. давить кнопки
Выпасть на дурачка решил? Очевидно, что он про программирование, социофоб ебучий.
x = e ^ ln(x)
x^y = e ^ ln (x ^ y) + e ^ [y(ln(x))]
x^y^z = x ^ [e ^ z(ln(y))] = e ^ [e ^ z(ln(y))*ln x]
главное привести к одному основанию, далее - какое произведение логарифмов и последней степени меньше. вроде так
так как все числа больше единицы, то подвохов не должно быть
мимо джава-веб-макака 100к, вполне мог где обосраться т.к. дно в математиках
x^y = e ^ ln (x ^ y) + e ^ [y(ln(x))]
x^y^z = x ^ [e ^ z(ln(y))] = e ^ [e ^ z(ln(y))*ln x]
главное привести к одному основанию, далее - какое произведение логарифмов и последней степени меньше. вроде так
так как все числа больше единицы, то подвохов не должно быть
мимо джава-веб-макака 100к, вполне мог где обосраться т.к. дно в математиках
Да, поскидывай еще подобных проблем олимпиадных
То есть разные числа
7 2 - 7^2
2 7 - 2^7
По сути 7 2 - входные данные, которые из себя представляют 7^2.
Раз тут речь зашла про программирование, то подскажите как в mathcad в условии цикла while поставить логическое И? Я пытался поставить &, но вместо этого в mathcad вылезает шаблон интеграла
С недавних пор начал участвовать в разных турнирах по спортивному программированию, одиночному и командному. Иногда даже были какие-то успехи.
В чем суть, около года назад заметил одну задачку, которую ни я, ни мои знакомые не смогли решить. Сейчас же вспомнил о ней.
http://acmp.ru/index.asp?main=task&id_task=561
В 2005 году она была на одном турнире, но и там ее никто не решил.
Сможет ли мейлач ее осилить?