parrot-studio/poh_kirishima.rb

## poh_kirishima.rb
# 再帰的探査
def search(list, i, need, nco, maxind, mincost, limit_mem)
  c = list[i]
  nmem = need - c[0]
  cost = nco + c[1]

  return mincost if cost > mincost # すでにわかっている答えより大きいので無駄
  return cost if nmem <= 0 # メンバーが埋まった
  return mincost if i >= maxind # 終端までいったが、メンバーが埋まらない
  # 自身の効率*残り人数＋現在のcostがmincostを超える
  return mincost if (cost + c.last * nmem >= mincost)

  # 自分よりindexが大きいものから探査したcostの最小値
  min = mincost
  ((i+1)..maxind).each do |ind|
    # これ以上先に満たせるだけのメンバーがいない
    break if nmem > limit_mem[ind]
    rsl = search(list, ind, nmem, cost, maxind, min, limit_mem)
    min = rsl if rsl < min
  end
  min
end

member = gets.to_i
size = gets.to_i
companys = []
ans = nil
tcos = 0 # total cost

size.times do
  ds = gets.split(' ').map(&:to_i)
  if ds.first >= member
    ans = ds.last if (ans.nil? || ans > ds.last)
  else
    mem = ds.first
    cos = ds.last
    companys << [mem, cos, (cos.to_f / mem)]
    tcos += cos
  end
end
(puts ans; exit) if companys.empty?
ans ||= tcos
(puts ans; exit) if ans < tcos

companys.sort_by!{|c| c.last}
maxind = companys.size - 1

# あるindexまでのメンバー数
limit_mem = {}
lm = 0
limitind = nil
maxind.downto(0) do |i|
  lm += companys[i].first
  limit_mem[i] = lm
  limitind = i if (limitind.nil? && lm > member)
end

ratio = ans.to_f / member
(0..limitind).each do |i|
  break if companys[i].last > ratio
  cost = search(companys, i, member, 0, maxind, ans, limit_mem)
  next if cost >= ans
  ans = cost
  ratio = ans.to_f / member
end

puts ans

exit
	# 再帰的探査
	def search(list, i, need, nco, maxind, mincost, limit_mem)
	c = list[i]
	nmem = need - c[0]
	cost = nco + c[1]

	return mincost if cost > mincost # すでにわかっている答えより大きいので無駄
	return cost if nmem <= 0 # メンバーが埋まった
	return mincost if i >= maxind # 終端までいったが、メンバーが埋まらない
	# 自身の効率*残り人数＋現在のcostがmincostを超える
	return mincost if (cost + c.last * nmem >= mincost)

	# 自分よりindexが大きいものから探査したcostの最小値
	min = mincost
	((i+1)..maxind).each do \|ind\|
	# これ以上先に満たせるだけのメンバーがいない
	break if nmem > limit_mem[ind]
	rsl = search(list, ind, nmem, cost, maxind, min, limit_mem)
	min = rsl if rsl < min
	end
	min
	end

	member = gets.to_i
	size = gets.to_i
	companys = []
	ans = nil
	tcos = 0 # total cost

	size.times do
	ds = gets.split(' ').map(&:to_i)
	if ds.first >= member
	ans = ds.last if (ans.nil? \|\| ans > ds.last)
	else
	mem = ds.first
	cos = ds.last
	companys << [mem, cos, (cos.to_f / mem)]
	tcos += cos
	end
	end
	(puts ans; exit) if companys.empty?
	ans \|\|= tcos
	(puts ans; exit) if ans < tcos

	companys.sort_by!{\|c\| c.last}
	maxind = companys.size - 1

	# あるindexまでのメンバー数
	limit_mem = {}
	lm = 0
	limitind = nil
	maxind.downto(0) do \|i\|
	lm += companys[i].first
	limit_mem[i] = lm
	limitind = i if (limitind.nil? && lm > member)
	end

	ratio = ans.to_f / member
	(0..limitind).each do \|i\|
	break if companys[i].last > ratio
	cost = search(companys, i, member, 0, maxind, ans, limit_mem)
	next if cost >= ans
	ans = cost
	ratio = ans.to_f / member
	end

	puts ans

	exit
No results found