Сап, мейлач.С недавних пор начал участвовать в разных турнирах по спортивному программированию, одиночному и командному. Иногда даже были какие-то успехи. В чем суть, около года назад заметил одну задачку, которую ни я, ни мои знакомые не смогли решить. Сейчас же вспомнил о ней.http://acmp.ru/index.asp?main=task&id_task=561В 2005 году она была на одном турнире, но и там ее никто не решил.Сможет ли мейлач ее осилить?
Бампец
Бумп
Бампер
B U M P
Бамп
БЭМБ
Б А М ПАМП
Ответ: твоя мамка шлюхаа по сабжу - успшнокодеры не сидят на дваче
оставь мыло есть вопрос по кодингу
>>151236842Разве только успешнокодер сможет ее решить?
>>151236246 (OP)ничо не понимаю в спортивном кодинге, но вкотилсо в условии намек на то что сортировка должна осуществляться без вычисления самой башни, по каким то признакам?
>>151236925Но я в основном занимаюсь именно спортивным программированием
ну на пшп передать массив из файла или xargs'omоставь мыло, бабок подкину если поможешь
>>151237003Раньше условие было немного иным, и можно было посчитать полный размер башни через тип Extended на Паскале, у меня даже имеется этот код, но там были неточности при округлении. Сейчас уже считать напрямую нельзя, только по признакам.
>>151237192> пшпТут я не смогу помочь.
а на чем кодишь вообще? зачем ты нужен не зная даже пшп
>>151237497Жавапитуг на слоте ОПа.
Ну например, можно однозначно сказать что одна башня больше другой, если все числа равны или больше всех чисел другой башни мимо капитан очевидность
>>151237555А как быть с башнями 7 22 7например?
Могу решить это, но работать за бесплатно это привилегии школьников-олимпиадников.мимо шарподебил
>>151237656дать каждому числу какой то условный ранг, который показывает степень влияния на общую сумму?
>>151237815Ну, конкретно я хочу понять хотя бы принцип решения, уж очень интересно.
>>151237834По моему на числовой оси они и так находятся в порядке влиятельности..
Знающий анон сегодня не на борде?
>>151238036ну типа для твоего примера было бы 71 + 22<21 + 72только вместо 1,2 должна быть какая то формула
>>151238475бджада, разметка
>>151238572Балдежно.
>>151238623как то так
>>151238650 •дарю тебе сивол для умножения •••••• вот тебе ещё отсыпал
>>151238768зачем, если можно скринить дальше можно развивать формулу и например учитывать в коэффициенте числа которые стоят перед конкретным числом в башне
>>151239099То есть предлагаешь вычислять коэф каждого числа относительно того, перед каким числом оно стоит?
>>151239176например, коэф каждого числа это его порядковый номер умноженный на произведение всех чисел, стоящих перед ним но это как то слишком наивно
>>151239365Мне кажется слишком много надо будет высчитывать в таком случае.При большом количестве "высоких" башен не зайдет.
Думаю надо чтото типа системы очков сделать.Чем выше порядок числа тем больше строка получает очков и потом сравнить очки всех строк и построить по порядку.
давайте сначала рассмотрим башни длиной в 2их можно сравнивать только при одинаковых основаниях или при одинаковых степеняхто есть сначала надо будет сводить как то
>>151236246 (OP)Инетересная задача. Я бы ее стал решать так:надо приводить все башни к одному основанию, например, к 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 минут.
>>151240557Но чтобы свести к одинаковому основанию, нужно предварительно вычислить степень.
>>151236246 (OP)Это, конечно, тупо и напролом, но почему бы не юзать BigInteger?
>>151240745Для начала у всех башен нужно удалить всё, что находится правее 1. Далее отфильтровать простые еденицы - то есть если в основании 1, то всё правее отфильтруется и эти еденицы автоматом в самой жопе находятся и их сравнивать смысла нету.
>>151240986На одимпиадах обычно вроде нельзя пользоваться подобными расширениями. Только самый базовый набор типов, только хардкор. Раньше был целый класс задач на большие числа, и алгоритм надо было реализовывать всегда самому. Как сейчас, не знаю.
>>151241028Там по умолчанию нет единиц. Очевидно, что когда в башне стоит единица, башня на ней обрывается.
>>151241102>Раньше был целый класс задач на большие числаБольше всяких longint'ов и прочей стандартной числовой чепухи, но такие задачи были на целые числа и решались с помощью строк.>>151241175>Каждое из aij - целое число в пределах от 1 до 99И в примерах есть основания еденицы.
>>151240745Сам думал о чем то подобном, но в итоге ни к чему не пришел. Интересно.>>151241102В задачах на большие числа обычно используют массивы, где в каждую ячейку пихают отдельный разряд.
>>151241246>еденицыСука, заебал.Ок, но с единицами - это тривиальное место.
>>151241246>И в примерах есть основания еденицыЭто не основания, а величина башни.
>>151241275>Сам думал о чем то подобном, но в итоге ни к чему не пришел. Интересно.Просто очевидно, что лучше свести задачу в вычислению логарифмов, так расходуется минимум памяти, надо придумать, как к этому свести задачу.Вообще, что-то мне подсказывает, что большие числа в этой задаче использовать не нужно. Судя по результатам, лучшие решения используют совсем мало памяти, я думаю там какое-то похожее решение. Задача больше математическая, чем кодерская.
>>151241434>Задача больше математическая, чем кодерская.Ну это понятно. Ключевой момент - создание математической модели алгоритма сравнения чисел с кучей степеней.
>>151240745>a0^a1^a2=2^2^(lg(lg a0)+a2 lg(a1))Что то мне подсказывает, что не равно. Кто то проверял?
>>151241792a^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)]
>>151242059На самом деле для решения задачи достаточноa^b = 2^2^[lg(lg(a))+lg(b)], и рекурсии для b
>>151242216И как будет работать эта рекурсия?Заместо b разве не будет тогда число с основанием двойки и прочим дерьмом?
>>151242280У тебя есть два числа, a0^a1 и b0^b1, благодаря этой формуле тебе надо сравнить двойной логарифм от a0 и b0 и повторить процедуру для a1, b1.
>>151242430Я вот сейчас посчитал на калькуляторе некоторые значения. Формула не робит чота.5^2 = 252^2^( lg(lg(5)) + lg(2) ) = 2.1526
>>151242710lg в калькуляторе по какому основанию? По умолчанию 10 обычно, я подразумевал основание 2>>> 22(np.log2(np.log2(5))+np.log2(2))24.999999999999993
>>151242896блядская разметка в макабе>>> 2^2^(np.log2(np.log2(5))+np.log2(2))24.999999999999993
>>151242896Я просто увидел lg и сразу десятку накрутил.
>>151242967Сори, думал, что очевидно, что должно быть 2.
>>151242999Теперь все встает на свои места!
>>151242216>a^b = 2^2^[lg(lg(a))+lg(b)]Погоди, я все еще не понимаю, как работает эта рекурсия. Можешь разжевать?
Кажись работает: https://ideone.com/y87Rdp
>>151245436Почти2 4 3 7 6 10 9 5 8 1 - у тебя2 4 3 6 7 5 9 10 1 8 - в ответе
>>151245660https://ideone.com/UTmGeAЕщё раз все проверил, думаю проеб у них.
>>151248201Уверен? 3^3 = 27, 2^2^2 = 2^4 = 16. А у тебя 16 стоит после 27
>>151248201Давай ка еще разок
>>151248201>>151248575Походу все проебались2. 1 2 2 = 44. 1 2 3 = 83. 1 3 2 = 96. 2 2 2 2 = 167. 1 3 3 = 275. 3 2 2 2 2 = 25610. 2 2 3 4 = 40961. 4 2 2 2 2 2 = 655369. 2 4 3 3 = 2621448. 3 3 3 3 3 = 7625597484987
>>151248839Билять!2. 1 2 2 = 44. 1 2 3 = 83. 1 3 2 = 96. 2 2 2 2 = 167. 1 3 3 = 275. 3 2 2 2 2 = 25610. 2 2 3 4 = 40961. 4 2 2 2 2 2 = 655369. 2 4 3 3 = 2621448. 3 3 3 3 3 = 7625597484987
>>151248839Ну да, бля. Вот только 2^2^2^2 = 2^2^4 = 2^16 = 65536А 2^2^2^2^2 = 2^2^2^4 = 2^2^16 = 2^65536
>>151248201Я не понимаю, как это твоя хрень работаетТы в лоб считаешь чтоли?
>>151249024Да, обосрался, не с той стороны считать начал.
>>151249265>2^2^2^2>не с той стороны What?
>>151249314Погоди, ты 2 возводил в 2, потом это в два и так далее?((2^2)^2)^2 шоли?И получил 2^(222)Так?
>>151249263Ну как тебе сказать, это просто лексиграфическое сравнение списков. На тестовом примере получилось почти правильно, но на самом деле это хуета.
>>151249553Да, задание читать надо было внимательнее.Мимокрокодил, не буду отвлекать.
>>151249808Может тоже попробуешь решить адекватно? Интересная же задачка.
>>151250042Рабочий день заканчивается, как-нибудь в следующий раз, анон.С логарифмами вполне адекватный вариант, на мой взгляд.
>>151250518Ладно. Как думаешь, стоит ли почаще подобные треды пилить, чтоб разбавить фап-треды, вебм-парашу и прочее?
>>151250704Неа, найди себе кодерский чатик или ещё что-нибудь и забудь харкач.
>>151250704Так то полезно иногда мозги размять и интересно.В бредаче скорее всего утонет.
Не совсем понимаю, как вам простое взятие логарифма поможет. Даже логарифм от искомых чисел не вместится ни в какой тип данных (или, если какой-нибудь BigDecimal в Java юзать с бесконечной точностью, всё равно не полезет в память компьютера). И даже логарифм от логарифма не полезет.Можно исхитриться, и делать так: пишем компаратор для сортировки. Даны два числа. Если какое-либо из них не лезет, например, в long double, сравниваем логарифмы. Если опять не лезет - сравниваем логарифмы логарифмов. Потом логарифмы логарифмов лоагрифмов, ну и так далее, пока оба числа не полезут. Какое-то из них уже на каком-то этапе может в ноль превратиться - тогда можно сразу сказать, что оно меньше.Не факт, что пройдёт по точности. Но это ещё написать надо, что не так просто, а мне лень сейчас.
>>151251181Если на вход будет дано 5000 башен, то времени не хватит с такой сортировкой.
>>151251726Почему не хватит? Ты пишешь компаратор. Стандартная сортировка Java или из stl с++ вызывает его n log n раз. Сам компаратор будет не более 9 раз брать логарифм у каждого числа.
>>151251851>Сам компаратор будет не более 9 раз брать логарифм у каждого числа.> не более 9 разЧому?
>>151252091Потому что чисел в каждой башне не более 9. Очевидно, что если 9 раз прологарифмировать такую башню, получится число, которое лезет в стандартный тип данных.
>>151252091Добавлю, если ты захочешь это писать, что логарифмировать нетривиально.На каждом этапе логарифмирования придется поддерживать что-то вида a + b x^y^z. Если x^y^z достаточно маленькое, то считаем в тупую. Если нет, то отбрасываем старую a (очевидно, что точности вычислений все равно не хватит, чтобы эта a вообще что-то значила). После чего говорим, что теперь new_a = log(b), new_b = log(x) - и переходим к new_a + new_b y^z.
>>151252171Да, но изначальное число, которое надо прологарифмировать не влезет ни в один тип.
>>151252492Выше расписал, как делать. Изначальное число не нужно.
>>151252492Сначала берем a = 0, b = 1.
Говнокод? Говнокод!https://ideone.com/8h3rwH
>>151253252На сайте тесты прогонял?
>>151253252Да, не будет работать при сравнениях типа 1 и 99^99^99, в данном случае могут помочь проверки, типо: если a0<b0, a1<b1...ak<bk, то вторая башня больше, но я ебал это добавлять
решил за 20 минут.
>>151253436Нет, не пройдет. Я просто показал, что вариант с логарифмами может сработать, а дальше ума не хватает
>>151253252>>151253436Wrong answer на втором тесте.
>>151253512Wrong answer? Значит код нерабочий, ну и хуй с ним, я пытался
лучше бы вы девственность теряли, Дауны
>>151253691Лучше бы помог, неДаун.
>>151236246 (OP)>2к17>турниры по программированиюМожет знает кто - турниры по маханию киркой проводятся?
>>151253822А что тебя не устраивает?
>>151253734Как тебе помочь? Во всём интете дохуя курсов пикапа, дерзай.
>>151253886Не, у меня то всё заебись.
>>151253909А почему у тебя тригернуло на турниры по программированию?
>>151253907Мне они не нужны, и без них все получается.
>>151253994Вангую что щас дебс начнёт что-то втриать про галеры. Зоонаблюдаем.
>>151253994Удивляет как можно так бесцельно прожигать свою жизнь.
>>151254054Лол. И меня тригернутым называете?
>>151254025>нет нужды>тратит время на давлю кнопок>нет нуждыКому ты пиздишь, хокага ебаная?
>>151254068Научи, как "цельно".
>>151254068Ну, это деньги приносит и бесплатные поездки по городам.
>>151254097А что нет чтоли? В каждом подобном треде появляется подобный отбитый чувачёк и начинает лезть со своим бредом. Одна и та же хуйня каждый раз.
>>151254141>>151254129А могли бы баб ебать. Дауны аз ис.
Оп, а в чем прикол спортивного программирования?
>>151254054«…я был взят на судно „Северный“, потому что я обнаружил храбрость. Когда осаждали город Хат-Уарит [Аварис, столица гиксосов], я обнаружил храбрость в пешем бою перед лицом царя. Я был назначен на корабль „Сияющий в Мемфисе“. Сражался на воде, на канале Па-джел-ку около Авариса. Я участвовал в рукопашном бою. Я взял руку [убил врага, вероятно знатного, военачальника или богатыря]. Сообщили об этом царскому вестнику. Пожаловали мне „Золото храбрости“. Снова сражались на этом месте. Я снова участвовал в рукопашном бою. Я взял руку. Мне пожаловали „Золото храбрости“ во второй раз.»«…После того, как его величество разгромил азиатов ментиу-сатет, он поднялся по реке [прошёл вверх по Нилу] до Хентхеннофера для того, чтобы уничтожить нубийские племена лучников иунтиу-сетиу … Его величество поплыл вниз по реке, сердце его радостно, переполнено мужеством и силой. Он схватил южан и северян.»«И я вез на гребном судне царя Верхнего и Нижнего Египта, покойного Джосеркара, когда он плыл вверх по Нилу в Нубию с целью расширить границы Египта.»
>>151254228Тебе пояснить за то что там происходит или за профиты?
>>151254213А я и так ебу, и соревнованиями по программированию занимаюсь. Одно другому не мешает.
>>151254213Ну, благо, с этим проблем нет.
>>151254183Т.е. каждый раз в любом треде, где какие то долбоёбы тратят время на непойми что, приходит мудрец, поучает вас жизни, а вы его называете "отбитым чувачком"? Хера себе вы ебанутые.Я не думал, что человек который называет себя вангой, а потом проёбывается имеет право говорить что-то
>>151254304>>151254284
>>151254373
>>151254400Проецируешь, небось, сам с себя орешь?
>>151254440Девственность потеряй, ебло.
>>151254465Кекаю с тебя, мамкин недевственник.
>>151254440>Проецируешь>небось, сам с себя орешьооо психологи комнатные подъехали.
>>151254506Я баб с 14 лет ебу, и жизнью живой нормальной, а не кнопки давлю и наруту смотрю как некоторые...
>>151254611Т.е. давить кнопки и ебать баб - это взаимоисключающие вещи? У меня для тебя плохие новости (ты сейчас кнопки давишь).
>>151254611За Наруто и двор стреляю в упор.
>>151254668>Т.е. давить кнопкиВыпасть на дурачка решил? Очевидно, что он про программирование, социофоб ебучий.
Хули вы спорите? Вот, батя поясняет:https://www.youtube.com/watch?v=DDZxjGe7FEg
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к, вполне мог где обосраться т.к. дно в математиках
>>151250704Да, поскидывай еще подобных проблем олимпиадных
>>151237656То есть разные числа7 2 - 7^22 7 - 2^7
>>151256141По сути 7 2 - входные данные, которые из себя представляют 7^2.
>>151236246 (OP)Раз тут речь зашла про программирование, то подскажите как в mathcad в условии цикла while поставить логическое И? Я пытался поставить &, но вместо этого в mathcad вылезает шаблон интеграла
