Гуровиц Владимир Михайлович Кротков Павел Андреевич

Скачать 62.35 Kb.

Название	Гуровиц Владимир Михайлович Кротков Павел Андреевич
Дата публикации	05.07.2013
Размер	62.35 Kb.
Тип	Документы

100-bal.ru > Спорт > Документы

Гуровиц Владимир Михайлович

Кротков Павел Андреевич

Станкевич Андрей Сергеевич

Ульянцев Владимир Игоревич

ОЛИМПИАДНЫЕ ЗАДАЧИ ПО ИНФОРМАТИКЕ И ПРОГРАММИРОВАНИЮ

Этой статьей мы продолжаем цикл публикаций олимпиадных задач для школьников по информатике. Решение таких задач и изучение разборов поможет Вам повысить уровень практических навыков программирования и подготовиться к олимпиадам по информатике.

В этой статье рассматривается задача «Космический кегельбан», которая предлагалась на региональном этапе Всероссийской олимпиады школьников по информатике в 2011/2012 учебном году. Материалы этой олимпиады можно найти на сайте http://neerc.ifmo.ru/school/spb/.

Условие задачи

Рассмотрим игру «Космический кегельбан», поле для которой представляет собой бесконечную плоскость, на которой расставлены кегли. Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые и расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. Так, в последнем ряду стоит n кеглей.

Введем на плоскости систему координат с единицей измерения, равной одному километру. Центр единственной кегли в первом ряду находится в точке

, во втором ряду центры кегель находятся в точках

, и так далее. Так, центры кеглей в i-м ряду находятся в точках с координатами

, …,

.

В игре используется шар радиуса q метров. Игрок выбирает начальное положение центра шара

и вектор направления движения шара

. После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора

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

На рисунке приведен пример расположения кеглей и шара при

Требуется написать программу, которая по заданным радиусу кегли

количеству рядов кеглей

радиусу шара

, его начальному положению

и вектору направления движения

определяет количество кеглей, сбитых шаром.

Формат входного файла

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (

) – радиус одной кегли в метрах и количество рядов кегель, соответственно.

Вторая строка входного файла содержит целое число q (

) – радиус шара в метрах.

Третья строка входного файла содержит два целых числа

, разделенных ровно одним пробелом

) – координаты центра шара в километрах.

Четвертая строка входного файла содержит два целых числа

, разделенных ровно одним пробелом

) – координаты вектора скорости шара в километрах.

Формат выходного файла

Выходной файл должен содержать одно целое число — количество сбитых кеглей.

Примеры входных и выходных данных

spacepin.in	spacepin.out
500 4 1000 -2 -2 1 1	7

Пояснение к примеру

На рисунке ниже изображено, какие кегли будут сбиты (такие кегли обозначены «х»).

Разбор задачи

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

Заменим окружности на точки, а полосу ширины 2q на полосу ширины 2(q + r). Тогда задача сведется к эквивалентной: сколько точек (центров кеглей) лежат в расширенной полосе, то есть находятся на расстоянии не более (q + r) от прямой, по которой движется центр шара. Заметим, что, поскольку по условию задачи каждая точка шара лежит изначально ниже любой точки каждой кегли, можно рассматривать не часть полосы выше шара, а всю полосу: на ответ это не повлияет.

Запишем неравенством условие принадлежности точки полосе. Обозначим точкой C начальное положение центра шара, вектором CB его скорость (v_x, v_y), а точкой P – центр некоторой кегли.

Тогда расстояние от точки P до прямой CB равно

где квадратными скобками обозначено псевдоскалярное произведение векторов [1], а условие принадлежности точки полосе запишется так:

Проверим отдельно принадлежность центра P(x_p, y_p) некоторой кегли нашей полосе. Для этого запишем полученное выше неравенство в координатах:

Теперь можно перебрать все кегли и для каждой проверить, выполняется ли это неравенство. Приведем фрагмент решения на языке Pascal, выполняющий эту проверку:

Листинг 1. Фрагмент решения, рассматривающего каждую кеглю
answer := 0;

len := sqrt(vx * vx + vy * vy);

for yp := 0 to (n - 1) do begin

xp := -yp;

while (xp <= yp) do begin

vec_mul = (xp - xc) * vy - (yp - yc) * vx;

if abs(vec_mul) / len < q + r then

answer := answer + 1;

xp := xp + 2;

end;

end;

Асимптотическое время работы такого решения равно

, так как всего кегель

. Такое решение не укладывается в ограничения по времени работы персонального компьютера при указанном ограничении на n.

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

относительно x_p для каждого значения y_p – ординаты рассматриваемого ряда кегель. Данное неравенство является квадратичным, и его решением является отрезок с концами

где

Теперь нам необходимо найти абсциссы центров самой левой и самой правой кегли, находящихся внутри этого отрезка, – left и right. Способ вычисления этих значений приведен в листинге 2. Теперь количество сбитых кегель в горизонтальном ряду равно

. Взятие максимума необходимо, так как в процессе вычисления

может оказаться, что

. В этом случае шар не сбивает ни одной кегли в данном ряду.
Приведем соответствующий фрагмент программы на языке Pascal:

Листинг 2. Фрагмент корректного решения задачи
k := vx / vy;

c := (q + r) / 1000 * sqrt(vx * vx + vy * vy) / vy;

for yp := 0 to n – 1 do begin

l := k * (yp – y) – c + x;

r := k * (yp - y) + c + x;
left := ceil(l);

right := floor(r);
if (abs(left) mod 2 <> yp mod 2) then

inc(left);

if (abs(right) mod 2 <> yp mod 2) then

dec(right);
left:= max(left, -yp);

right:= min(right, yp);
answer := answer + max(0, (right – left) div 2 + 1);

end;

Источник

[1] Андреева Е.В., Егоров Ю.Е. Вычислительная геометрия на плоскости / Информатика. 2002. №39, с. 26 – 29.
Информация об авторах

Гуровиц Владимир Михайлович – учитель информатики Московской ФМШ №2007, методист Лаборатории дистанционных технологий работы с одаренными детьми Московского института открытого образования, член жюри ВКОШП

Кротков Павел Андреевич – студент второго курса кафедры «Компьютерные технологии» НИУ ИТМО, член жюри Интернет-олимпиад по информатике

Станкевич Андрей Сергеевич – кандидат технических наук, доцент кафедры «Компьютерные технологии» НИУ ИТМО, председатель научного комитета Всероссийской олимпиады школьников по информатике, председатель жюри ВКОШП

Ульянцев Владимир Игоревич – студент пятого курса кафедры «Компьютерные технологии» НИУ ИТМО, член жюри Интернет-олимпиад по информатике, член жюри ВКОШП

Добавить документ в свой блог или на сайт

Похожие:

	Рабочая программы дисциплины Теория волн Лекторы ...		Владимир Андреевич Мезенцев Чудеса: Популярная энциклопедия. Том 1 Работа выполнена при поддержке ргнф, проект 06-06-00449а «Структура и диагностика личностного потенциала»
	Исследовательская работа «Человек и электричество» Кузнецов Владимир... Исследование влияния различных факторов на сопротивление тела человека		Вестник Санкт-Петербургского университета Серия «Математика, механика, астрономия» ГелигА. Х., Ибрагимов И. А., Леонов Г. А., Матвеев А. С., Морозов Н. Ф., Плисс В. А., Шепелявый А. И. Владимир Андреевич Якубович...
	Программа курса «глобальная безопасность» Программу курса разработал Кулагин Владимир Михайлович, кандидат исторических наук, доцент		Разработчики издания Главный редактор розинов владимир Михайлович, доктор медицинских наук, профессор, заместитель директора Московского нии педиатрии...
	Павел Михайлович Влияние моделирования эффектов микрогравитации на... Работа выполнена в Учреждении Российской академии наук Государственном научном центре Российской Федерации – Институте медико-биологических...		Среди строительных организаций «Элита строительного комплекса России»... Генеральный директор ОАО «внипинефть» капустин владимир Михайлович награждается орденом российского Союза строителей «за заслуги...
	Владимир Андреевич Мезенцев Чудеса: Популярная энциклопедия. Том 2 Полтора месяца длится война, но сколько горя и слез уже принесла она. И сколько еще принесет. Фашистский сапог топчет землю Прибалтики,...		Программа по формированию навыков безопасного поведения на дорогах... Компании Распадская. В соревнованиях принимали участие сильнейшие спортсмены сибирского региона. Воспитанник спортивной школы города...
	Реферат Вячеслав Геннадьевич, Богославский Дмитрий Дмитриевич, Бодягин Владимир Михайлович, Бодягин Андрей Владимирович, Волков Сергей Денисович,...		Программа по формированию навыков безопасного поведения на дорогах... Младшеклассники были достаточно хорошо подготовлены к урокам и проблем с дисциплиной не было, несмотря на то, что учителя практически...
	37. Личность императора Николая 1 Заговорщики ворвались в спальню Павла и потребовали, чтобы он подписал акт об отречении. Павел отказался. Началась перепалка, и Павел...		26. Мельников Федор Михайлович Мельников Федор Михайлович родился 31 июля 1942 года в дер. Остречиха Сандовского района Калининской области
	Вячеслав Андреевич Майер. Чешежопица Вячеслав Андреевич Майер (Некрас Рыжий). Чешежопица		Анализ преподавателя обж моу «Глубоковская средняя общеобразовательная... Я, Дзюбло Андрей Андреевич, закончил в 1989 году бгпи, факультет физического воспитания и отделения начальной военной подготовки....

Школьные материалы