Submission #2972413


Source Code Expand

Copy
INF = 10**5

class MaxAvg

  attr :n,:k,:w,:v,:y

  def initialize(n,k,w,v)
    @n=n
    @k=k
    @w=w.dup
    @v=v.dup
  end

  def C(x)
    # @w = water
    # @p = concentration
    #  sigma (@w*@p/100) / sigma (@w)
    #  sigma (@w*@p/100) / sigma (@w) >= x
    #  sigma (@w*@p/100 - x*@w) >= 0
    y=[]
    for i in 0...@n
      y[i] = (@w[i].to_f*@v[i].to_f).quo(100).to_f - (x * @w[i].to_f).to_f
      #y[i] = @v[i].to_f - (x * @w[i].to_f).to_f
    end
    y=y.sort
    #p y

    sum=0.to_f
    for i in 0...@k
      sum+=y[@n-i-1]
    end

    return sum>=0, y
  end

  def solve()
    lb,ub=0.to_f,INF.to_f
    for i in 0..100
      mid = (lb+ub).quo(2).to_f
      result,y = C(mid)
      if result
        lb = mid
      else
        ub = mid
      end
    end
    # p lb
    # p ub

    #puts "%.9f" % y.select{|n| n < 0}.inject(&:+).abs
    puts "%.9f" % (ub * 100)
  end
end

lines = $stdin.read
array = lines.split("\n")
N,K = array[0].split(" ").map(&:to_i)
w,p = [],[]
array[1...N+1].each do |str|
  w << str.split(" ")[0].to_i
  p << str.split(" ")[1].to_i
end

MaxAvg.new(N,K,w,p).solve()

Submission Info

Submission Time
Task D - 食塩水
User hiroyuking
Language Ruby (2.3.3)
Score 100
Code Size 1170 Byte
Status
Exec Time 104 ms
Memory 4088 KB

Compile Error

./Main.rb:38: warning: assigned but unused variable - i
./Main.rb:40: warning: assigned but unused variable - y

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s0.txt, s1.txt
All 100 / 100 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, s0.txt, s1.txt
Case Name Status Exec Time Memory
000.txt 100 ms 3832 KB
001.txt 18 ms 2040 KB
002.txt 96 ms 3832 KB
003.txt 21 ms 4088 KB
004.txt 102 ms 3832 KB
005.txt 99 ms 3704 KB
006.txt 96 ms 3832 KB
007.txt 84 ms 3320 KB
008.txt 103 ms 3832 KB
009.txt 17 ms 2044 KB
010.txt 101 ms 3832 KB
011.txt 55 ms 2680 KB
012.txt 104 ms 3832 KB
013.txt 48 ms 2680 KB
014.txt 103 ms 3832 KB
015.txt 80 ms 3192 KB
016.txt 100 ms 3832 KB
017.txt 68 ms 3064 KB
018.txt 96 ms 3832 KB
019.txt 75 ms 3064 KB
s0.txt 7 ms 1788 KB
s1.txt 8 ms 1788 KB