fork download
  1. def f(t,t2,l,r,arr)
  2. tz=Rational(0,1)
  3. if l==r then
  4. t3=arr[l]-t2-t
  5. p t3
  6. if tz<=t3 then
  7. return l
  8. else
  9. return l+1
  10. end
  11. end
  12. m=(l+r)/2
  13. t3=arr[m]-t2
  14. p [0,l,r,m,t,t3]
  15. if t3<=tz then
  16. return f(t,t2,l,m,arr)
  17. end
  18. t3=t3-t
  19. p [t,t3]
  20. if t3<tz then
  21. return f(t,t2,l,m,arr)
  22. else
  23. return f(t,t2,m+1,r,arr)
  24. end
  25. end
  26. n,p,q=gets.split(" ").map{|e| e.to_i}
  27. t=Rational(p, q+p)
  28. tA=[0]
  29. tB=[0]
  30. tAB=[0]
  31. n.times{|i|
  32. a,b=gets.split(" ").map{|e| e.to_i}
  33. tA<<tA[i]+a
  34. tB<<tB[i]+b
  35. tAB<<tAB[i]+a+b
  36. }
  37. arr=[]
  38. (1..n).each{|i|
  39. arr<<Rational(tA[i],tAB[i])
  40. }
  41. arr=arr.sort.reverse
  42. ans=0
  43. n.times{|i|
  44. t2=Rational(0,1)
  45. if i>0 then
  46. t2=Rational(tA[i],tAB[i])
  47. end
  48. p f(t,t2,0,n-1,arr)
  49. }
  50. puts ans
Success #stdin #stdout 0.02s 8040KB
stdin
3 1 3
1 4
2 8
7 2
stdout
[0, 0, 2, 1, (1/4), (1/5)]
[(1/4), (-1/20)]
[0, 0, 1, 0, (1/4), (5/12)]
[(1/4), (1/6)]
(-1/20)
2
[0, 0, 2, 1, (1/4), (0/1)]
[0, 0, 1, 0, (1/4), (13/60)]
[(1/4), (-1/30)]
(-1/30)
1
[0, 0, 2, 1, (1/4), (0/1)]
[0, 0, 1, 0, (1/4), (13/60)]
[(1/4), (-1/30)]
(-1/30)
1
0