dnsortorovka, Ну, руками также просто. Во-первых, скопируйте звездочки из ячеек, где они уже стоят. Потом берете каждую строку, смотрите, где там стоят звездочки, в каких столбцах, и копируете строку с этим номером в ответ, ставя звездочки, где их еще нет. Вот первая строка в ответе: там стоят звездочки в столбцах 3,5,6, потому что в R они там есть. Потом, втретьей строке есть звездочки в столбцах 1,2,5, в пятой строке - 2,4,5,6, в шестой строке в столбце 1. В итоге ставим звездочки в столбцах 3,5,6,1,2,5,2,4,5,6 - покрывая все ячейки в первой строке. А во второй строке: столбец 1 стоит, потому что он есть в R. Первая строка содержит звездочки в столбцах 3,5,6 - ставим их тоже.
Dyikot, Одна вещь логична: создание потоков сильно более тяжелая операция чем перемножение матриц, поэтому вариант с 4 потоками в ~4 раза медленнее.
Разница между 8x8 и 10x10 все еще укладывается впогрешность. Гоняйте тест 100000 или лучше миллион раз.
Плюс, возможно тут дело в том, что 8 - степень двойки. Так вот получается, что ячейки памяти, к которым вы обращаетесь при проходе по столбу чаще оказываются отстоящими ровно на 64 байта, что есть размер кеш линии. Т.е. они будут вытеснять значения из кеша и там будет больше промахов.
У вас очень короткая и операция и там почти нет вычислений - в основном обращения к памяти. Так что можно получить весьма неожиданные результаты из-за каких-то тонких деталей работы с кешем.
Попробуйте еще, например, транспонировать вторую матрицу - измените код умножения так, чтобы он по второй матрице тоже шел по строкам, а не по столбцам. Возможно странность исчезнет.
Alexandroppolus, Вообще, да, странное у вас ДП. По идее, ДП должно быть двумерное: F(sum, k) - минимальное количество монет, чтобы собрать сумму sum, используя первые k монет (где все монеты имеют по 2 копии и можно их использовать только по одному разу). Это стандартное ДП и можно хранить только одну строчку, если пересчитывать ее с конца: dp[i] = min(dp[i], dp[i-coin_value]). Но тогда цикл по монеткам должен быть внешним.
У вас же параметр только один, а использованные монеты засунуты в возвращаемое значение. Так делать нельзя. Любое состояние, влияющее на ответ должно быть в параметрах, а не в вычисляемом значении.
Указанная вами проблема действительно существует. При чем, не надо чтобы единственным предшественником был dp[sum-k]. Достаточно, чтобы по всем возможным оптимальным предшественникам нужная монета была использованна дважды.
Я тоже пока тест придумать не могу, но пока алгоритм не доказан - он должен считаться неправильным. Ваш алгоритм не является ДП как таковым, ибо по указанной проблеме, нельзя решать задачу для n через n-k: Ибо оптимальное решение для подзадачи не гарантирует оптимальное решение для текущей задачи. Так что его надо как-то по-другому доказывать.
Можно попробовать стресс тест написать с нормальным ДП или перебором: Авось рандом тест найдет.
Lastochka17, сначала по двойному углу раскрыли. Получили sin(3x)cos(3x). Синус там в ноль не обращается в пределе, его не трогаем. cos(3x) раскладываем в (4сos^2(x)-3)cos(x). cos(x) опять не трогаем, косинус в квадрате заменяем на 1-sin^2. 1-4sin^2(x) остается. Раскрываем по формуле разности квадратов и получаем в одном из множетелей -числитель. Оно-то и сокращается.
HedgeHog1234, и сколько они там памяти потребляли? Пишут ли там, сколько памяти было в тестах, которые упали? Вы уверены, что попытка выделить больше допустимого памяти будет учтена в этой статичтике как высокое потребление, а не, допустим, прошрамма будет прибита еще при попытке эту память съесть?
Вообще, я как специалист вам утверждаю: в этом точно есть ошибка. Это решение задачи не правильное, тут нужен перебор, а не ДП.
HedgeHog1234, Этого не может быть. Вы точно запустили с суммой и монетами примерно в 1000000000? Оно что-то вывело? Обратите внимание, надо чтобы монеты тоже были большие, иначе программа выведет -1 не создавая очень большого массива.
Евгений Петряев, И как вы там видите большое число? Вы тут len вообще не используете.
Если len выводить прямо там, оно неправильное?
Единственное, что тут может быть не так, это что функция читает меньше 10 байт и там какая-то фигня с досутпом к несуществующей части QByteArray. Проверяйте его длину, что ли.
Вообще, это на совести того, кто этот файл записывал. Можно вообще байты одного числа в разные части файла записывать и в любом порядке. Но обычно, все-таки, их все кладут рядом и в том же endianess (порядок байт): сначала самый старший байт, или наоборот - но одинаково для всех чисел.
Но это можно проверить или в спецификации формата файла, если он общепринятый, или расковырять программу, которая файл записывает. Или эксперементально определить.
Borankin, Ага, т.е. вы в каком-то редакторе вводите символ и сохраняете файл. Что за редактор? Даже если вы используете одну и ту же программу (например, notepad++), вот вообще не факт, что она ведет себя одинаково в разных системах.
Раз уж вы в линуксе, запустите команду `xxd 1.txt` в консоли и приведите ее вывод. Оно выведет файл в 16-ричном формате - там сразу станет видно, что это за 2 байта.
Евгений Петряев, В этом хедере приведена лишь декларация оператора <<. Его определение (тело функции), определено в каком-то cpp файле, которого у вас даже, скорее всего, нет. Оно скомилированно и лежит в файле xbase32.lib, или в каком-то подобном файле. Гуглите документацию к этой библиотеке - что и как надо подключать к вашему проекту.
Sunter, В бинарном виде. У вас массив интов. Каждый инт хранит от 0 до 2^32 - 1. Фактически, число записано в 2^32-ичной системе счисления.
При выводе такого числа, надо делить его на короткие вроде 1000000000. Остатки выводить. Все, кроме последнего с ведущими нулями до 9 цифр. И в обратном порядке.
При сдвиге у вас есть перенос с младших разрядов. Сдвигаете текущую "цифру" влево, OR-ите с переносом. 32 младших бита в текущую цифру, оставшиеся - в перенос.
Складывать как обычно, только смотреть, чтобы переполнения не было - надо использовать int64 для промежуточных значений.
С умножениями чуть сложнее - надо или промежуточный массив из int64 завести, или базу уменьшать, чтобы аккумуляторы не переполнялись.
Sunter, У вас нет умножения длинных чисел, у вас есть умножение длинного на короткое (2^64). Если за раз не помещается, можно 2 раза домножить на 2^32.
Вообще, если база не степень двойки, то все плохо. Я так понял, у вас в строке цифры хранятся, так что база у вас 10. Сдвиги можно реализовать только умножением на 2 в какой-то степени.
