Задачи 7-8 и 9-11 класс

 

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

 

Задача «Счастливый билет»

Эту задачу можно решить, используя чтение строк и конвертацию их в числа и наоборот.  Остановимся подробнее на другом подходе: использование операций div и mod. Остаток при делении шестизначного числа на 1000 – это число, состоящее из последних трех цифр номера, а частное – это число, состоящее из первых трех цифр номера. Сложим их и получим описанную в условии задачи сумму. Далее, используя div и mod, найдем все цифры, из которых состоит описанная сумма, и сравним их. Это нам позволит найти ответ в задаче.

Рекомендации при проверке.

Любое правильное решение оценивать в 100 баллов. Если при решении задачи участник не учел, что сумма двух трехзначных чисел может быть четырехзначным числом, то следует оценивать задачу из 70 баллов.

Задача «Лестница»

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

Рекомендации при проверке.

Если участник не учел, описанное выше условие, то оценивать задачу стоит исходя из 30 баллов.

Задача «Космический бой»

Решение задачи подразумевает процесс моделирования космического боя, по описанным в условии правилам. В начале, первый корабль первого игрока, стреляет по первому кораблю второго. Проверяем: уничтожил он его или нет. Если нет, то второй корабль первого игрока стреляет по недобитому первому кораблю второго игрока и т.д. Когда все корабли первого игрока выстрелили, то игроки меняются ролями, но у второго игрока корабли уже понесли потери и это необходимо учесть. Чиним раненный корабль и начинаем атаку.

При решении этой задачи желательно использовать следующие эвристики:

  1. если параметр атаки кораблей атакующей сторону больше количества «очков жизни» защищающейся стороны, то каждый выстрел атакующей стороны уничтожает корабль защитника.
  2. если H количество «очков жизни» кораблей защищающейся стороны, а A параметр атаки атакующей стороны, то для уничтожения 1 корабля выстрелить должно (H–1) div A.
  3. если у обеих сторон что параметр починки кораблей больше суммарной атаки всех кораблей противника, то это означает ничью. Не сложно доказать, что если хотя бы одна сторона уничтожила хотя бы один корабль другой стороны, то к ничьей игра уже не сведется.
  4. если у одной из сторон параметр починки кораблей больше суммарной атаки всех кораблей противника, то это означает победу этого игрока.

 

Рекомендации при проверке.

Если участник не учел только одну из описанных выше эвристик, то задачу стоит оценивать исходя из 90 баллов.

Если участник не учел две описанные выше эвристики, то задачу стоит оценивать исходя из 80 баллов.

Если участник не учел три или все четыре из описанных выше эвристик, то задачу стоит оценивать исходя из 70 баллов.

 

Задача «Игра великанов»

Не оптимальное решение этой задачи состоит в полном переборе всех вариантов квадрата, на который мог бы прыгнуть великан, и последующего сравнения первой позиции после прыжка великана со второй позицией. Это приводит к реализации решения, содержащей четырехмерный вложенный цикл, и, следовательно, сложность такого решения O(N4).

Оптимальное решение имеет сложность O(N2). Заметим, что в какой бы квадрат на поле не прыгнул великан, он может перевернуть либо 4, либо 6, либо 9 дисков. Если для наших позиций другое количество отличающихся дисков, то получить из первой вторую нельзя. Можно сравнить первую и вторую позиции и искать отличающиеся диски. Назовем диск первым отличающимся диском, если среди отличающихся дисков у него номер строки будет наименьшим, а если таких несколько, то среди них тот, у которого номер столбца наименьший.

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


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

Рекомендации при проверке.

Если решение не оптимально, то оценивается исходя из 50 баллов.

Если в решении найдено расположение отличающихся дисков, но не найдено общее количество, то решение оценивается исходя из 80 баллов. Это связано с тем, что позиции могут отличаться в нескольких местах.

 



Карта сайта Версия для печати © 2009 - 2017 Администрация Ростовской области