Школьные олимпиады Калининградской области
Олимпиады
Поиск
Эксперты
Вопросы и ответы
Ссылки
Контакты
Английский язык =
Астрономия =
Биология =
География =
Информатика и ИКТ =
Искусство (мировая художественная культура) =
Испанский язык =
История =
Китайский язык =
Литература =
Математика =
Немецкий язык =
Обществознание =
Основы безопасности жизнедеятельности =
Основы православной культуры =
Право =
Русский язык =
Технология (девушки) =
Технология (юноши) =
Физика =
Физкультура (девушки) =
Физкультура (юноши) =
Французский язык =
Химия =
Экология =
Экономика =
Нормативная база
Анонсы новостей

Предварительные результаты регионального этапа олимпиады по ОБЖ
15.02.2019

Результаты по экологии обновлены с учетом рассмотренных апелляций
15.02.2019

Результаты по математике и обществознанию обновлены с учетом рассмотренных апелляций
14.02.2019

Вопросы и ответы

Раздел:

Уважаемые посетители! В связи с проведением работ по модернизации форума, его работа приостанавливается с 15.03.2010 г. по 29.03.2010 г. Приносим свои извинения за временные неудобства.

Вопрос:
Я имел ввиду, что ответ получится неправильный, ведь я представлял там, что T(34)=T(4), там ответ был 3, а должен 5 Влад [10.02.2009]

Ответ:
Да, правильно, T(34)=2. Теперь можете закодировать решение задачи 7. Только не забудьте описать динамическую таблицу на 1 больше, чем максимальное n, и сразу присвоить T(n+1)=1.

Вопрос:
T(34)=T(4)+T( )? или как это записать, ведь 34 можно 3 4 и 34, т.е. мои предыдущие соображения неверны. Влад [10.02.2009]

Ответ:
Почему не верны? T(34)=T(4)+T() - правильно, T() - ответ для пустой последовательности, всегда равный единице. Можно считать, что T(4) = T() или что T(4) = 1. Но первый способ проще, так как C может быть, например, 3, и тогда T(4) = 0, а T() = 1 при любом C.

Вопрос:
То есть в конце всех вычислений получится одна и та же величина:
T(01234), где C=100
-------------------------
T(01234)=T(1234)=T(234)+T(34)+T(4)=T(34)+T(4)+T(4)+T(4)=T(4)*4=1*4=4, всё ли я правильно понял? Влад [10.02.2009]

Ответ:
Да, в листьях дерева рекурсии всегда будет одно и то же. Насчёт ответа не знаю, считать ленюсь, да и не надо.
Важно вот что. Можно решить задачу перебором, многократно вычисляя одно и то же. Такое решение не пройдёт по времени. Динамическое же программирование гарантирует, что любая подзадача будет решаться не более одного раза. В этом вся суть и состоит. Динамическое программирование - это перебор с однократным решением подзадач. Результаты запоминаются в динамической таблице. Как видите, всё совсем просто :)

Вопрос:
напишите разбор решения задачи "Трамвай", который набирает 100 баллов Боголюбский Алексей [09.02.2009]

Ответ:
Это за один раз не получится. Ответ на этом сайте не более 1К. Так что, постигнув порцию информации, запрашивайте следующую.
1 серия. "Кумулятивное дерево".
Пусть мы имеем числовой массив длиной N = 2^K (степень двойки!). Элементы массива являются листьями дерева. каждая пара соседних листьев имеет предка, в котором записана сумма чисел из этих листьев. Т.о. мы имеем N/2 вершин второго уровня - предков листьев. Каждая пара соседних вершин второго уровня также имеет общего предка - вершину третьего уровня т т.д. Всего получится N-1 дополнительных вершин. Самая верхняя вершина называется корнем дерева, и в ней записана сумма всех чисел массива. Такая структура называется кумулятивное дерево или дерево отрезков или дерево интервалов. Как реализовать в программе - в следующей серии. Пока научитесь за логарифмическое время выполнять две операции: CHANGE(v,d) - изменить значение листа v на d; и SUM(v) - найти сумму чисел, записанных в листьях от первого до v-го включительно.

Вопрос:
А для чего нужна динамика в 7-ой задаче, как надо её здесь использовать? Ghost [08.02.2009]

Ответ:
Жюри не нашло никакого решения, кроме динамического. Если оно Вам известно, сообщите.
Теперь о динамическом решении. Пусть вход таков:
последовательность="0123004567" и C=200. Обозначим T(0123004567) искомую величину. Посмотрим, как могла получиться данная последовательность: первое число только 0 => T(0123004567)=T(123004567). Второе число могло быть 1 или 12 или 123 => T(123004567)=T(23004567)+T(3004567)+T(004567). Аналогично T(23004567)=T(3004567)+T(004567), T(3004567)=T(004567)+T(04567), T(004567)=T(04567). И так далее. То есть решение некоторой подзадачи выражается через решение меньших подзадач. Опишем динамическую таблицу T[1..50001]. Индекс ячейки - это номер цифры, с которой начинается подпоследовательность. Положим T[n+1]=1. Теперь будем последовательно вычислять T[i] для i=n,n-1,...,1. T[1] и будет ответом.

Вопрос:
Напишите, пожалуйста, разбор задачи "Трамвай". Боголюбский Алексей [08.02.2009]

Ответ:
Задача "Трамвай" предполагала два решения: медленное, набирающее 80 баллов, и быстрое, набирающее 100 баллов. Излагаю медленное решение. Быстрое решение будет в следующих сериях (Вы должны будете прислать вопрос).
Максимальная сумма складывается из базовой части S(b[i]*(d[i]-c[i])) и "бонусной" части, которую дают сидящие пассажиры. Здесь буква S используется вместо греческой "сигма". Базовую часть целесообразно посчитать сразу при вводе, а пассажиров, у которых b[i]>=a[i] вообще не запоминать, они никакого бонуса не дадут. Для остальных пассажиров не надо хранить отдельно a[i], b[i], а лишь e[i]=a[i]-b[i].
После ввода сортируем пассажиров по убыванию e[i].
Описываем и зануляем массив v[i] длиной 10^5, v[i]=0 означает, что i-й пассажир на улице, а v[i]=1 - в трамвае.
В цикле по остановкам:
1)Единичим v[i] для всех вошедших пассажиров, нулим v[i] для вышедших пассажиров.
2)Прибавляем к максимальной сумме e[i] первых M пассажиров из едущих в трамвае (если едет меньше М, то всех едущих).

Вопрос:
Здравствуйте.
дайте пожалуйста ссылки на динамические задачи с разбором или приведите примеры задач сами. Ghost [06.02.2009]

Ответ:
Владислав! Вы хотите освоить динамическое программирование - это похвально, да и пора уже. Но Вы напрасно надеетесь сделать это, прочитав какой-нибудь учебник. Программирование - вообще магия, а динамика - магия в квадрате. Научиться решать динамические задачи, можно только решая динамические задачи, всё более и более трудные. В региональном этапе было две динамических задачи - 7 (очень простая) и 8 (трудная). Простая динамика была в муниципальном этапе. Давайте попробуем начать с задачи 7. Пишите на этот сайт, м.б. ещё кто-то прочитает.

Вопрос:
Можете сказать, есть ли в нашем городе курсы по подготовке к олимпиадам? Или какие-либо заочные курсы? Боголюбский Алексей [30.01.2009]

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

Вопрос:
Объясните пожалуйста алгоритм решения задачи 'Газон'. Кроме того, что можно разбирать точки на данном прямоугольнике и прямоугольнике, описанном около окружности не вижу других способов. Sky_Net [30.01.2009]

Ответ:
Для каждого y от y3-r до y3+r, если y1 <= y <=y2, вычисляем (согласно уравнению окружности) x_min и x_max - минимальную и максимальную целочисленную координату точки внутри круга. Получаем отрезок [x_min,x_max], находим его пересечение с [x1,x2] и длину этого пересечения прибавляем к счётчику.

Вопрос:
Извините, можете подсказать, в задаче "трамвай" ведь нельзя устроить цикл по останокам и в этом цикле для каждого пассажира рассматривать сидит или стоит он? Такое решение просто не успеет. Если я правильно понял разбор, то надо рассматривать для каждого пассажира его промежуток на котором он едет и рассматривать какое удовлитворение для этого пассажира, но как определить меняет ли он свое положение (садится,встает) на этом промежутке? Каждый раз сортировать других людей? Боголюбский Алексей [27.01.2009]

Ответ:
Почему же, цикл по остановкам в правильном решении есть. Нужно только обработать всех пассажиров на каждой остановке за логарифмическое время, чтобы суммарная сложность была меньше n^2. Если использовать кумулятивные деревья и бисекцию, можно получить сложность n*(log n)^2. Если на каждой остановке сортировать пассажиров, получится не менее n^2*log n, это не пройдёт по времени. Есть и другие варианты правильного решения, так Липовский использовал сбалансированные деревья поиска.

 

Всего страниц 7: (..) 6 7

Предыдущая | Следующая

 

Центр информатизации и технического творчества

Поиск | Эксперты | Вопросы и ответы | Ссылки | Контакты

2002-2007 © Калининградское областное государственное образовательное учреждение дополнительного образования детей.
Калининградский областной центр информатизации и технического творчества.
При публикации любых материалов ссылка на сайт обязательна.