Шахматный конь находится в левом верхнем углу

Шахматный конь находится в левом верхнем углу

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

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

В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15).

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

Пусть dp[ i][ j] содержит количество способов, которыми можно добраться из левого верхнего угла – клетки с координатами (1, 1) в правый нижний угол – клетку с координатами ( n, m). Изначально обнулим массив dp и положим dp[1][1] = 1.

Согласно ходам коня в клетку ( i, j) можно попасть либо из ( i – 1, j – 2), либо из ( i – 2, j – 1). Следовательно

dp[ i][ j] = dp[ i – 1][ j – 2] + dp[ i – 2][ j – 1]

Заполним массив dp для поля размером 7 * 7:

Объявим двумерный массив.

Читаем входные данные.

Пересчитываем ячейки массива dp. Поскольку в ячейки первой строки и первого столбца конь попасть не может ( кроме начальной позиции ) , то циклы по i и по j можно начинать с 2.

memset(dp,0, sizeof (dp));

printf( "%d
" ,dp[ n ][ m ]);

public static void main(String[] args )

Scanner con = new Scanner(System. in );

int n = con .nextInt();

int m = con .nextInt();

for ( int i = 2; i n ; i ++)

for ( int j = 2; j m ; j ++)

dp [ i ][ j ] = dp [ i -1][ j -2] + dp [ i -2][ j -1];

System. out .println( dp [ n ][ m ]);

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит "Мы с радостью продадим Вам метр ткани за Pi бурлей, однако если Вы купите не менее Ri метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Qi бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

Читайте также:  Устав открытого акционерного общества российские железные дороги

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более Fi метров ткани.

Ответственный за покупку очень устал от проделанной работы и поэтому поставленную перед ним задачу «закупить ткань за минимальные деньги» переложил на своих помощников. Напишите программу, которая определит, сколько ткани нужно купить в каждом из магазинов так, чтобы суммарные затраты были минимальны.

Первая строка выходного файла должна содержать единственное число — минимальное необходимое количество бурлей.

Во второй строке выведите N чисел, разделенных пробелами, где i-ое число определяет количество метров ткани, которое нужно купить в i-ом магазине. Если в i -ом магазине ткань покупаться не будет, то на i -ом месте должно стоять число 0. Если вариантов покупки несколько, выведите любой из них.

Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1 .

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

Как оказалось, голубые ели бывают M различных сортов. Для ели каждого сорта известна максимальная длина ее тени в течение дня в западном и в восточном направлении ( W i и E i соответственно). При этом известно, что ели растут гораздо лучше, если в течение дня они не оказываются в тени других елей.

Координатная ось направлена вдоль аллеи с запада на восток.

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

Во входном файле записано сначала натуральное число M — количество сортов елей (1  M  100). Затем идет M пар чисел W i , E i , описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели (числа W i , E i — целые, из диапазона от 0 до 30000). Далее идет натуральное число N — количество клумб, в которых можно сажать ели (1  N  100). Далее идет N чисел, задающих координаты клумб (координаты — целые числа, по модулю не превышающие 30000). Клумбы перечислены с запада на восток (в порядке возрастания их координат).

Читайте также:  Как отключить обновления на планшете андроид

Примечание

Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E , то все клумбы с координатами от X +1 до X + E –1 попадают в тень от этой ели, а клумба с координатами X + E — уже нет. Аналогично для тени в западном направлении.

В выходной файл выведите сначала число A — максимальное количество елей, которые удастся посадить, а затем A пар чисел, описывающих ели. Первое число каждой пары задает номер клумбы, в которую садится ель. Второе число определяет номер сорта этой ели.

В спортзале размером N x M метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на N x M клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

Аттракцион заключается в том, что участника ставят в некоторой клетке спортзала и просят как можно быстрее добежать до некоторой другой клетки. При этом накладываются следующие условия:

  • Участнику запрещено ходить по черным клеткам.
  • Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
  • За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
  • В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

Известно, что на то, чтобы перебежать из клетки в соседнюю, участник тратит ровно 1 секунду. Требуется вычислить минимальное время, за которое участник сможет достичь конечной клетки.

Читайте также:  Увеличение дальности полета dji phantom 3 standard

Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M , задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

Ссылка на основную публикацию
Что такое автозагрузка в компьютере
Автозагрузка в Windows 10 В Windows 10 есть много интересных особенностей. Но сейчас речь пойдет о такой штуке, как автозагрузка....
Чернила светятся в ультрафиолете
Употребление симпатических (невидимых) чернил подразумевает запись неразличимую в обычных обстоятельствах, но появляющуюся после фото, химической или физической проявки. Это есть...
Чернила для принтера в шприцах
Заправочные комплекты INKO в шприцах 3х20 мл., с высококачественными чернилами на основе красителя (Dye ink) и пигментные чернила (Pigment ink)...
Что такое айти специалист
Именно в ИТ стремится перейти больше всего представителей других профессиональных областей — там хотел бы работать каждый пятый российский соискатель....
Adblock detector