Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача 7 регионального этапа Всероссийской олимпиады школьников по информатике 2011/2012 учебного года (offline)

Задачу добавил: alef

Успешно сдано решений: 5

Космический кегельбан

Входной файл:  input.txt
Выходной файл:   output.txt
Ограничение по времени:    2 секунды
Ограничение по памяти:    256 мегабайт

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.
Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. В последнем n-м ряду стоит n кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке (0, 0). Центры кеглей во втором ряду находятся в точках
(–1, 1) и (1, 1). Таким образом, центры кеглей в i-м ряду находятся в точках с координатами (–(i – 1), i – 1), (–(i – 3), i – 1), …, (i – 1, i – 1).
Игра происходит следующим образом. Используется шар с радиусом q метров. Игрок выбирает начальное положение центра шара (xc, yc) и вектор направления движения шара (vx, vy). После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора (vx, vy). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.
На рисунке приведен пример расположения кеглей для r = 500, n = 4 и шара для q = 1000, xc = –2, yc = –2, vx = 1, vy = 1.

 
Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению (xc, yc) и вектору направления движения (vx, vy) определяет количество кеглей, сбитых шаром.

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

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (1 ≤ r ≤ 700, 1 ≤ n ≤ 200 000).
Вторая строка входного файла содержит целое число q (1 ≤ q ≤ 109).
Третья строка входного файла содержит два целых числа xc и yc, разделенных ровно одним пробелом (–106≤ xc ≤ 106, –106≤ yc , 1000×yc < –(r + q) ).
Четвертая строка входного файла содержит два целых числа vx и vy, разделенных ровно одним пробелом (–106≤ vx ≤ 106, 0 < vy ≤ 106).

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

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

Пример входного файла
500 4
1000
-2 -2
1 1
   

Пример выходного файла
7

Пояснения к примеру
Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).
 


Система оценивания
Правильные решения для тестов, в которых 1 ≤ n ≤ 1000 и vx = 0, будут оцениваться из 20 баллов.
Правильные решения для тестов, в которых 1 ≤ n ≤ 1000 и vx ≠ 0, будут оцениваться еще из 20 баллов.
Правильные решения для тестов, в которых 1000 < n ≤ 200 000 и vx = 0, будут оцениваться еще из 20 баллов.
Чтобы получить оставшиеся 40 баллов, решение должно правильно работать также для тестов, в которых 1000 < n ≤ 200 000 и vx ≠ 0.
 

Сдать задачу

Задать вопрос жюри по этой задаче