Этого треда уже нет.
Это копия, сохраненная 9 ноября 2014 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Это копия, сохраненная 9 ноября 2014 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
159 Кб, 792x819
гнидо в детстве заболел страшной неизлечимой болезнью - динамико-дриснёй головного мозга
заболевший человек теряет способность к визуальному опознаванию окружающих объектов и вынужден полагаться на чтение бирок с их названиями
в комнате гнидо к каждому предмету была приклеена бирка с его названием, пока сегодня его мать-наркоманка не сорвала все бирки, не перепутала в них буквы и не склеила их в одну длинную строку
теперь гнидо несчастлив, он совершенно заблудился в собственной комнате
поможем ему восстановить порядок!
на вход:
первая строка - предметы в комнате гнидо
вторая строка - склеенные вместе названия предметов с перепутанными в них буквами
вывести:
в первой строке - разделённую на части вторую строку ввода - список анаграмм названий предметов в комнате гнидо
во второй строке - вывести названия предметов так, чтобы каждый предмет был красивенько под соответствующей анаграммой из первой строки вывода
гнидо очень хочет найти дверь чтобы выйти в туалет; если ваша программа не уложится в 5 секунд - гнидо обосрётся
решения на джява/сцяла/кобол/с# должны сопровождаться детальными отчётами и документацией
решения на с++ должны вычислять ответ на этапе компиляции
http://ideone.com/6iVyd2
заболевший человек теряет способность к визуальному опознаванию окружающих объектов и вынужден полагаться на чтение бирок с их названиями
в комнате гнидо к каждому предмету была приклеена бирка с его названием, пока сегодня его мать-наркоманка не сорвала все бирки, не перепутала в них буквы и не склеила их в одну длинную строку
теперь гнидо несчастлив, он совершенно заблудился в собственной комнате
поможем ему восстановить порядок!
на вход:
первая строка - предметы в комнате гнидо
вторая строка - склеенные вместе названия предметов с перепутанными в них буквами
вывести:
в первой строке - разделённую на части вторую строку ввода - список анаграмм названий предметов в комнате гнидо
во второй строке - вывести названия предметов так, чтобы каждый предмет был красивенько под соответствующей анаграммой из первой строки вывода
гнидо очень хочет найти дверь чтобы выйти в туалет; если ваша программа не уложится в 5 секунд - гнидо обосрётся
решения на джява/сцяла/кобол/с# должны сопровождаться детальными отчётами и документацией
решения на с++ должны вычислять ответ на этапе компиляции
http://ideone.com/6iVyd2
>решения на с++ должны вычислять ответ на этапе компиляции
>работа производится с тем, что подается в stdin
ясно
>>392648
Привет хаски-кун, опять ленивыми списками балуешься?
Вот тебе тестик, оптимизируй:
http://ideone.com/VeMSvT
Привет хаски-кун, опять ленивыми списками балуешься?
Вот тебе тестик, оптимизируй:
http://ideone.com/VeMSvT
22 Кб, 559x176
алсо, что за ашот у тебя на оппике?
>>392691
Что это за хуйня? Это обычный zip или чем-то отличается? Нахуй было добавлять это уродливое и неэстетичное With на конце?
>zipWith
Что это за хуйня? Это обычный zip или чем-то отличается? Нахуй было добавлять это уродливое и неэстетичное With на конце?
>>392695
http://www.haskell.org/hoogle/?hoogle=zipWith
zipWith generalises zip by zipping with the function given as the first argument, instead of a tupling function. For example, zipWith (+) is applied to two lists to produce the list of corresponding sums.
http://www.haskell.org/hoogle/?hoogle=zipWith
zipWith generalises zip by zipping with the function given as the first argument, instead of a tupling function. For example, zipWith (+) is applied to two lists to produce the list of corresponding sums.
11 Кб, 250x187
>>392850
Извените я больше не буду
Извените я больше не буду
>>392695
zip = zipWith (,)
zip = zipWith (,)
>>393406
Что же ты наделал?! Гнидо обосрётся, увидев твой код.
Что же ты наделал?! Гнидо обосрётся, увидев твой код.
>>393485
в первоначальной задаче ничего такого не было
>слова с одинаковым набором букв
>слова, являющиеся частями других слов
в первоначальной задаче ничего такого не было
>>393501
Ты имеешь в виду, что в тесте такого не было. Но даже первое решение Ашота(хаски-куна) все эти случаи учитывало.
Ты имеешь в виду, что в тесте такого не было. Но даже первое решение Ашота(хаски-куна) все эти случаи учитывало.
>>393474
Нечитабельная императивная лапша а-ля Си.
Нечитабельная императивная лапша а-ля Си.
http://ideone.com/F2bzB9
Rubygovno.
Rubygovno.
>>393485
У тебя ввод неправильный. Cначала перемешиваешь буквы, а потом склеиваешь.
>склеенные вместе названия предметов с перепутанными в них буквами
У тебя ввод неправильный. Cначала перемешиваешь буквы, а потом склеиваешь.
>>393512
Тебе ссылку на учебник по русскому языку дать? Или какое слово в процитированном предложении ты не понимаешь?
>da ty chto
Тебе ссылку на учебник по русскому языку дать? Или какое слово в процитированном предложении ты не понимаешь?
>>393515
Алсо, без этого условия задача не имеет смысла, потому что тогда можно просто взять готовое слово и пикать из перепутанного подходящие буквы. Линейная сложность - элементарное решение.
Алсо, без этого условия задача не имеет смысла, потому что тогда можно просто взять готовое слово и пикать из перепутанного подходящие буквы. Линейная сложность - элементарное решение.
50 Кб, 460x300
она срывала бирки в каком-то порядке
необязательно в таком же как во входных данных
необязательно в таком же как во входных данных
>>393516
где ты линейную сложность увидел, ткни пальцем?
где ты линейную сложность увидел, ткни пальцем?
175 Кб, 791x815
>>393050
незна где запустить http://pastebin.com/sNfFthbD
работает так себе
видимо твои тесты неинтересны моим программам и они ленятся
сам-то вбросишь кроме тестов чо?
>>393406
>>393474
wrong answer для:
abab ab ba
ababaabb
>>393506
медленновато:
http://ideone.com/p4qIj8
;D
незна где запустить http://pastebin.com/sNfFthbD
работает так себе
видимо твои тесты неинтересны моим программам и они ленятся
сам-то вбросишь кроме тестов чо?
>>393406
>>393474
wrong answer для:
abab ab ba
ababaabb
>>393506
медленновато:
http://ideone.com/p4qIj8
> veshi.permutation.each do
;D
Ещё одно решение "в лоб" на Scala: http://ideone.com/7IKaKq
А теперь немного кукаретики:
1. Глядите, как я хитро наебал систему и заюзал красно-чёрные деревья для log-удалений вместо линейных, от которых соснул хаскель
2. Само решение тупое и отличается от полного перебора только отсечением неподходящих префиксов остатка решения
3. По идее, единственный класс случаев, от которых здесь нужен бектрекинг, связан именно с парами слов, в которых множество букв одного является подмножеством букв второго. Наверное, можно как-то оптимизировать это всё, включив цепочки таких слов в некие группы и делая бранчинг только на членах одной группы, слово-"представитель" которой с точностью до перестановок букв является префиксом остатка анаграмной строки.
А теперь немного кукаретики:
1. Глядите, как я хитро наебал систему и заюзал красно-чёрные деревья для log-удалений вместо линейных, от которых соснул хаскель
2. Само решение тупое и отличается от полного перебора только отсечением неподходящих префиксов остатка решения
3. По идее, единственный класс случаев, от которых здесь нужен бектрекинг, связан именно с парами слов, в которых множество букв одного является подмножеством букв второго. Наверное, можно как-то оптимизировать это всё, включив цепочки таких слов в некие группы и делая бранчинг только на членах одной группы, слово-"представитель" которой с точностью до перестановок букв является префиксом остатка анаграмной строки.
А я вдруг понял суть динамических петухов. Она заключается в жадности. Кроме алгоритмов, жадность эта наиболее ощутимо распространяется на их отношение ко времени. Свободное время своё они зажмочивают на изучение настоящих языков программирования, а рабочее - на написание качественных решений. Последним они предпочитают быстрый и грязный быдлокод и последующее впаривание оного несведующему заказчику. И это только частный случай. В других областях человеческой деятельности они будут называться как-нибудь иначе, но суть везде одна и та же - присосаться к самым лакомым кусочкам, минимально напрягаясь и создавая иллюзию полезного действия. Динамический петух - это самый страшный, единственный паразит, который без труда маскируется под партнёра, коллегу, или даже друга.
>>393584
Как что-то плохое.
>присосаться к самым лакомым кусочкам, минимально напрягаясь и создавая иллюзию полезного действия
Как что-то плохое.
http://ideone.com/e0qDMc
Блядский сайт, никак не обновит древнюю версию пифона…
http://pastebin.com/zwQGfJkn
Блядский сайт, никак не обновит древнюю версию пифона…
http://pastebin.com/zwQGfJkn
>>393648
пыхтон вынырнул из 1го колодца, но утонул во втором
http://ideone.com/Dmj5VA
вечером еще попытаюсь утопить скалагосподина.
пыхтон вынырнул из 1го колодца, но утонул во втором
http://ideone.com/Dmj5VA
вечером еще попытаюсь утопить скалагосподина.
>>393655
тебе не приходило в голову, что слово может быть больше чем из 2 подслов?
тебе не приходило в голову, что слово может быть больше чем из 2 подслов?
А скажите-ка мне, как вы отличаете "ab" (анаграмма "ab") от "ab "(анаграмма "ba"). Сдается мне, что задним числом. У того же ОП, если порядок анаграмм в строке поменять, всё ломается.
>>393813
Я круто сам себя наебал. Почему-то я решил, что для не-очень-хорошего, но корректного Ordering для TreeSet достаточно будет указать такую _<_, двойной зажим которой !(a < b) & !(b < a) будет эквивалентен a = b, но это оказалось совсем не так:
https://github.com/scala/scala/blob/v2.11.2/src/library/scala/math/Ordering.scala#L200
С моим _!=_ compare, спецификация которого утверждает, что он возвращает 0 при равенстве, -1 при меньше, 1 при больше, становится некорректен: не существует сюрьективной функции из {true,false} в {-1,0,1}, потому как минимум 1 элемент кодомена никогда не будет возвращаться. Например, если это 1, значит, в соответствии со спецификацией compare,
для любых a и b, compare(a,b) != 1 <-> !(a > b) <-> a <= b,
Конкретизируя a и b для любых фиксированных (x, y), а потом (y, x): x <= y & x >= y
Откуда следует, что для любых a и b, a = b.
Понятно, что Ordering, допускающий такие выводы по equational reasoning, не сулит ничего хорошего.
Зато я придумал, как всю эту хуету починить и очень существенно оптимизировать, попозже напишу.
Я круто сам себя наебал. Почему-то я решил, что для не-очень-хорошего, но корректного Ordering для TreeSet достаточно будет указать такую _<_, двойной зажим которой !(a < b) & !(b < a) будет эквивалентен a = b, но это оказалось совсем не так:
https://github.com/scala/scala/blob/v2.11.2/src/library/scala/math/Ordering.scala#L200
С моим _!=_ compare, спецификация которого утверждает, что он возвращает 0 при равенстве, -1 при меньше, 1 при больше, становится некорректен: не существует сюрьективной функции из {true,false} в {-1,0,1}, потому как минимум 1 элемент кодомена никогда не будет возвращаться. Например, если это 1, значит, в соответствии со спецификацией compare,
для любых a и b, compare(a,b) != 1 <-> !(a > b) <-> a <= b,
Конкретизируя a и b для любых фиксированных (x, y), а потом (y, x): x <= y & x >= y
Откуда следует, что для любых a и b, a = b.
Понятно, что Ordering, допускающий такие выводы по equational reasoning, не сулит ничего хорошего.
Зато я придумал, как всю эту хуету починить и очень существенно оптимизировать, попозже напишу.
>>393823
Не могу воспроизвести, пока будем считать, что я ошибся.
Не могу воспроизвести, пока будем считать, что я ошибся.
>>393893
Вроде программист, а мысли свои излагать не умеешь. Проще было по строчке кода понять суть проблемы, чем по твоей простыне.
Вроде программист, а мысли свои излагать не умеешь. Проще было по строчке кода понять суть проблемы, чем по твоей простыне.
>>394351
Ньюфажек.
Ньюфажек.
ну чо
>>394712
Всё что на jvm ведет себя на ideone аналогично.
Всё что на jvm ведет себя на ideone аналогично.
>>394025
Я писал для людей, понимающих, что такое Ord(ering), красно-чёрные деревья, сюръекция, equational reasoning, и могущих в квантификаторы и элементарные математические рассуждения типа "!(a < b) & !(b < a) <-> a = b", и считаю, что очень хорошо всё объяснил. Даже им нельзя изложить проблему одной строчкой кода, не то что всем остальным.
>>393563
Сделал, но моя оптимизация оказалась не такая уж существенная: http://ideone.com/NLxEFs
Я писал для людей, понимающих, что такое Ord(ering), красно-чёрные деревья, сюръекция, equational reasoning, и могущих в квантификаторы и элементарные математические рассуждения типа "!(a < b) & !(b < a) <-> a = b", и считаю, что очень хорошо всё объяснил. Даже им нельзя изложить проблему одной строчкой кода, не то что всем остальным.
>>393563
> я придумал, как всю эту хуету починить и очень существенно оптимизировать, попозже напишу.
Сделал, но моя оптимизация оказалась не такая уж существенная: http://ideone.com/NLxEFs
Да уж, yield для таких переборных задач немного сокращает и упрощает код. Последнее решение на scala почти эквивалентно последнему решению на питоне, но немножко сокращает пространство перебора, запихивая в Bag (питоновский Counted - что-то подобное, как я понял) отсортированные строки, а порядок восстанавливая потом.
Немножко разобрался со скала-компрехеншонами и порефакторил: http://ideone.com/8AKTBi
>>394814
Ох, вы только посмотрите на этого умника.
Писал ты для себя, чтобы потешить своё самолюбие. Если бы ты действительно хотел донести суть своей пустяковой проблемы до остальных будто она кому-то интересна, то изложил бы её в двух словах.
Ох, вы только посмотрите на этого умника.
>Я писал для людей, понимающих
Писал ты для себя, чтобы потешить своё самолюбие. Если бы ты действительно хотел донести суть своей пустяковой проблемы до остальных будто она кому-то интересна, то изложил бы её в двух словах.
>>394936
Суть проблемы: некорректный инстанс тайпкласса Ordering. Но это само-по-себе неинтересно. Забавно то, как из при него можно вывести, что любые два слова равны. Это какбы поучительный пример, что не надо грозить отношениям строгого порядка.
Суть проблемы: некорректный инстанс тайпкласса Ordering. Но это само-по-себе неинтересно. Забавно то, как из при него можно вывести, что любые два слова равны. Это какбы поучительный пример, что не надо грозить отношениям строгого порядка.
>>394942
Вывод уровня /pr/: чудеса коммутативности.
Оленю понятно, что fromLessThan требует некоммутативную операцию, на что намекает LessThan
>Забавно то, как из при него можно вывести
Вывод уровня /pr/: чудеса коммутативности.
Оленю понятно, что fromLessThan требует некоммутативную операцию, на что намекает LessThan
>>394960
То, что привычные less-than некоммутативны - это, конечно, очевидно, а вот то, что КЧ-дерево станет работать плохо с немножко неправильным Ordering - это ещё не факт. Я же объяснил изначальную интуицию (думал, что от Ordering требуется только сохранять равенства). Более того, с таким поломанным Ordering оно даже работает в нескольких примерах из треда.
То, что привычные less-than некоммутативны - это, конечно, очевидно, а вот то, что КЧ-дерево станет работать плохо с немножко неправильным Ordering - это ещё не факт. Я же объяснил изначальную интуицию (думал, что от Ordering требуется только сохранять равенства). Более того, с таким поломанным Ordering оно даже работает в нескольких примерах из треда.
Я думал, что это будет примерно эквивалентно тому, как если бы я занумеровал все свои слова последовательными int и вставлял друг за дружкой - не самый лучший сценарий для RBT, но оно ведь балансируется.
28 Кб, 225x225
>>394882
да твоё решение всех ушатало (если наш тестер не найдёт ошибку опять)
так что заползай на подиум, тебе есть чем гордиться
да твоё решение всех ушатало (если наш тестер не найдёт ошибку опять)
так что заползай на подиум, тебе есть чем гордиться
>>394981
За весь тред не было ни одного работающего решения, кроме жабоговна?! Нипарядок.
За весь тред не было ни одного работающего решения, кроме жабоговна?! Нипарядок.
Перлобог в треде! Все обратно под шконку.
http://ideone.com/mXXYrc
http://ideone.com/mXXYrc
>>395060
Нет, ты!
Что у тебя с выводом? Жульничаешь небось?
И не лень тебе на этом недоязычке писать было?
Нет, ты!
>abababababababababababaabb
>abab ab ab ab ab ab ab ab ab ab ab ab
>abab ab ab ab ab ab ab ab ab ab ab ab
Что у тебя с выводом? Жульничаешь небось?
И не лень тебе на этом недоязычке писать было?
>>395050
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.004s
user 0m0.001s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.003s
user 0m0.001s
sys 0m0.000s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.005s
user 0m0.003s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.001s
user ~/lua $
Кратко: перл соснул
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.004s
user 0m0.001s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.003s
user 0m0.001s
sys 0m0.000s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.005s
user 0m0.003s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.001s
user ~/lua $
Кратко: перл соснул
>>395050
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.004s
user 0m0.001s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.003s
user 0m0.001s
sys 0m0.000s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.005s
user 0m0.003s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.001s
user ~/lua $
Кратко: перл соснул
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.004s
user 0m0.001s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.003s
user 0m0.001s
sys 0m0.000s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.000s
user ~/lua $ time cat data.dat | perl perl.perl
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
real 0m0.005s
user 0m0.003s
sys 0m0.001s
user ~/lua $ time cat data.dat | luajit olimpics.lua
abab ab ab ab ab ab ab ab ab ab ab ab
abab ab ab ab ab ab ab ab ab ab ab ab
real 0m0.002s
user 0m0.000s
sys 0m0.001s
user ~/lua $
Кратко: перл соснул
>>395067
Щас починю
Щас починю
>>395079
Мне похуй какой у тебя вывод.
Задача допускает много решений.
Из того как строка склеена нельзя сделать вывод о том, как она была разрезана.
На малых длинах строк и их количествах мое решение быстрее. Давай большие данные ( типа цепочки днк) и будем оптимизировать, или создавай новую олимпиадку с переписаным условием.
Ты соснул уже второй раз за тред.
Мне похуй какой у тебя вывод.
Задача допускает много решений.
Из того как строка склеена нельзя сделать вывод о том, как она была разрезана.
На малых длинах строк и их количествах мое решение быстрее. Давай большие данные ( типа цепочки днк) и будем оптимизировать, или создавай новую олимпиадку с переписаным условием.
Ты соснул уже второй раз за тред.
>>395090
Хотя на маленьких алфавитах тоже мое решение быстрее
Хотя на маленьких алфавитах тоже мое решение быстрее
>>395090
Условия внимательней прочитай, прежде чем петушиться.
Условия внимательней прочитай, прежде чем петушиться.
>вывести:
>в первой строке - разделённую на части вторую строку ввода - список анаграмм названий предметов в комнате гнидо
>во второй строке - вывести названия предметов так, чтобы каждый предмет был красивенько под соответствующей анаграммой из первой строки вывода
>>395094
Хуй соси мудила
Ты не можешь определить в суфиксе vatj откуда у тебя t из стула стола или кровати.
Впрочем просто продолжай посасывать
Хуй соси мудила
Ты не можешь определить в суфиксе vatj откуда у тебя t из стула стола или кровати.
Впрочем просто продолжай посасывать
>>395098
Лол, в этом и есть суть задачи.
>Ты не можешь определить в суфиксе vatj откуда у тебя t из стула стола или кровати.
Лол, в этом и есть суть задачи.
>>395101
;D
;D
> суть задачи
В условии.
В нем не сказано: мамаша нарезает на крупные кусочки.
В нем не сказано: вывести в порядке следования первых букв анаграмм
В нем не сказано: разделить строку на анаграммы заданных слов так, чтобы количество частей на которые нужно разрещать эти слова было минимальным.
Все что ты "подразумеваешь" нужно описывать словами.
>>395100
давай ты продемонстрируешь скиллы
Есть три слова:
stol stul krovatj
Я разрезал на 14 частей, склеил, получилось
stolstulkrovatj
Из какого слова первая t?
давай ты продемонстрируешь скиллы
Есть три слова:
stol stul krovatj
Я разрезал на 14 частей, склеил, получилось
stolstulkrovatj
Из какого слова первая t?
>>395107
ты:
- либо тралишь
- либо не понял условие
в первом случае:
во втором: перечитай оп-пост и посмотри примеры
ты:
- либо тралишь
- либо не понял условие
в первом случае:
во втором: перечитай оп-пост и посмотри примеры
>>395104
Ты уже почти понял. Молодец.
Осталось только его прочитать и немножечко напрячь мозги. Самую малость.
Надеюсь, дальше ты уже разберешься без моей помощи.
>> суть задачи
>В условии.
Ты уже почти понял. Молодец.
Осталось только его прочитать и немножечко напрячь мозги. Самую малость.
Надеюсь, дальше ты уже разберешься без моей помощи.
>>395110
Я просто решил задачу другим способом, который показывает двусмысленность условия.
а, т.е. олимпиадка в духе: скопируйте мое решение? ну ты и комик! Такой выдумщик!
Я просто решил задачу другим способом, который показывает двусмысленность условия.
> посмотри примеры
а, т.е. олимпиадка в духе: скопируйте мое решение? ну ты и комик! Такой выдумщик!
>>395111
Тебе бы мозги изредка напрягать.
Тебе бы мозги изредка напрягать.
>>395115
Лол
Я кстати могу переписать так, чтобы ответ был еще другой, почти совпадал с твоим. Не считаю нужным конечно, но если очень попросишь...
Лол
Я кстати могу переписать так, чтобы ответ был еще другой, почти совпадал с твоим. Не считаю нужным конечно, но если очень попросишь...
>>395095
Все сводится к проверке на наличие сортированной анаграммы из входной строки в таблице anagram.
Все сводится к проверке на наличие сортированной анаграммы из входной строки в таблице anagram.
>>395118
Изи мод
http://ideone.com/FagssV
В исходной строке анаграмма не такая.
Но на самом деле мы оба знаем, что даже этого нет в условии
Изи мод
http://ideone.com/FagssV
В исходной строке анаграмма не такая.
Но на самом деле мы оба знаем, что даже этого нет в условии
>>395124
ну пж
ну пж
>>394981
У меня просто багира, что решение на питоне короче, и что там в стандартной библиотеке есть Bag, а в Scala нету, хотя в оной самая выдроченная стдлиба коллекций за всю историю мейнстримных ЯП.
У меня просто багира, что решение на питоне короче, и что там в стандартной библиотеке есть Bag, а в Scala нету, хотя в оной самая выдроченная стдлиба коллекций за всю историю мейнстримных ЯП.
Я сначала думал, что последнее питоновое решение хуйня какая-то, а потом вчитался и понял, что там то же самое. В целом, короче в первую очередь за счёт yield на уровне методов - но это сохраняет всего пару строчек самого кода поиска - и, существеннее, за счёт ввода-вывода - но там какое-то адовое динамическое петушение:
> a, b = input(), input()
> print("\n".join(map(" ".join, zip(next(yoba(a, b))))))
>>395116
Из слова stol.
Получение исходной строки:
Берем каждое слово, перепутываем в них буквы.
Получившиеся слова из перепутанных букв конкатенируем в произвольном порядке.
Как бы косячно не было написано условие, имеется в виду именно это.
Из слова stol.
Получение исходной строки:
Берем каждое слово, перепутываем в них буквы.
Получившиеся слова из перепутанных букв конкатенируем в произвольном порядке.
Как бы косячно не было написано условие, имеется в виду именно это.
32 Кб, 405x423
>>395146
эх
смори, этот ввод: http://ideone.com/sSNnPk
повторим 5 раз: http://ideone.com/FATOlq
однако: http://ideone.com/tz78Om
эх
смори, этот ввод: http://ideone.com/sSNnPk
повторим 5 раз: http://ideone.com/FATOlq
однако: http://ideone.com/tz78Om
да норм условие чо вы это самое))
>>395155
Оказалось, я в одном месте проебал ленивость: http://ideone.com/YzZhw3
На примере из >>393655 всё-равно взрывается.
Оказалось, я в одном месте проебал ленивость: http://ideone.com/YzZhw3
На примере из >>393655 всё-равно взрывается.
Опять np-complete подсунули? Хрень какая.
Я вот понимаю, были бы задачки с очевидным алгоритмом O(n^4), с хитровыебанным O(n^3) с потенциальным снижением до O(n^(8/3)) или с применением какого-нибудь ада из глубин топологии до O(nnln(n)). Это было бы интересно.
А тут всё превращается костыльную задрочку под конкретный инпут (может ещё не превратилось, но к этому идет).
Щас вот пойдут костыли, которые специально обрабатывают одинаковые слова.
Я вот понимаю, были бы задачки с очевидным алгоритмом O(n^4), с хитровыебанным O(n^3) с потенциальным снижением до O(n^(8/3)) или с применением какого-нибудь ада из глубин топологии до O(nnln(n)). Это было бы интересно.
А тут всё превращается костыльную задрочку под конкретный инпут (может ещё не превратилось, но к этому идет).
Щас вот пойдут костыли, которые специально обрабатывают одинаковые слова.
>>395165
Сможешь ли ты доказать, что она NP-полная?
Сможешь ли ты доказать, что она NP-полная?
количество дней: 7
количество постов: 107
количество решений: 8
количество верных решений: 0
количество постов: 107
количество решений: 8
количество верных решений: 0
>>395165
ты че пидор, какая нп-полнота? для этой задачки есть решение О(н), причем н - число слов.
ты че пидор, какая нп-полнота? для этой задачки есть решение О(н), причем н - число слов.
>>395209
Лл, даж буквы в словах не надо читать? Охуительные истории, иди нахуй.
Лл, даж буквы в словах не надо читать? Охуительные истории, иди нахуй.
>>395209
Лол ок. Давай свой алгоритм, я на тебя контрпримером поссу.
Лол ок. Давай свой алгоритм, я на тебя контрпримером поссу.
>>395183
Тогда ты молодец
Тогда ты молодец
Пример двусмысленности уже исправленного условия:
http://ideone.com/FtzGKB
http://ideone.com/FtzGKB
>>395241
Это где в условии такое написано? Ты какую-то свою задачку придумал и хочешь, чтобы условие её описывало?
Это где в условии такое написано? Ты какую-то свою задачку придумал и хочешь, чтобы условие её описывало?
>>395241
Анаграмма - это любое слово, составленное из букв данного. Любое слово является само-себе-анаграммой.
Анаграмма - это любое слово, составленное из букв данного. Любое слово является само-себе-анаграммой.
>>395230
Ну какбе да, ответов может быть несколько. Это вообще нормально для задач. Требуется найти хотя бы одно решение.
Ну какбе да, ответов может быть несколько. Это вообще нормально для задач. Требуется найти хотя бы одно решение.
Эта задачка может быть тоньше, чем кажется. Вероятно, ОП в конце нас затиранит каким-то хитрым решением со строкоиндексирующей структурой.
>>395251
Один хрен она просто не решается.
Могу вот ещё алгоритм предложить.
Для каждого символа входной строки делаем список всех анаграмм.
Одна потенциальная анаграмма - вершина графа.
Это O(nmk), где n - слов, m - длина строки, k - длина самого длинного слова.
Ребро (ориентированное) — от анаграммы A длины z, начинающейся с символа i, до всех анаграмм B, начинающихся с символа i+z.
Можно произвести элиминацию вершин, из которых нет ребер кроме вершин, которые по идее должны указывать на конец строки.
Дальше каждому слову (точнее классу эквивалентности по отношению "является анаграммой") можно присвоить простое число в виде веса.
Нужный нам вес - произведение весов всех слов.
Эти же веса навешиваем на вершины.
Дело за малым — найти путь заданного веса в графе. Задача несколько упрощается из-за гарантированного отсутствия циклов. Что не отменяет её np-полноты.
Есть ощущение, что это не будет быстрее поиска в глубину, который тут в каждом решении. Хотя на многих примерах элиминация позволит очень сильно упростить граф. Например, на пресловутом ab ab ... abab и abab...aabb
Один хрен она просто не решается.
Могу вот ещё алгоритм предложить.
Для каждого символа входной строки делаем список всех анаграмм.
Одна потенциальная анаграмма - вершина графа.
Это O(nmk), где n - слов, m - длина строки, k - длина самого длинного слова.
Ребро (ориентированное) — от анаграммы A длины z, начинающейся с символа i, до всех анаграмм B, начинающихся с символа i+z.
Можно произвести элиминацию вершин, из которых нет ребер кроме вершин, которые по идее должны указывать на конец строки.
Дальше каждому слову (точнее классу эквивалентности по отношению "является анаграммой") можно присвоить простое число в виде веса.
Нужный нам вес - произведение весов всех слов.
Эти же веса навешиваем на вершины.
Дело за малым — найти путь заданного веса в графе. Задача несколько упрощается из-за гарантированного отсутствия циклов. Что не отменяет её np-полноты.
Есть ощущение, что это не будет быстрее поиска в глубину, который тут в каждом решении. Хотя на многих примерах элиминация позволит очень сильно упростить граф. Например, на пресловутом ab ab ... abab и abab...aabb
Божественная джава
http://ideone.com/MNaoZF
http://ideone.com/MNaoZF
>>395256
Написано красиво, только не очень понятно.
Для этого же нужно пройтись по всем factors строки (по всем подстрокам s[i,j], 0 <= i < j < len(s)), правильно?
Написано красиво, только не очень понятно.
> Ребро (ориентированное) — от анаграммы A длины z, начинающейся с символа i, до всех анаграмм B, начинающихся с символа i+z.
Для этого же нужно пройтись по всем factors строки (по всем подстрокам s[i,j], 0 <= i < j < len(s)), правильно?
А, хотя нет. Наверное имелось в виду, что мы берём s[0], смотрим анаграммы ans(s[0]) с ним, каждую x делаем вершиной и соединяем рёбрами со всеми анаграммами ans[s[len(x)]] и т.д.
>>395270
У тебя поиск в ширину. Гарантированно говено работает на всех типах входных данных.
У тебя поиск в ширину. Гарантированно говено работает на всех типах входных данных.
>>395302
Там не печатаемый символ какой-то очевидно.
http://ideone.com/BBxbkD
все равно соснул. Да. нужно поиск писать.
Там не печатаемый символ какой-то очевидно.
http://ideone.com/BBxbkD
все равно соснул. Да. нужно поиск писать.
>>395304
Я не просто так писал, что задача сложная.
Сначала перебрал в голове все возможные жадные алгоритмы и придумал по контрпримеру на каждый.
Всё никак не могу найти нп-полную задачу, которую можно к этой свести. Однако полиномиальный алгоритм тоже не придумывается.
Я не просто так писал, что задача сложная.
Сначала перебрал в голове все возможные жадные алгоритмы и придумал по контрпримеру на каждый.
Всё никак не могу найти нп-полную задачу, которую можно к этой свести. Однако полиномиальный алгоритм тоже не придумывается.
Продолжаем разговор.
http://ideone.com/zb5y0A
http://ideone.com/zb5y0A
>>395380
К раскладыванию говна всякого можно свести.
К раскладыванию говна всякого можно свести.
217 Кб, 1387x1203
пока что нет ниодного решения работающего правильно и не отсасывающего при смешных входных данных
многообещающей всего выглядели:
хитрожопный перебор на сцяла с какими-то там деревьями - http://ideone.com/FATOlq
обфусцированный жадник на перл - http://ideone.com/fkpD5T
алсо похоже что некоторые участники пытаются прийти к эффективному решению изменяя свой код случайным образом и постя его сюда
ждём
многообещающей всего выглядели:
хитрожопный перебор на сцяла с какими-то там деревьями - http://ideone.com/FATOlq
обфусцированный жадник на перл - http://ideone.com/fkpD5T
алсо похоже что некоторые участники пытаются прийти к эффективному решению изменяя свой код случайным образом и постя его сюда
ждём
>>395395
100 постов на страхе, боли и отчаянье. Нашел чем гордиться. Ты еще политический сравню тут разведи, сразу 300 постов будет.
100 постов на страхе, боли и отчаянье. Нашел чем гордиться. Ты еще политический сравню тут разведи, сразу 300 постов будет.
>>395399
И все равно злая олимпиадка.
И все равно злая олимпиадка.
>>395404
да
да
пока что нет ниодного варианта условия непротиворечивого и сформулированного литературным языком
алсо похоже что оп пытается прийти к победе путем изменения требований случайным образом, бампая тред с сажей и постя сюда коментарий "неправильно"
ждём
алсо похоже что оп пытается прийти к победе путем изменения требований случайным образом, бампая тред с сажей и постя сюда коментарий "неправильно"
ждём
>>395409
немоизация
немоизация
>>395423
Функция поиска принимает список слов и строку в которой нужно искать. Возвращает список пар слово-анаграмма и маркер успеха. Работает рекурсивно.
Для конца строки она постоянно вызывается с одинми и теми же аргументами.
Ее и мемоизировал.
Еще сортировку строки, но это так, ерунда.
Функция поиска принимает список слов и строку в которой нужно искать. Возвращает список пар слово-анаграмма и маркер успеха. Работает рекурсивно.
Для конца строки она постоянно вызывается с одинми и теми же аргументами.
Ее и мемоизировал.
Еще сортировку строки, но это так, ерунда.
>>395422
Поторопился ты с награждением:
$ cat data{,2}.txt | lua /tmp/pr.lua
huy tam
http://pastebin.com/pLPBdGjC
Поторопился ты с награждением:
$ cat data{,2}.txt | lua /tmp/pr.lua
huy tam
http://pastebin.com/pLPBdGjC
Решение на скале висело на этих вхоных данных полчаса безрезультатно.
193 Кб, 1366x2048
щас ждём линейное решение на конечных автоматах
>>395467
это один из участников
это один из участников
>>395459
Погоди-погоди... Ты что хочешь сказать, что вот это на пикче - это Носатая? Это наша Даша в такое превратилась? Деад_Телеграфист? Скажи что это не так, прошу.
Погоди-погоди... Ты что хочешь сказать, что вот это на пикче - это Носатая? Это наша Даша в такое превратилась? Деад_Телеграфист? Скажи что это не так, прошу.
>>395459
А по делу никто не написал.
Там получается НКА, который надо детерминировать. Такой бздыщ будет, что мама не горюй. При этом сам по себе НКА тоже будет гигантский. Хуй с ней, с памятью, ты его строить полгода будешь.
А по делу никто не написал.
Там получается НКА, который надо детерминировать. Такой бздыщ будет, что мама не горюй. При этом сам по себе НКА тоже будет гигантский. Хуй с ней, с памятью, ты его строить полгода будешь.
366 Кб, 1365x2048
>>395483
значит надо какой нибудь хитрожопый автомат
вот есть http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm (корасик азхаахах)))
надо придумать что-то подобное: anagram-matching-automaton
значит надо какой нибудь хитрожопый автомат
вот есть http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm (корасик азхаахах)))
надо придумать что-то подобное: anagram-matching-automaton
509 Кб, 1365x2048
ой простите, господин полицейский
вот, зацензурил
вот, зацензурил
>>395485
А это не хитрожопый автомат, это обычный автомат для поиска подстроки в строке.
Во-первых, его самого сложно строить. Он хорошо работает, когда тебе надо искать недлинную строку в охуительной длины тексте, потому что сложность поиска сильно зависит от длины слова, а от текста только линейно и эти сложности складываются, а не перемножаются, как в других алгоритмах.
Здесь же тебе нужно проверить строку на соответствие. То есть длина пути в автомате будет равна исходной строке.
Более того, этот автомат ещё не так сложно построить для обычно строки, здесь же его надо построить для всевозможных перестановок кусков строки, при этом внутри кусков тоже должны быть обработаны всевозможные перестановки.
А это не хитрожопый автомат, это обычный автомат для поиска подстроки в строке.
Во-первых, его самого сложно строить. Он хорошо работает, когда тебе надо искать недлинную строку в охуительной длины тексте, потому что сложность поиска сильно зависит от длины слова, а от текста только линейно и эти сложности складываются, а не перемножаются, как в других алгоритмах.
Здесь же тебе нужно проверить строку на соответствие. То есть длина пути в автомате будет равна исходной строке.
Более того, этот автомат ещё не так сложно построить для обычно строки, здесь же его надо построить для всевозможных перестановок кусков строки, при этом внутри кусков тоже должны быть обработаны всевозможные перестановки.
>>395490
[мечты]
хочу автомат
он будет хитрожопо склеен из anagram-matching-automatonов
мы бы скармливали ему вторую строку ввода по одной букве
и он бы быстро разрешал коллизии, когда несколько слов из словаря являются анаграммо-префиксами хвоста бирки
с откатами он был бы похож на автомат ахо-карасика
при этом он не будет слишком большим и строится за поли время
[/мечты]
[мечты]
хочу автомат
он будет хитрожопо склеен из anagram-matching-automatonов
мы бы скармливали ему вторую строку ввода по одной букве
и он бы быстро разрешал коллизии, когда несколько слов из словаря являются анаграммо-префиксами хвоста бирки
с откатами он был бы похож на автомат ахо-карасика
при этом он не будет слишком большим и строится за поли время
[/мечты]
>>395494
Ща, замутим недетерминированную машину Тьюринга и будем все задачки щелкать как орехи.
Ща, замутим недетерминированную машину Тьюринга и будем все задачки щелкать как орехи.
>>395529
Это-то без проблем. Конечная машина Тьюринга всё равно только конечное количество ячеек может посетить. А зациклившаяся машина Тьюринга — это багованная, ей можно и исключение кинуть.
Это-то без проблем. Конечная машина Тьюринга всё равно только конечное количество ячеек может посетить. А зациклившаяся машина Тьюринга — это багованная, ей можно и исключение кинуть.
39 Кб, 600x600
>>395534
если машина зациклилась - надо сразу кидать исключение
если машина зациклилась - надо сразу кидать исключение
>>395598
Но что с ней на тех, других фотках? Она колется? У нее рак?
Кстати, "дед т-графист" здесь в спам листе, к чему бы?
Но что с ней на тех, других фотках? Она колется? У нее рак?
Кстати, "дед т-графист" здесь в спам листе, к чему бы?
>>395608
;D
;D
Интересно, достаточно ли хороша моя тян? Пойду-ка в программаче запощу, посмотрю что пацаны скажут!
>>395614
Давай. Уж мы-то оценим по достоинству.
Давай. Уж мы-то оценим по достоинству.
>>395611
Дамы украшают имиджборду
Дамы украшают имиджборду
>>395622
В том числе и хуй, который наваял на нем решение.
В том числе и хуй, который наваял на нем решение.
Тред утонул или удален.
Это копия, сохраненная 9 ноября 2014 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Это копия, сохраненная 9 ноября 2014 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.