• Как разбить множество на три подмножества с одинаковой суммой элементов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Задача о рюкзаке, даже о двух :)
    Заводите массив M[0..S/3,0..S/3] (можно битовый, но лучше побольше - чтобы хранить обратные ссылки). В нём будут отмечены элементы M[a,b], такие, что из уже просмотренных элементов текущего набора можно выбрать непересекающиеся подмножества с суммами a и b.
    Когда приходит очередной элемент x - выполняете M[a,b]=M[a,b] | M[a-x,b] | M[a,b-x] для всех a,b начиная с конца (с больших a,b). Если при этом 0 сменился на 1 - помечаете в массиве обратных ссылок, из какого элемента вы сюда попали.
    Сложность - O(n*S^2). Можно ли сделать лучше, не знаю.

    Вот вариант кода - но он печатает только два множества. Как напечатать третье, разберётесь.
    spoiler
    static void Main(string[] args) {
                int[] dat=Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
                int S=0;
                foreach(int x in dat) S+=x;
                if(S%3!=0) {
                    Console.WriteLine("-1"); return;
                }
                S/=3;
                int[,] M=new int[S+1,S+1];
                M[0,0]=-1;
                foreach(int x in dat) {
                    for(int a=S;a>=0;a--) {
                        for(int b=S;b>=0;b--) {
                            if(M[a,b]==0) {
                                if(a>=x && M[a-x,b]!=0) M[a,b]=x;  // back by set1
                                else if(b>=x && M[a,b-x]!=0) M[a,b]=-x;  // back by set2
                            }
                        }
                    }
                }
                if(M[S,S]==0) {
                    Console.WriteLine("-1"); return;
                }
                int u=S,v=S;
                string res1="",res2="";
                while(u!=0 || v!=0) {
                    if(M[u,v]>0) {
                        res1+=" "+M[u,v]; u-=M[u,v];
                    } else {
                        res2+=" "+(-M[u,v]); v+=M[u,v];
                    }
                }
                Console.WriteLine(res1);
                Console.WriteLine(res2);
            }

    Ответ написан
  • Что не так с алгоритмом для поиска наибольшей неубывающей подпоследовательности?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В этой задаче нельзя обойтись "текущей подпоследовательностью". Надо держать самые длинные подпоследовательности, заканчивающиеся на разные элементы (чем больше элемент, тем длиннее должна быть подпоследовательность, заканчивающаяся на него), и когда приходит новый элемент, то присоединить его к самой длинной из последовательностей, к какой возможно (причём старую последовательность сразу выбрасывать нельзя - она ещё может пригодиться), а потом выбросить неоптимальные (последовательность такой же длины, что и другая, но заканчивающаяся на больший элемент).
    Например, для последовательности [1,2,7,8,9,5,6,3] вам придётся помнить
    [1,2,7,8,9]
    [1,2,5,6]
    [1,2,3]
    [1,2]
    [1]
    Любая из этих последовательностей может быть началом правильного ответа.
    Так что начало решения у вас правильное. Но в векторе d должны храниться не числа, а их индексы (и поиск должен быть более сложным), а массив prev надо модифицировать так: prev[i]=d[j-1].
    Для примера [1,2,7,8,9,5,6,3] получаем
    d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
    (значение -1 используется для обозначения ситуации "нет такого индекса").
    Ответ написан
    3 комментария
  • Разница между: транспайлер, транслятор, компилятор?

    RiseOfDeath
    @RiseOfDeath
    Диванный эксперт.
    Ну если в двух словах, то компиляция - процесс получения программы (исполняемые машиной команды) из исходного кода на неком языке программирования.

    Трансляция - преобразование исходного кода программы из одного ЯП в другой. Обычно компиляторы (например для C/C++) транслируют исходник в программу на асемблере, и уже потом ее компилируют.

    Что касатеся транспайлера (Transpiler) - это тот же транслятор с той лишь разницей, что у результата примерно тот же уровень абстракции, что и у исходного текста (ну например транслятор из Java в C++).

    Ссылки:
    Source-to-source compiler
    Compiler
    Translator
    Ответ написан
    Комментировать
  • Сколько можно составить слов длины n из русских букв, таких что в них есть слово X?

    @localghost
    Возможно, чего-то не понял, но откуда у вас степени ниже пятой? Если, к примеру, 4 символа перед, а 1 после - вы считаете это как 33^4 + 33? Почему, чем это отличается от случая просто 5 символов перед?

    По-моему, следует считать так: кроме "привет" есть еще пять букв. Вариантов набрать эти пять букв - 33^5. Когда у нас уже есть пять букв, слово "привет" можно впихнуть туда шестью разными способами. Итого 6 * 33^5.

    Кроме того, в общем случае надо учесть, что некоторые "слова" мы могли посчитать не один раз. Скажем, если всего букв 12, то "приветпривет" посчитан лишний раз. Здесь, кажется, такого нет.
    Ответ написан
    2 комментария
  • Как, используя алгоритм быстрой сортировки, определить лежит точка в массиве отрезков или нет?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Можно решить и за линейное время (после сортировок):
    1) берём массив концов отрезков (xi,1) и (yi,-1), сортируем (не забывая, что при одинаковых первых числах сначала идут все начала отрезков, а потом все концы: так для отрезков [1,2] и [2,3] получим массив (1,1),(2,1),(2,-1),(3,-1))
    2) берём массив длиной n (число точек), заполняем его числами от 1 до n (если пишем на C-подобных языках - то от 0 до n-1). Cортируем массив, используя условие less(a,b)=(P[a] < P[b]), где P - массив точек. Получим индексы точек, отсортированные по возрастанию координат соответствующих точек.
    3) Идём по обоим массивам, сравниваем координаты. Когда проходим точку в массиве концов, то прибавляем к счётчику второй элемент. Когда достигаем координаты очередной точки из P - записываем в массив результатов значение счётчика. Не забываем, что точка P[a]=x обрабатывается после всех точек (x,1) но до всех точек (x,-1) из массива концов.
    4) Выводим массив результатов.
    Ответ написан
    2 комментария
  • Как, используя алгоритм быстрой сортировки, определить лежит точка в массиве отрезков или нет?

    Объединить вместе в один массив точки начал (с доп.полем "+1") и концов (с доп.полем "-1") отрезков и отсортировать его по координате :
    [11,+1],[17,+1],[21,-1],[32,+1],[37,-1],[42,-1]
    А затем один раз пройтись по нему накапливая сумму доп.поля.
    Ответ написан
    7 комментариев