Методические рекомендации к оцениванию заданий

Методические рекомендации к оцениванию заданий

Оценивание каждой задачи 20 б, максимальное число баллов 100.

Задача 1. «СовятникХагварца»

Простейшим решением является просмотр элементов i-й строки и i-го столбца, i=1,2,...,N (номера строки и столбца должны быть равны, иначе они пересекаются не по диагональному элементу) массива до нахождения индекса k, такого что элементы k-ой строки и k-го столбца удовлетворяют требуемому свойству или установления факта, что такого индекса нет. Очевидно, что в последнем случае необходим просмотр почти всех элементов массива.

Однако возможно существенно сократить количество операций, используя следующий факт. Рассмотрим элемент A[k, j], k<>j. Возможны следующие ситуации:

1. A[k, j] = 0.

В этом случае легко заметить, что индекс k не подходит, так как в строке с индексом k стоит 0. Поэтому можно ограничится поиском заданного элемента в подмассиве без k-ого столбца и k-й строки.

2. A[k, j] = 1.

В этом случае легко заметить, что индекс j не подходит, так как в столбце с индексом j стоит 1. Поэтому можно ограничится поиском заданного элемента в подмассиве без j-ого столбца и j-й строки.

Таким образом, рассматривая на каждом шаге значения элементов A[k, j], таких, что A[k, j] является элементом интересующего нас подмассива, потребуется просмотр ровно N-1 элемента для установления единственного индекса k, удовлетворяющего требуемому свойству. Осталось проверить только элементы этого столбца и строки.

k:=1

для j от 2 до N

если A[k, j] = 0то k:=j

Задача 2. «Гуляющий кубик»

«Гуляющий кубик» – типичная задача на графы, основой решения которой является алгоритм Дейкстры на графе с 64*6 вершин. Метод полного перебора приемлемлишь на небольших тестах, не требующих больших затрат времени и оцениваться может в 50%.

Задача 3. «Шоу»

Для начала сделаем два замечания. Во-первых, пусть некоторое число M разложено на простые множители, т. е. .Тогда число различных его делителей, включая 1 и M, можно вычислить по формуле . Для решения поставленной задачи необходимо, чтобы это выражение было равно N. Во-вторых, если с учетом первого замечания подобрать такие di, чтобы M было минимальным, то решением данной задачи будет .

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

Задача 4. «Конверты для Прорицательницы»

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

Более эффективным будет упорядочить открытки по уменьшения размеров (ориентируясь на наиболее длинную сторону) и пытаться разместить по конвертам сначала самые большие открытки. Причем, если открытка помещается в несколько конвертов, надо взять самый маленький из них. Для снижения времени работы алгоритма можно предварительно упорядочить конверты аналогично тому, как это сделано с открытками. При проверке условия, поместится ли открытка в конверте, надо не забывать, что открытка может лечь в конверт под каким-либо углом.

Задача 5. Укладка плиток

При решении данной задачи существенным является тот факт, что числа n и m – четные. Это значит, что всю матрицу, соответствующую площадке, можно разбить на квадраты размером 2×2 и решать локальные задачи отдельно для каждого такого квадрата. А далее все просто: если горизонтальное расположение кирпичей не подходит, то необходимо использовать вертикальное расположение.