Городская олимпиада, анализ

Автор: Опубликовано: Ноя 15, 2009 В рубрике: Олимпиада

Методические рекомендации и ответы к заданиям муниципального этапа всероссийской олимпиады школьников 2009-2010 учебного года по информатике

Задача A. Умные слоны

Решение:

Задача на динамическое программирование. Пусть слонов N штук.

Нужно отсортировать слонов по увеличению веса сохранив при этом начальную нумерацию слонов. Этого можно достичь путем хранения исходных номеров слонов в отдельном массиве Ind[1..N], в котором Ind[i] содержит исходный номер слона, который после сортировки по возрастанию веса оказался на i-м месте.

Будем называть подпоследовательность слонов подходящей, если в ней слоны расположены по возрастанию веса и при этом убыванию IQ.

Введем в рассмотрение массивы Pred[1..N], Count[1..N].

Count[k] – кол-во слонов в максимально длинной подходящей подпоследовательности слонов из множества первых k слонов, в которую входит слон с номером k.

Pred[k] – номер слона предшествующего k- ому в подпоследовательности максимальной длины.

Pred[k] = i, а i выбрано так, что Count[i]>=max Count[j], где 0<j<k и S[Ind[j]]>S[Ind[k]], т.е. IQ слона с номером k ниже его предшественника в последовательности с номером i. Если у слона с номером k IQ ниже чем у всех кто весит меньше его, то Pred[k]=0.

Count[k] = Count[Pred[k]] +1. Но если у слона с номером k IQ ниже чем у всех кто весит меньше его, то Count[k]=0.

Очевидно, что Pred[1] = 0, Count[1]=0  — решение, состоящее из одного слона, а следовательно перед ним нет ни одного слона.

После заполнения массивов Pred и Count необходимо найти число m – номер слона, для которого значение Count[m] максимально.

С помощью массивов Pred и Ind можно восстановить подпоследовательность, являющуюся решением задачи, например так:

write(Ind[m]);
i:=m;
while (Pred[i]>0) do
begin
write(Ind[Pred[i]]);
i := Pred[i];
end;

Задача B. Железные дороги

Решение:

Представим задачу в виде графа. Города – это вершины графа. Переезды между городами – дуги. Оптимальная структура данных, хранящая информацию о графе – список смежности.

Для решения эадачи можно использовать обход в глубину.

Пусть  Obhod(p, time) – процедура осуществляющая обход в глубину  из вершины p.

time, метка, которой помечается вершина с номером p, задает минимальное время за которое Боб может приехать в вершину p из начальной.

marks – массив меток. В начале работы алгоритма marks[i] = maxint для любого i.

ways[i, j].nextCity – город в который ‘прибывает’  j-я дуга из города i.

ways[i, j].t1 – “время отбытия” j-й дуги из города i.

ways[i, j].t2 – “время прибытия” j-й дуги в город ways[i,j].nextCity.

procedure Obhod(p, time : integer);

var I: Integer;

begin

marks[p] := time;

for i := 1; i <= “количество дуг исходящих из p“ do

if (ways[p,i].t1 >= time AND ways[p,i].t2 < marks[ways[p,i].nextCity]) then

Obhod(ways[p, i].nextCity, ways[p,i].t2);

end;

end;

Обход начинается из города A и его метка равна 0 :

Obhod(ACity, 0 );

marks[BCity] – задает минимальное время прибытия Боба

Задача C. Вырубка деревьев

Решение:

var

res, left, n, m: integer;

fIn, fOut : text;

begin

res := 0;

assign(fIn, ‘c.in’);

reset(fIn);

read(fIn, n);

read(fIn, m);

close (fIn);

assign(fOut, ‘c.out’);

rewrite(fOut);

if (m = 1) then write(fOut, n-1) else

begin

left := 1;

for left:=1 to n do

res := res + (n — left) div (m — 1);

write(fOut, res);

end;

close(fOut);

end.

Задача D. Треугольники

Решение:

Эту геометрическую задачу можно решить несколькими способами. Например, так:

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

2.     Проверим, лежит ли верхняя вершина нижнего треугольника выше основания верхнего. Если нет, то пересечение пусто.

3.     Найдем пересечение боковых сторон нижнего треугольника с основанием верхнего. Если их нет, то треугольники либо не пересекаются либо верхний находится внутри нижнего (это легко проверить по точкам пересечения продолжения основания верхнего треугольника и боковых сторон нижнего).

4.     Определим основание пересечения исходя из точек полученных в п.3.

5.     Найдем площадь равностороннего треугольника (пересечение исходных треугольников) по длине его основания.

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

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

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