Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Для каждой клетки создаются два значения: максимальная и минимальная сумма монет на пути из левой верхней клетки в эту клетку.
- 2
Если в клетку можно попасть из соседней клетки сверху, переход разрешён только при отсутствии стены между ними. Аналогично проверяется переход слева.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Считаем левую верхнюю клетку начальной: её монета входит в сумму каждого маршрута.
- 2
Для каждой клетки храним две величины: максимальную и минимальную сумму, которую можно получить при попадании в эту клетку.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Считываем из файла размер поля, стоимость монет в клетках и расположение внутренних стен.
- 2
Для каждой клетки храним две величины: максимальную и минимальную сумму, которую можно получить при движении из левой верхней клетки в эту клетку.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Обозначим через $max[i][j]$ и $min[i][j]$ максимальную и минимальную суммы, которые можно получить при попадании в клетку $(i,j)$.
- 2
Для каждой клетки рассматриваем только те переходы сверху или слева, которые не пересекают стену.$$max[i][j] = a[i][j] + \max(max[i-1][j], max[i][j-1])$$
Ещё 2 шага — в полном решении
05ФИПИ 4392F7№ 8Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз. Между соседними клетками могут быть…
- 1
Вычислим максимальные суммы для маршрутов до клеток таблицы. В правой нижней клетке получаем:$$1 \to 9 \to 17 \to 21;\quad 11 \to 20 \to 21 \to 24;\quad 12 \to 23 \to 35 \to 37;\quad 14 \to 26 \to 40 \to 46$$
- 2
Аналогично вычислим минимальные суммы. В правой нижней клетке минимальная сумма равна:$$1 \to 9 \to 17 \to 21;\quad 11 \to 10 \to 11 \to 14;\quad 11 \to 13 \to 23 \to 16;\quad 13 \to 14 \to 18 \to 22$$
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Считайте из электронной таблицы размеры квадрата, стоимости монет и сведения о стенах.
- 2
Для каждой клетки вычислите максимальную сумму пути из левой верхней клетки. Переходы разрешены только из верхней или левой клетки, если между клетками нет стены.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Квадрат ограничен внешними стенами, между соседними клетками могут…
- 1
Построим две таблицы динамического программирования: $max[i][j]$ — максимальная сумма при достижении клетки $(i,j)$, а $min[i][j]$ — минимальная сумма.
- 2
Для каждой клетки, кроме стартовой, рассмотрим допустимые переходы из клетки сверху и из клетки слева. Переход разрешён только при отсутствии соответствующей стены.
Ещё 2 шага — в полном решении
Задание выполняется с использованием прилагаемых файлов. Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну…
- 1
Считаем для каждой клетки две величины: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку.
- 2
Если в клетку можно прийти сверху или слева, максимум равен стоимости монеты в клетке плюс больший из соответствующих максимумов, а минимум — стоимости монеты плюс меньший из соответствующих минимумов.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот может перемещаться только вправо или вниз, если между соседними…
- 1
Обозначим через $F_{\max}(i,j)$ максимальную сумму, которую можно собрать при попадании в клетку $(i,j)$, а через $F_{\min}(i,j)$ — минимальную сумму.
- 2
Для каждой клетки учитываем только те переходы сверху или слева, которые не пересекают стену.
Ещё 2 шага — в полном решении
10ФИПИ 097227№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n<3$; $F(n)=F(n-2)-F(n-1)$, если $n>2$ и при этом $n$ чётно…
- 1
Так как $1<3$ и $2<3$, начальные значения равны:$$F(1)=F(2)=1$$
- 2
Последовательно применяем соответствующую формулу для чётных и нечётных значений $n$:$$F(3)=1,\ F(4)=0,\ F(5)=-1,\ F(6)=1,\ F(7)=3,\ F(8)=-2$$
Ещё 3 шага — в полном решении
11ФИПИ 1644D5№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n<3$; $F(n)=F(n-2)-F(n-1)$, если $n>2$ и при этом $n$ чётно…
- 1
По условию $F(n)=1$ при $n<3$, поэтому $F(1)=1$ и $F(2)=1$.$$F(1)=F(2)=1$$
- 2
Последовательно применяем соответствующую формулу для чётных и нечётных значений $n$.$$F(3)=1,\ F(4)=0,\ F(5)=-1,\ F(6)=1,\ F(7)=3,\ F(8)=-2,\ F(9)=-7$$
Ещё 2 шага — в полном решении
12ФИПИ 2C19E5№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=2\times F(n-1)+2$, если $n>1$ и при этом $n$…
- 1
Начальные значения: $F(0)=0$ и $F(1)=0$. Последовательно применяем заданные правила.
- 2
Для чётного аргумента $30$ используется второе слагаемое $n/2$: $F(30)=30/2+F(29)$.
Ещё 2 шага — в полном решении
13ФИПИ 4254B4№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=2\times n+F(n-1)$, если $n>1$ и при этом $n$…
- 1
Начальные значения: $F(1)=0$, поэтому $F(2)=2F(1)=0$.
- 2
Последовательно применяем рекуррентные соотношения для нечётных и чётных значений $n$.
Ещё 3 шага — в полном решении
14ФИПИ 7C0639№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=\left\lfloor\dfrac{n+1}{2}\right\rfloor+F(n-1)$…
- 1
Последовательно вычисляем значения функции по заданным формулам. Для чётного $n$ значение удваивается и увеличивается на 1, для нечётного $n$ прибавляется целая часть $(n+1)/2$.
- 2
На последних шагах получаем:$$F(30)=131037$$
Ещё 3 шага — в полном решении
15ФИПИ 7C657B№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=n+F(n-1)$, если $n>1$. Чему равно значение выражения…
- 1
По рекуррентному соотношению последовательно выражаем значение функции:$$F(2023)=2023+F(2022)=2023+2022+F(2021)=2023+2022+2021+F(2020)$$
- 2
Вычитаем $F(2020)$ из обеих частей:$$F(2023)-F(2020)=2021+2022+2023$$
Ещё 1 шаг — в полном решении
16ФИПИ 8C4B9D№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=2\cdot F(n-1)+2$, если $n>1$ и $n$ нечётно…
- 1
Начальные значения: $F(0)=F(1)=0$. Последовательно применяем рекуррентные формулы.$$F(2)=1$$
- 2
Для нечётных аргументов значение удваивается и увеличивается на 2, для чётных прибавляется половина аргумента. После последовательного вычисления получаем:$$F(24)=12272,\quad F(25)=2\cdot12272+2=24546$$
Ещё 2 шага — в полном решении
17ФИПИ FF255D№ 16Повышенная Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=2\times n+F(n-1)$, если $n>1$ и при этом $n$…
- 1
Начинаем вычисление с базового значения:$$F(1)=0$$
- 2
Последовательно применяем нечётную и чётную формулы. В частности, для последних значений:$$F(19)=2\cdot19+F(18)=5074$$
Ещё 1 шаг — в полном решении
18ФИПИ 01C951№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Начальную клетку включают в сумму бонусов. Для неё минимальная и максимальная суммы равны её бонусу.$$min[1][1] = max[1][1] = bonus[1][1]$$
- 2
Для каждой следующей клетки рассматривают только разрешённые переходы из клетки сверху и из клетки слева.$$min[i][j] = bonus[i][j] + \min(допустимые\ min[i-1][j],\ min[i][j-1])$$
Ещё 2 шага — в полном решении
Квадратное поле имеет размер $N \times N$, где $1 < N < 30$. В каждой клетке находится монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только…
- 1
Считаем, что значение клетки входит в сумму маршрута, в том числе для начальной и конечной клеток.
- 2
Для каждой клетки заполняем две динамические таблицы: одну для максимальной, другую для минимальной суммы от начальной клетки до данной клетки. Переход разрешён только по отсутствующим стенам.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
- 1
Создаём две таблицы динамических значений: в одной храним максимальную сумму от начальной клетки до каждой достижимой клетки, в другой — минимальную сумму.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
- 2
При вычислении клетки исключаем переходы, через которые проходит внутренняя стена. Недостижимым клеткам значения не присваиваем.
Ещё 1 шаг — в полном решении