AtCoder ABC #074 / ARC #083

arc083-a.rb

n = gets.chomp.to_i
a = gets.chomp.to_i
puts n * n - a

arc083-b.rb

n = gets.chomp.to_i
k = gets.chomp.to_i
x = gets.chomp.split(" ").map(&:to_i)
ans = 0
x.each do |i|
  ans += [i, k - i].min
end
puts ans * 2

arc083-c.rb

a, b, c, d, e, f = gets.chomp.split(" ").map(&:to_i)
na = f / (100 * a)
nb = f / (100 * b)
ans = []
0.upto(na) do |i|
  0.upto(nb) do |j|
    s = f - (100 * a * i + 100 * b * j)
    next if s < 0
    nc = s / c
    nd = s / d
    0.upto(nc) do |k|
      0.upto(nd) do |l|
        sugar =  c * k + d * l
        water = 100 * (a * i + b * j)
        if  sugar + water <= f && e * water >= 100 * sugar then
          ans << [sugar + water, sugar] if sugar + water != 0
        end
      end
    end
  end
end
puts ans.max_by{|x, y| y.to_f / x}.join(" ")

arc083-d.rb

# TLE
# https://beta.atcoder.jp/contests/abc074/submissions/1601175

n = gets.chomp.to_i
a = []
n.times do
  a << gets.chomp.split(" ").map(&:to_i)
end

n.times do |k|
  n.times do |i|
    n.times do |j|
      if a[i][k] + a[k][j] < a[i][j]
        puts -1
        exit
      end
    end
  end
end

flag = Array.new(n){Array.new(n, 1)}

n.times do |k|
  n.times do |i|
    n.times do |j|
      next if (i == j) || (j == k) || (k == i)
      if a[i][j] == a[i][k] + a[k][j] then
        flag[i][j] = 0
        flag[j][i] = 0
      end
    end
  end
end

ans = []
n.times do |i|
  ((i+1)...n).each do |j|
    ans << a[i][j] * flag[i][j]
  end
end

puts ans.inject(:+)