fork(1) download
  1. def f(t,l,r,arr)
  2. p [l,r]
  3. if l==r then
  4. return l
  5. end
  6. m=(l+r)/2
  7. t3=arr[m]-t
  8. p [m,t,t3]
  9. if t3<=0 then
  10. return f(t,l,m,arr)
  11. else
  12. return f(t,m+1,r,arr)
  13. end
  14. end
  15. n,p,q=gets.split(" ").map{|e| e.to_i}
  16. t=Rational(p, q+p)
  17. tA=[0]
  18. tB=[0]
  19. tAB=[0]
  20. n.times{|i|
  21. a,b=gets.split(" ").map{|e| e.to_i}
  22. tA<<tA[i]+a
  23. tB<<tB[i]+b
  24. tAB<<tAB[i]+a+b
  25. }
  26. arr=[]
  27. (1..n).each{|i|
  28. arr<<Rational(tA[i],tAB[i])
  29. }
  30. arr<<Rational(-1,1)
  31. arr<<Rational(10**18,1)
  32. arr=arr.sort.reverse
  33.  
  34. n.times{|i|
  35. t2=t
  36. if i>0 then
  37. t2+=Rational(tA[i],tAB[i])
  38. end
  39. p f(t2,0,n+1,arr)
  40. }
Success #stdin #stdout 0.01s 8088KB
stdin
5 1 3
3 9
1 2
4 6
1 5
5 3
stdout
[0, 6]
[3, (1/4), (5/124)]
[4, 6]
[5, (1/4), (0/1)]
[4, 5]
[4, (1/4), (1/60)]
[5, 5]
5
[0, 6]
[3, (1/2), (-13/62)]
[0, 3]
[1, (1/2), (-11/78)]
[0, 1]
[0, (1/2), (1999999999999999999/2)]
[1, 1]
1
[0, 6]
[3, (31/60), (-421/1860)]
[0, 3]
[1, (31/60), (-41/260)]
[0, 1]
[0, (31/60), (59999999999999999969/60)]
[1, 1]
1
[0, 6]
[3, (57/100), (-867/3100)]
[0, 3]
[1, (57/100), (-823/3900)]
[0, 1]
[0, (57/100), (99999999999999999943/100)]
[1, 1]
1
[0, 6]
[3, (67/124), (-1/4)]
[0, 3]
[1, (67/124), (-877/4836)]
[0, 1]
[0, (67/124), (123999999999999999933/124)]
[1, 1]
1