Блог пользователя andryk

Автор andryk, 12 лет назад, По-русски

Собственно куда копать и что читать?

http://acm.hnu.cn/online/?action=problem&type=show&id=12284&courseid=0

http://acm.hnu.cn/online/?action=problem&type=show&id=12285&courseid=0

P.S. Нашел задачи на другом сайте. e-olimp выдает 403

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор andryk, 13 лет назад, По-русски
Хочу рассказать как я решал задачу на сегодняшнем контесте.

Что бы уравнение имело хотя бы один корень, дискриминант должен быть не меньше 0.
Получаем
p - 4q >= 0
p >= 4q

Что такое вероятность? Это отношения положительных событий ко всем. В данном случае положительное событие - такая пара (p,q) для которой p >= 4q .
А все события? Это все возможные пары (p, q). Так как числа выбираются на промежутке и могут быть действительными, таких пар существует бесконечное количество. Как же их подсчитать?
Вспомним что такое декартово произведение. Это как раз множество всех таких пар. И главное, что такое произведение можно изобразить как прямоугольник в системе координат x,y, где по оси x - отрезок [-b,b], а по оси y - [0,a].
Тогда его площадь - величина всех возможных пар (p,q)
Тогда искомая нами площадь - та часть прямоугольника, для которой выполняется p >= 4q
Что бы найти ее, проведем прямую y = 4x, нужная нам фигура будет находится выше этой прямой.
Таким образом ответ - отношение площади найденной фигуры ко всей фигуре.
Ну а площадь фигур думаю найти труда не составит.
Только не забудьте учесть еще один вариант, когда 4b < a.
А также два особых случая когда a = 0,  а также когда b = 0.
При a = 0, останется только правая часть графика, что даст нам вероятность 0.5.
При b = 0, любые p будут больше за 4q, поэтому вероятность 1.0

Прилагаю картинки для лучшего понимания

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 69 (Div. 1 Only)
Разбор задач Codeforces Beta Round 69 (Div. 2 Only)
  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится