Тогда решение такое:
Зная количество троек (n), вы знаете, сколько изначально чисел было (x):
x(x-1)(x-2) = n
Проще всего просто увеличивать x по одному, считать сколько троек должно получится из такого количества изначальных чисел и сравнивать с тем, что у вас есть.
Потом отсортируйте ваши тройки по возрастанию в лексикографическом порядке.
Вы уже точно знаете, что первая тройка - это первые 3 минимальные числа в вашем исходном массиве. Вторая тройка обязательно - 2 первых числа и четвертое. Следующая тройка - 2 первых и пятое. И так далее. Т.е. сморите на первые x-2 тройки. Там первые 2 элемента в каждой тройке - первые 2 в ответе, а оставшиеся третьи элементы - это все остальные x-2 числа в ответе.
Вот вам пример для x=5: (a,b,c,d,e)
abc, abd, abe, bcd, bce ...
Не важно, что за числа a..e - важно что они в не убывающем порядке. Тогда тройка abc - точно будет самой первой.
Это все если вам на вход подаются ВСЕ тройки. Если же не все, то можно, например, взять все уникальные элементы и, если в какой-то тройке элементы повторяются, то брать эти элементы 2, или 3 раза, если вся тройка состоит из повторений.
Proshka17, Вы делаете что-то вроде полного перебора, а тут нужно комбинаторную магию и динамическое программирование применить. Я попозже распишу подробнее. Пока, напишите ограничения в задаче. Сколько карт всего, сколько типом может быть.
Сначала напишите "в даблах", когда у вас все числа с плавающей точкой и вы можете их умножать и делить. Потом примените хитрость из условия, что считать надо по модулю. Все числа целые. Вместо деления - умножайте на обратное по модулю. Обратное, как вам уже сказал Mercury13 , ищите расширенным алгоритмом эвклида. Это стандартный прием на соревнованиях, чтобы не требовать писать длинную арифметику.
Ну сжатий есть 2 вида. С потерями и без потерь. С потерями это у вас же - отрезать 2 младших бита.
Без потерь вам уже советовали - коды хаффмана, RLE, или какой-нибудь стандартный обобщенный сжиматель, типа zlib.
Проблема в том, что если у вас цены подарков -10, -10 и -15, то, независимо от того, какую из -10 вы взяли, вы потом опять можете взять любую из двух. Согласитесь: принципиально другое поведение, чем когда все числа разные. Идея же в том, что как только вы взяли вторую -10, первую вы уже брать опять не должны. Вы в последовательности из нескольких -10 в ответе будете считать все возможные перестановки двух типов подарков. Что в этой задаче не надо.
Вот запустите на тесте x=2 y=2 z=1000 w=10.
Правильный ответ - 11 (x может быть взято от 0 до 10 раз, остальное - y). Сколько выдает ваша программа? 1024 небось?
> И вообще при числах 2 2 3 4 отработала верно.
Правильный ответ 3 (2 раза первый подарок; 2 раза второй подарок; первый+второй). Ваша же программа, если я не напутал, выдает 4.
Ничего особо революционного там нет - просто вместо DFS дополняющие пути ищутся через BFS. Но там есть интересная эвристика, которая не влияет на асимптотическую сложность, но на некоторых графах хорошо ускоряет работу алгоритма: бфс не запускается заново каждый раз, некоторая часть с предыдущего обхода переиспользуется.
Заодно там уделяется внимание, собственно, паралелизации и в описании алгоритма указано, какие операции надо делать с локами/атомиками. Думаю, это именно то, что вы ищете.
Весьма странный документ. Во первых, там утверждается, что с обходом в ширину алгоритм Куна получает n*2.5 сложность, но это уже будет алгоритм Хопкрафта-Карпа.
А главное, там параллелизация делается по данным и отсутствует какое-либо объяснение, как они этого добились. Как будто, там граф разбивается на много независимых областей. Проблема только в том, что, если граф связен, таких независимых областей вообще нет. Но у них там граф случайный и с очень маленьким количеством ребер. Т.ч. вполне возможно, что там куча мелких несвязанных между собой компонент. Это очень крайний случай (найдите паросочетание в куче мелких графов сразу). Вся идея - запустить один и тот же алгоритм Куна кучу раз параллельно.
Еще там какой-то бред про итоговую линейную сложность(?!).
В общем, качество этого документа весьма сомнительное. Обычная курсовая работа ради зачета. Пользы и новизны почти нет. Все идеи тривиальные, но расписано так, чтобы это не бросалось в глаза.
xmoonlight, Какая разница? От чисел мерсенна пользы может и не быть, это был лишь пример входных/выходных данных для вашей задачи, которые хоть и имеют математический смысл и очень простое определение, но сгенерировать практический алгоритм для них никто не умеет.
Но, вообще, смысл может быть в криптографии. Большие простые числа там нужны, а если они близки к степени 2, то можно быстро делить/брать остатки, что тоже очень часто в криптографии делается. Так что генерировать их весьма полезно. Правда, редко надо найти именно 113355-ое простое число мерсенна. Обычно достаточно найти любое простое число примерно заданного размера. А это гораздо проще задача.
xmoonlight, В контексте про Ваше утверждение "Если задачу может решить человек - машина это может делать 100%", то тут не до гита и "мне в руки". Создание сильного искусственного интеллекта - это такой шаг вперед для человечества, что никто это скрывать не стал бы. Хозяева такого открытия легко бы поработили весь мир и/или получили бы бессмертную славу.
Если вы про решение вашей задачи какой-то софтварью, то это решение, хоть и выглядит более практично чем полиномиальная интерполяция или write(42), на самом деле кардинально от них не отличается - там просто разобрано гораздо больше частных случаев и выбирается лучший. На игрушечных примерах вы можете что-то получить. На практике - далеко не факт.
Более того, ваша задача не может иметь алгоритмического решения. Это математический факт. Некоторые задачи вообще нельзя запрограммировать (Как, например, halting problem, уже приведенная выше). Другие - человечеству пока не поддались. Например, входные данные {1,2,3,4,5,6,7}, выходные {3,7,31,127,8191,131071,524287}. Даже если создатель программы рассмотрел частный случай "простые числа Мерсенна", Ни формулы, ни даже применимого на практике алгоритма вычисления их человечеству неизвестно. Полного перебора на всех компьютерах мира для входного числа 10000000 Вы будете ждать до тепловой смерти вселенной.
xmoonlight, Ё-маё. Как же жалко потраченного на вас и ваше трололо время. Жаль, что тут нельзя минусы ставить. Вам же советую, наоборот, побольше умных книжек читать. Может мозги себе вправите. Прощайте.
xmoonlight, Анализ вам вкратце: "хорошего" решения вашей задачи не существует (Если вы хотите кратчайший или имеющий практический смысл алгоритм). Хотя бы потому, что можно в виде входных данных закодировать программы, а в виде выходных хотеть ответ - завершается ли эта программа. Алгоритма реализующего это не существует. И тем более нет алгоритма, который бы его нашел.
А плохих решений вашей задачи море - можно, например, выдавать известные ответы на известные входы, а на все другие входы - выдавать 42. Даже интерполяций не надо.
eRKa , Вот только тот код не работает в некоторых случаях - если точка лежит снаружи и на той же горизонтали, что и единственная самая нижняя точка многоугольника. Т.е. горизонтальный луч касается многоугольника в вершине. В этом случае должно быть 0 или 2 пересечения, а ваш метод подсчитает ровно одно.
Это потому что вы в каждом отрезке игнорируете второй конец (в порядке обхода), а надо игнорировать только нижниее точки (или только верхние).
Mercury13, вообще не много, учитывая что алгоритм работает за линию от количества вершин+ребер в этом новом графе.
keddad, Логика построения - рассматриваем все возможные варианты. Вот вы можете как-то покататься и оказаться в вершине 42 с 1 "литра" топлива. А можете как-то по другому покататься и приехать туда с 100 литров топлива. Вот это 2 разные вершины в новом графе. Они все различные от 0 до n. У вас все состояние описывается двумя величинами: где вы и сколько у вас топлива сейчас топлива. Мы все это пространство состояний описываем с помощью этого искусственного графа. Ведь совершенно неважно, как вы раньше ездили, ведь если вы в вершине 42 с 10 литрами топлива, то вы дальше можете делать все то же самое. Поэтому и получается n * "количество вершин" вершин в новом графе. Далее мы в этом пространстве состояний ищем минимальный путь.
Даниил,
Размеры областей по площади или по количеству ячеек (сайтов) заданы?
У вас ячейки (сайты) выделены уже? В смысле есть граф соседей для ячеек? Вроде вершина-область и от нее ребра к соседним областям, с которыми данная делит границу.
Допустим, [6, 2] - это true? Правильно понимаю, что надо вернуть False, только если одно число из списка в какой-то рациональной степени будет равно другому числу?
Зная количество троек (n), вы знаете, сколько изначально чисел было (x):
x(x-1)(x-2) = n
Проще всего просто увеличивать x по одному, считать сколько троек должно получится из такого количества изначальных чисел и сравнивать с тем, что у вас есть.
Потом отсортируйте ваши тройки по возрастанию в лексикографическом порядке.
Вы уже точно знаете, что первая тройка - это первые 3 минимальные числа в вашем исходном массиве. Вторая тройка обязательно - 2 первых числа и четвертое. Следующая тройка - 2 первых и пятое. И так далее. Т.е. сморите на первые x-2 тройки. Там первые 2 элемента в каждой тройке - первые 2 в ответе, а оставшиеся третьи элементы - это все остальные x-2 числа в ответе.
Вот вам пример для x=5: (a,b,c,d,e)
abc, abd, abe, bcd, bce ...
Не важно, что за числа a..e - важно что они в не убывающем порядке. Тогда тройка abc - точно будет самой первой.
Это все если вам на вход подаются ВСЕ тройки. Если же не все, то можно, например, взять все уникальные элементы и, если в какой-то тройке элементы повторяются, то брать эти элементы 2, или 3 раза, если вся тройка состоит из повторений.