Критерии оценки и решения задач 9-11 класс

Автор: admin Опубликовано: Дек 8, 2010 В рубрике: Олимпиада

Задача 1. Магический квадрат


q2.JPG
Рекомендации при проверке.
Если участник не учел, что одна из сумм может выйти за пределы типа Integer (2-х байтное знаковое целое), то решение оценивается из 70 баллов.
Задача 2. Бег с препятствиями
Введем обозначения: [x]– округление вещественного числа до ближайшего сверху целого не равного x; [x]– округление вещественного числа до ближайшего снизу целого не равного x;
Путь бегуна будет проходить по ломанной, соединяющей старт и финиш. Кратчайший путь не единственен, но очевидно, что сумма вертикальных звеньев кратчайшей ломанной будет равна Fy–Sy. Вычислим длины горизонтальных звеньев.
Будем строить кратчайшую ломанную следующим образом:
1) сначала если бегун левее первого препятствия, то он бежит вправо так, чтобы оказаться правее первого препятствия;
2) затем вверх, чтобы оказаться выше его, но ниже второго препятствия;
3) затем если бегун находиться правее второго препятствия, то он бежит влево, чтобы оказаться левее второго препятствия;
4) затем вверх, чтобы оказаться выше его, но ниже третьего препятствия;
5) затем если бегун находиться левее третьего препятствия, то он бежит вправо, чтобы оказаться правее второго препятствия;
6) затем вверх, чтобы оказаться на уровне с финишем;
7) затем бежит влево или вправо до финиша, если еще его не достиг.
Таким образом, у нас будет не более 4 горизонтальных звеньев. Длина первого звена будет равна  – Sx, если [x1]  – Sx > 0, т.е. если это звено будет присутствовать в ломанной. Длина второго горизонтального звена [x1]-[x2], если [x1]-[x2]> 0. Длина третьего [x3]-[x2],  если[x3]-[x2]  > 0. Длина четвертого [x3]-[Fx], если[x3]-[Fx] > 0.
Найдя суммарную длину горизонтальных звеньев и добавив длину вертикальных, получаем ответ задачи.
Рекомендации при проверке.
Если участник не учел, что сумма вертикальных звеньев равна Fy–Sy, то решение оценивается из 90 баллов.
Если участник находит вершины кратчайшей ломанной, а затем выполняет вычисление длины ее звеньев, то решение оценивается из 70 баллов.
Задача 3. Суперкомпьютер «Лобачевский»
За одну операцию рассылки нельзя отправить более чем N–1 пакетов. Суммарное время, затраченное на обработку 2*K пакетов равно 4*K+1 секунд. Таким образом, прежде чем выполнить операцию рассылки нужно определить, а будет ли полностью загружен первый процессор все это время. Например, если нам осталось обработать 5 пакетов, то оставить их все на обработку первому процессору займет 5 сек. Оставить на обработку 3 пакета, а 2 отправить в рассылку, займет также 5 сек. А отправлять в рассылку 4 пакета, а 1 пакет оставлять первому процессору невыгодно, т.к. это займет 9 сек суммарно.
Таким образом, для S оставшихся пакетов имеет смысл отправить в рассылку 2*K пакетов, где K = min{(N–1) div 2, (S–1) div 4}. Если одной рассылки недостаточно и у нас остались еще пакеты на обработку по прошествии 4*K+1 сек, т.е. S – 2*K – (4*K + 1) > 0, то мы должны снова выбрать стоит ли отправлять рассылку. Очевидно, что рассылку лучше делать с максимально возможным количеством пакетов. Процесс продолжается до тех пор, пока не закончатся пакеты.
Пусть рассылка по 2*((N–1) div 2) пакета была выполнена P раз. Тогда
P = S div (6*((N–1) div 2) + 1). После P рассылок пройдет P*(4*(N–1) div 2) + 1) сек и останется S0 = S mod (6*((N–1) div 2) + 1) пакетов. Общее время обработки данных будет равно P*(4*((N–1) div 2) + 1)+max{4*((S0–1) div 4)+1, S0–2*((S0–1) div 4)}.
Таким образом, оптимальный алгоритм решения состоит в вычислении P, S0 и затем вычислении итогового времени обработки данных по формуле указанной выше.
Рекомендации при проверке.
Если участник выбрал переборный алгоритм, то оценивать это решение нужно не более чем на 50 баллов.

Вы можете обсудить этот пост комментариях или в нашем чате, который находится в верхнем правом углу сайта. Если вы не знаете как общаться в чате, то скорее жмите СЮДА! Приятного Вам общения :)

Прокомментировать

Copyright © 2018 Урок информатики All rights reserved.
Тема доработана интернет студией SMOpro, специализация которой реклама в блогах.