Длинное GCD входит в разряд вещей, которые легко пишутся на С++. К сложным я бы отнес только длинное деление.

Перекладывать надо всегда самые тяжелые. Таким образом, по набору ходов можно понять, у кого будет самая тяжелая книга, у кого вторая по тяжести итд. Дальше, зная это, сортируем книжки и делаем ДП от двух параметров – текущая книга, сколько книг взято.

Задача Е ништяк. Идея простая, реализация сложная. По С интересно действительно ли можно доказать решение которое как бы за квадрат. Я думал над ним на контесте, но ничего в голову не пришло.

acm.am

That was not me, that was homo_sapiens.

Вообще причин не выводить с 20 (я всегда делаю 18) знаками нету. Это одна из привычек которую хорошо в себе развить :о)

Он новый выделит, старый-то он освободит.

Ну тот факт, что вершина может быть продавлена, не гарантирует, что все хлопья с отрезка могут на нее упасть.

Проблема не в жаднике, проблема в том, что авторское решение неверно.

2 0 2 2 2
| | | | |
2 4 2 4 2

Fourth 2 won’t break the scales.

My solution, which passes system tests, fails this test.

Если дп возвращает true, как много хлопьев падает на уровень ниже?

Сначала писалось правильное решение с тернарным поиском, а затем его запуском понималось простое решение :о)

В g++ вектор растет в два раза – только что проверил. В VS в презентации STL говорил, что у них растет в 1.5. Студии проверить нету.

Я сам хоть локально и пишу на g++, отправляю всегда в студии, потому что I64d.

Мое очень субъективное мнение: на С++ программистов ниже спрос, чем на Java, но и предложение хороших С++ программистов гораздо ниже, чем хороших Java программистов. Мне смутно кажется, что если действительно хорошо знать С++, трудоустроиться как минимум не сложнее.

Наверное, когда говорят “используя O(1) памяти”, подразумевается, что структура дерева лежит в read-only памяти. Если это не так, обычно прямо указывают, можно ли дерево менять, и надо ли его в конце восстановить.

Решение, когда дерево можно разрушить, можно сделать примерно так (тут я предполагаю, что указатель на вернишу и указатель на очередь занимают одинаковое количество памяти):

# создаем фиктивный список детей содержащий корень
ptr stack = [null, root]
while stack != null:
   ptr lst = stack # на вершине стека лежит список вершин
   stack = lst[0] # нулевой элемент украден для поддержания стека
   while lst[1:] содержит хотя бы один элемент не равный null:
      for vptr in lst[1:]: # vptr указывает на вершину
         # полагаем, что vptr -- это read-write указатель (то есть запись в него меняет соответствующий элемент списка)
         if vptr != null:
            vertex v = *vptr
            print v # вершина выведена, она нам больше не нужна
            if v имеет детей:
               lst2 = список детей v:
               vptr = lst2[0] # заменяем элемент lst содержащий vptr на первого ребенка v
               if v имеет более одного ребенка:
                  lst2[0] = stack
                  stack = lst2
            else: vptr = null

Эта функция вся в хаках, и наверняка можно сделать без них, но она должна работать. Основная идея – мы обрабатываем списки детей (не важно массив это или вектор – главное чтобы по нему можно было итерировать). Мы складываем такие списки в стек. При этом мы исползуем первый элемент списка чтобы указать на следующий элемент стека. Основная идея алгоритма: взять список из стека. Сейчас это список содержит детей какой-то вершины (та вершина уже давно выведена, и нам не интересна). Обработаем вершины из списка. Для каждой вершины выведем ее и положим список ее детей на стек. При этом нам придется пожертвовать первым элементом этого списка. Положим этот первый элемент в список, который мы обрабатываем прямо сейчас, вместо элемента, который мы только что вывели. Когда один список вершин обработан, для каждой вершины этого списка ее список детей уже лежит на стеке, с утраченным первым элементом, а все эти первые элементы сейчас сложены в список, который мы только что обработали. Обработаем его снова, и снова, пока в нем ничего не останется. Ничего не осталось – берем следующего из списка. В такой реализации это квадрат по времени, но можно ужать до линии, если в начале каждой обработки откидывать все nullptr в списке в конец. По пямяти константа, но используется память дерева.

Второе ветвление функции Prob там в коде напоминает вот эту картинку:

Проблемы надо решать в порядке приоретитов. Твоя текущая проблема не научиться челенжить, а рассмотреть возможность перехода с ПО, которому уже декада стукнула.

В админской комнате проскочил тест на полкуска, который убивает все решения, включая авторское

Edges are 0-1, 1-3, 0-2, 2-3, 3-4, 4-5. Our solutions return 2 but correct answer is 1

Решаем динамикой по дереву. Считаем три значения

1. Сколько стоит покрасить все поддерево.

2. Сколько стоит покрасить все поддерево, если мы знаем, что предок жарит бомбой (не обязательно сам, главное, чтобы в нашем направлении)

3. Сколько стоит покрасить все поддерево, если мы знаем, что предок ждет нас что мы прожарим бомбой из поддерева в предка.

Но конечно переходы правильно вбить это то еще волшебство.

ну с точностью до выбора базового типа

Базовый тип в этом вопросе важен. Например, если использовать unsigned char, полученный код будет примерно на 10% медленее.

Когда я также пошутил, у моего комментария было +200 :о)

+/-1 in general doesn’t change odd/even for B%(A+1), if A is even. If B%(A+1) = 0, then (B-1)%(A+1) = A – oddness doesn’t change.

You don’t have to lose first two games. If you win the third game, you will have a bag big enough to fit any presents from first two days, should you win any.

(double post)

Let’s say the larger number is B, the smaller one is A. If A is odd, the case is pretty simple – after each turn B % 2 changes, so we win if and only if B%2 = 0.

If A is even, we win if B % (A+1) is even. To prove it we need to prove that each winning state has a move to a losing state, and that any move from the losing state only goes to a winning state.

If B % (A+1) is even, we can always make it odd by subtracting one, if B % (A+1) is not zero, or by subtracting A, if it is zero. That proves that from every winning state there’s a move into a losing state.

If B % (A+1) is odd, any turn will make it odd. This can be proven by induction: If you subtract A^0=1, B % (A+1) will obviously become even. Let’s say we have proven that subtracting A^k changes oddness. Since subtracting A^k * (A+1) obviously doesn’t change oddness (since it is divisible by A+1), subtracting A^(k+1) = A^k * (A+1) — A^k does change it. That proves that from any losing state you can only move to a winning state.

Чтобы сымитировать конец файла с клавиатуры надо нажать Ctrl+Z. Тогда код, читающий с стандартного входа, поверит, что произошел EOF.

Для нечетных y легко понять, что достаточно чтобы x/y было четно (потому что четность x/y меняется каждый ход)

Для четного – в конце остаток на (y+1) равен нулю, то есть четен, и это выигрышная позиция. Докажем, что нечетный остаток – это проигрышная позиция.

Если сейчас остаток четный – его всегда можно сделать нечетным, сделав -1, если остаток не 0. и -y, если он ноль.

Если сейчас остаток нечетный, то любой ход его сделает четным – это легко показать для хода в -1, остальные легко доказываются по индукцти (пусть мы доказали, что y^k меняет четность, также очевидно, что y^k * (y+1) не меняет четность, потому что делится на y+1, отсюда y^(k+1) = y^k * (y+1) — y^k очевидно меняет четность).

Я просто оставлю это здесь http://habrahabr.ru/post/139895/

Писец, пацаны, после первого прочтения пытался понять почему прочитавшие плюсуют пост – повесть, по-моему, простенькая. Потом, прочитав первых пяти прокомментировавших под постом, понял прикол.

Предлагаю продолжение писать про политику, предпосылки присутствуют.

Вообще работать с соображением, что левая граница включетельно, правая – нет, кажется удобнее, чем когда обе границы включены. Мне кажется что писать бинарный поиск с правой границей включенной – это все еще осталось со времен, когда все писали на паскале (и переходит из старых книжек / учителей старой закалки), на котором обе границы включительно кажется более естественными.

По хорошему среда должна подсказать тип i при наведении на нее мышкой.

Я согласен с тем, что использовать auto либо когда код сокращается очень сильно, либо когда его избежать нельзя.

Не могу не отметить еще, что фраза “я не согласен с Саттером” в вопросах, связанных с С++, звучит забавно :о)

Это похоже на правильное решение.

Решение немного проще в правке.

В отладочном выводе видно, что j = 4, в коде видно, что перед этим происходит j–, а значит реально было заполнено пять элементов массива, заведенного на четыре. Или я не прав? :о

В очередной раз на конкурсе для программистов сайт подразуметвает, что программист использует windows – на ссылке для скачивания даже не указано для какой ОС скомпилированы лежание в ней бинарники (хотя, конечно, можно догадаться по расширению)

Откуда уверенность, что падает именно создание листа? В циклах ниже i3 указывает сразу на третий элемент листа, и дальше почти сразу сдвигается еще на один элемент вправо – то есть решение будет работать только если а) в листе есть хотя бы черыте элемента или б) вызов оператора ++ на итератор, указывающий на end, по прежнему указывает на end. Я бы скорее поверил, что ошибка кроется в этом цикле. В любом случае, на контейнеры, вообще говоря, надеяться можно, и глупо их не использовать. Надо просто ознакомиться с тем, как они устроены, и какие у них есть подводные камни (например, что удалять из вектора итерируя по нему опасно – хоть и возможно)

П.С.

(работаю в Microsoft Visual C++ 6.0)

Это просто без комментариев.

Очень крутой сайт, очень понятно объясняеться.

Не могу не вызарить полное не согласие с вашей точкой зрения.

Какие результаты дает clang на линуксе на такой же виртуалке? Мне кажется, что от компилятора должно мало зависеть в таком тесте.

Какие результаты показывает stdio, если выполнять те же самые действия?

++ в пользу разрешения ему участвовать. Запрет на участие в официальном старте кажется как минимум странным.

Конечно, это не “конечно”

А чекеры для таких раундов пишутся на языке раунда?

Я уже тоже нервничаю :о

В этой задаче не было двоякого понимания условия.

Я помню в седьмом классе на олимпиаде по математике была задача про рыцарей и лжецов, где каждый говорил “справа от меня сидит три рыцаря”. И на разборе один из неверно решивших ее участников с пеной у рта доказывал, что если лжец такое сказал, значит справа от него сидит три лжеца, а не по крайней мере один лжец. Схожая ситуация – человек не знает математику, и обвиняет организаторов математической олимпиады в том, что в условии задачу ему не разжевали.

Если пишешь соревнование по программированию, разумно уметь мыслить логически. И не в седьмом классе мы уже тут в большинстве своем.

В формате вывода по прежднему что-то странное.

Да, имеллось ввиду как в рантайме определяется что вызвать.

На самом деле примерно так и сделано как ты говоришь, только я не думаю, что таблица на самом деле ограницена. Просто если за ее пределы вылезти, скорее всего поймаешь AV попытавшись вызвать виртуальный метод через указатель.

Мой любимый вопрос про указатели на функции-члены класса – это как отличить указатель на виртуальную функцию от указателя на невиртуальную функцию.

#include <stdio.h>

class Moo
{
    public:
        virtual void a1(int a) { printf("a1 %d\n", a); };
        void a2(int a) { printf("a2 %d\n", a); };
};

int main()
{
    Moo* a = new Moo;

    void(Moo::*A1)(int) = &Moo::a1;
    void(Moo::*A2)(int) = &Moo::a2;

    printf("SizeOfs: %d %d\n", sizeof(A1), sizeof(A2));

    printf("Content of A1: %lld %lld\n", A1);
    printf("Content of A2: %lld %lld\n", A2);

    (a->*A1)(5);
    (a->*A2)(7);

    return 0;
}

Вот это код выводит:

SizeOfs: 16 16
Content of A1: 1 0
Content of A2: 4196196 0
a1 5
a2 7

Последние две строки ожидаемы – все вызвалось верно.

Первая строка говорит, что указатели на функцию обе 16 байт, вторая говорит, что последние восемь байт в обоих указателях не используются, в то время как первые восемь байт в первом указателе содержат номер в виртуальной таблице, а во втором – адрес функции.

Так как тип у них одинаковый, вопрос – как при вызове компилятор понимает, вызывать по адресу или из таблицы?

Как же он все правильно сказал, если в том участке полиморфизм не работает, а его комментарий начинается с утверждения, что работает, а затем объясняет, почему он не работает.

Это круто – Visual Studio ведет себя так, как я ожидал бы чтобы код себя повел. Это, среди прочего, обозначает, что студия хранит размер объекта где-то в виртуальной таблице.

А еще это отвечает на вопрос почему G++ падает сразу, не вызвав деструктор даже первого объекта. Потому что деструкторы вызываются начиная с последнего элемента (это хорошо видно в твоем выводе – указатели уменьшаются).

Догадайся убрать под спойлер хотя бы. В идеале конечно надо удалить комментарий.