Для игры, описанной в задании 19, найдите наименьшее значение $S$, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
Для каждой возможной позиции из игры задания 19 определяем, может ли Ваня гарантированно выиграть своим первым ходом.
- 2
Затем рассматриваем позиции, из которых Ваня выигрывает первым или вторым ходом независимо от хода Пети. Из них исключаем позиции, обеспечивающие гарантированный выигрыш уже первым ходом.
Ещё 1 шаг — в полном решении
Для игры, описанной в задании 19, найдите значение $S$, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой…
- 1
Рассмотрим дерево игры из задания 19 и проверим для каждого значения $S$ две характеристики: может ли Ваня гарантированно выиграть первым ходом и может ли он гарантированно выиграть первым или вторым ходом.
- 2
Выбираем значения $S$, при которых выигрыш первым ходом не гарантирован, но выигрыш первым или вторым ходом гарантирован при любой игре Пети.
Ещё 1 шаг — в полном решении
Для игры, описанной в задании 19, найдите минимальное значение $S$, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
По правилам игры из задания 19 перебираем значения $S$ и анализируем все возможные ходы Пети. Для подходящего значения после любого первого хода Пети у Вани должна существовать ответная стратегия, приводящая к победе не позднее второго…
- 2
Одновременно исключаем значения, при которых Ваня может гарантированно выиграть уже первым ходом.
Ещё 1 шаг — в полном решении
Для игры, описанной в задании 19, найдите значение $S$, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при…
- 1
Рассматриваем дерево игры из задания 19 и для каждого значения $S$ определяем, есть ли у Вани стратегия, гарантирующая победу первым или вторым ходом.
- 2
Одновременно исключаем значения, при которых Ваня уже может гарантированно выиграть первым ходом.
Ещё 1 шаг — в полном решении
Для игры, описанной в задании 19, найдите наименьшее значение $S$, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
По правилам игры из задания 19 перебираем значения $S$ и анализируем выигрышность начальной позиции: отдельно проверяем возможность гарантированной победы Вани первым ходом и возможность победы первым или вторым ходом.
- 2
Для значений, меньших 44, хотя бы одно из условий не выполняется. При $S=44$ у Вани существует стратегия, гарантирующая победу первым или вторым ходом при любой игре Пети, но стратегии гарантированной победы первым ходом нет.$$S=44$$
Для игры, описанной в задании 19, найдите минимальное значение $S$, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
Рассматриваем дерево игры из задания 19 и классифицируем позиции по минимальному числу ходов, за которое Ваня может гарантированно добиться победы.
- 2
Проверяем значения $S$ по возрастанию. Нужно, чтобы выигрыш Вани был гарантирован не позднее второго хода, но не гарантирован первым ходом.
Ещё 1 шаг — в полном решении
Для игры, описанной в задании 19, найдите минимальное значение $S$, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
Рассматриваем игру из задания 19 и строим дерево возможных ходов для разных значений параметра $S$.
- 2
Проверяем первое условие: после любого хода Пети у Вани должна быть стратегия, приводящая к победе не позднее второго хода.
Ещё 2 шага — в полном решении
Для игры, описанной в задании 19, найдите наименьшее значение $S$, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
Для каждой позиции игры из задания 19 определяем, может ли Ваня гарантированно завершить игру своим первым ходом. Такие значения $S$ необходимо исключить.
- 2
Затем проверяем, существует ли стратегия, гарантирующая победу Вани первым или вторым ходом независимо от ходов Пети.
Ещё 1 шаг — в полном решении
Для игры, описанной в задании 19, найдите наименьшее значение $S$, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
По правилам игры из задания 19 перебираем значения $S$ и анализируем все возможные ходы игроков.
- 2
Для каждого значения проверяем, существует ли у Вани стратегия, гарантирующая победу первым или вторым ходом независимо от действий Пети.
Ещё 2 шага — в полном решении
Для игры, описанной в задании 19, найдите наименьшее значение $S$, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым…
- 1
По условию задания 19 анализируем дерево игры и классифицируем позиции по возможности гарантированного выигрыша Вани.
- 2
Отбираем значения $S$, для которых Ваня может выиграть первым или вторым ходом при любой игре Пети, но не может гарантировать победу уже первым ходом.
Ещё 1 шаг — в полном решении
Ниже на пяти языках программирования записан один и тот же алгоритм. Получив на вход число $x$, алгоритм печатает два числа: $L$ и $M$. Укажите наибольшее число $x$, при вводе которого алгоритм…
- 1
При последовательном целочисленном делении положительного числа на $2$ количество выполнений цикла равно числу цифр в его двоичной записи. Поэтому $M=6$ означает, что число имеет шесть двоичных разрядов.
- 2
Остаток $1$ при делении на $2$ соответствует единице в двоичной записи. Поэтому $L=5$ означает, что среди шести двоичных цифр должно быть пять единиц.
Ещё 2 шага — в полном решении
В прилагаемом файле приведена таблица вычислительных процессов: для каждого процесса указаны его идентификатор, время выполнения в миллисекундах и идентификаторы процессов, от которых он зависит…
- 1
Для каждого процесса по таблице определяем все процессы, от которых он зависит. Независимые процессы могут начинаться с первой миллисекунды.
- 2
Для зависимого процесса вычисляем самое раннее начало: оно следует после окончания самого позднего из процессов-зависимостей. Если последний из них заканчивается на миллисекунде $k$, процесс начинается на миллисекунде $k+1$.
Ещё 2 шага — в полном решении
Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число $x$, этот алгоритм печатает два числа: $L$ и $M$. Укажите наибольшее число $x$, при вводе которого…
- 1
За одну итерацию значение $x$ заменяется на результат целочисленного деления на $8$. Поэтому $M$ равно числу цифр исходного числа в восьмеричной системе счисления.
- 2
Условие $M=3$ означает, что $64 \leqslant x \leqslant 511$.
Ещё 3 шага — в полном решении
Ниже на пяти языках программирования записан один и тот же алгоритм. Получив на вход целое число $x$, этот алгоритм печатает два числа: $L$ и $M$. Укажите наибольшее число $x$, при вводе которого…
- 1
Цикл вычитает из $x$ число $9$, пока результат не станет меньше $9$. Поэтому после цикла $L=q$, а оставшееся значение $M=r$, где $x=9q+r$ и $0\leq r<9$.$$x=9q+r$$
- 2
Если $r<q$, алгоритм заменяет $M$ на $q$, а $L$ на $r$. Чтобы получить сначала $5$, а затем $8$, можно взять $q=8$, $r=5$.
Ещё 2 шага — в полном решении
В прилагаемом файле содержится таблица вычислительных процессов: для каждого процесса указаны его идентификатор, время выполнения и идентификаторы процессов, от которых он зависит. Независимые…
- 1
По данным файла для каждого процесса определяем время начала. Если процесс зависит от нескольких процессов, его запуск возможен после завершения самого позднего из них.$$t_{start}(B)=\max_{A\in Dependencies(B)}(t_{start}(A)+t(A))$$
- 2
Для каждого процесса записываем интервал его выполнения $[t_{start}, t_{start}+t]$ и объединяем все моменты начала и окончания процессов.
Ещё 2 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$. Сначала записывается двоичная запись числа $N$. Если $N$ чётное, справа дописывается $0$, а слева — $1$…
- 1
Рассмотрим чётное число $N$ с шестизначной двоичной записью. После добавления слева единицы и справа нуля получаем число вида $1\,\text{bin}(N)\,0$.$$R = 2^{7} + 2N = 128 + 2N$$
- 2
Требуется, чтобы $R > 225$, поэтому $128 + 2N > 225$, откуда $N > 48{,}5$. Наименьшее подходящее чётное число — $N=50$.$$R = 128 + 2 \cdot 50 = 228$$
Ещё 1 шаг — в полном решении
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс $B$…
- 1
Представим процессы в виде ориентированного графа: ребро направлено от каждого процесса-зависимости к зависящему от него процессу.
- 2
Для независимого процесса время окончания равно его длительности. Для остальных процессов время окончания вычисляется как сумма собственной длительности и максимального времени окончания всех его предшественников.$$T_i = t_i + \max\limits_{j \in P_i} T_j$$
Ещё 2 шага — в полном решении
Ниже на пяти языках программирования записан алгоритм. Получив на вход число $x$, этот алгоритм печатает два числа: $L$ и $M$. Укажите наименьшее число $x$, при вводе которого алгоритм печатает…
- 1
На каждой итерации число $x$ заменяется на результат целочисленного деления на $2$. Поэтому количество итераций $M$ равно длине двоичной записи исходного числа.$$M = 6$$
- 2
Условие $L = 4$ означает, что в двоичной записи числа должно быть ровно четыре единицы.
Ещё 2 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$. Сначала строится двоичная запись числа $N$. Затем к этой записи справа дописываются два разряда: сначала…
- 1
Переведём число 114 в двоичную систему счисления:$$114_{10}=1110010_2$$
- 2
Удалим два последних разряда. Получаем предполагаемую исходную запись числа $N$:$$1110010_2\to11100_2$$
Ещё 3 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$. Сначала строится двоичная запись числа $N$. Затем к этой записи справа дописываются два разряда: сначала…
- 1
Проверим числа, начиная с наименьших возможных кандидатов около границы. Для $N=21$ двоичная запись имеет вид $10101$.$$10101_2 \to 101011_2 \to 1010110_2 = 86_{10}$$
- 2
Результат для $N=21$ не больше 89, поэтому проверяем следующее число $N=22$.$$22_{10}=10110_2$$
Ещё 2 шага — в полном решении