Хочу рассказать как я решал задачу на сегодняшнем контесте.
Что бы уравнение имело хотя бы один корень, дискриминант должен быть не меньше 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
Прилагаю картинки для лучшего понимания
Спасибо, именно эти картинки я и нарисовал когда думал над решением. Ещё нужно не забыть про вырожденные случаи a == 0 или b == 0.
Извиняюсь, я начал ветвь дискуссии, забыв переключиться на english, поэтому всё равно она не видна англоязычным читателям. В общем местами нужно поменять последние два кейса. Если b == 0, то не важно чему равно a, всё равно результат равен единице, на втором шаге нужно проанализировать случай a == 0 && b != 0. И потом все остальные.
А меня такого не научили ни в школе, ни (пока) на матанализе. Но зато на матанализе научили интегрировать - и я здесь взялся за интегрирование... А уже после интегрирования додумался до того, что действительно выходит вот такое решение - надо было только немного подумать, а не лезть сразу в интегрирование.
В школе мало чему учат, однако это не мешает школьникам решать задачи не хуже многих студентов:)
Я(школьник), например, решил.
Codeforces Beta Round #69 (Div. 1 Only) Problem B
Codeforces Beta Round #69 (Div. 2 Only) Problem D
this is better :D
possibility = 1/2 + 1/2 * (1/2 * a/4b)
Если a > 4b, рассуждения аналогичны предыдущим. Выбираем максимальный равный отрезок, который теперь будет [0, 4b], а вероятность попадания в него есть 4b/a. В данном случае надо рассмотреть оставшийся отрезок, вероятность попадания в него есть (a - 4b)/a (в таком случае p >= q выполняется всегда). Получаем формулу:
possibility = 1/2 + 1/2 * (1/2 * 4b/a + (a - 4b)/a)
Формулу нужно упростить, чтобы не было деления на а.
P.S. "Premature optimization is the root of all evil in programming."
Студентам, возможно, и очевидно,если они сталкивались с подобными вещами.
Школьникам - нет.
can't we solve this problem by following method ? for a given p we can have any q from -b to p/4. Therefore this length can be written as :- f(x) = b + x/4 we can integrate f(x) from 0 to a g(a)-g(0)=b*a-a*a/8 and the total number of ways to choose two numbers will be a*2b so probability is = ( g(a)-g(0) ) / 2ab But this is giving WA code
Yes you can my dear :) if you wait another 4 years, there will be some sort of method named solve, which solves this problem without any code :)
good contest