START_TIME = Time.utc.to_unix_ms TL = 1900 N = 50 K = 50 RND = Random.new(2) macro debug(msg) {% if flag?(:local) %} STDERR.puts({{msg}}) {% end %} end class Result getter :score, :b, :m, :e def initialize(@score : Int64, @b : Array(Int32), @m : Array(Int32), @e : Array(Int32)) end end class Solver @ts : Array(Int32) @us : Array(Int32) def initialize read_line @ts = read_line.split.map(&.to_i) @us = read_line.split.map(&.to_i) @b = Array(Int32).new(N) { RND.rand(1) + 1 } @m = Array(Int32).new(N) { |i| {RND.rand(2) + 1, @b[i]}.min } @e = Array(Int32).new(N) { RND.rand(2) + 1 } @pos_200 = Array(Int32).new(N, 0) @dir_200 = Array(Int32).new(N, 1) N.times do |i| @pos_200[i], @dir_200[i] = sim_200(@b[i], @m[i], @e[i]) end @pos_ts = Array(Array(Int32)).new(N) { Array.new(K, 0) } @pos_us = Array(Array(Int32)).new(N) { Array.new(K, 0) } N.times do |i| sim_k(i) end end def sim_200(b, m, e) m = {b, m}.min p = 0 d = 1 a = b 200.times do p += d if p == a * d d *= -1 a = {m, a - e}.max end end return p, d end def sim_k(i) K.times do |j| t = (@ts[j] - 200) % (@m[i] * 4) p = @pos_200[i] d = @dir_200[i] t.times do p += d if p == @m[i] * d d *= -1 end end @pos_ts[i][j] = p t = (@us[j] - 200) % (@m[i] * 4) p = @pos_200[i] d = @dir_200[i] t.times do p += d if p == @m[i] * d d *= -1 end end @pos_us[i][j] = p end end def solve best_res = Result.new(calc_score(), @b.dup, @m.dup, @e.dup) cur_score = best_res.score buf_pos_ts = Array.new(K, 0) buf_pos_us = Array.new(K, 0) initial_cooler = 1e-15 final_cooler = 4e-15 cooler = initial_cooler turn = 0 begin_time = Time.utc.to_unix_ms total_time = TL - (begin_time - START_TIME) while true turn += 1 if (turn & 0x3F) == 0 elapsed = Time.utc.to_unix_ms - begin_time if elapsed > total_time debug("total_turn:#{turn} score:#{best_res.score}") break end ratio = elapsed / total_time cooler = Math.exp(Math.log(initial_cooler) * (1.0 - ratio) + Math.log(final_cooler) * ratio) end ch_i = RND.rand(N) nb = RND.rand(13) + 1 nm = {RND.rand(13) + 1, nb}.min ne = RND.rand(2) + 1 old = {@pos_200[ch_i], @dir_200[ch_i]} @pos_200[ch_i], @dir_200[ch_i] = sim_200(nb, nm, ne) K.times do |i| buf_pos_ts[i] = @pos_ts[ch_i][i] buf_pos_us[i] = @pos_us[ch_i][i] end sim_k(ch_i) score = calc_score() if accept(score - cur_score, cooler) debug("score:#{score} at turn #{turn}") cur_score = score @b[ch_i] = nb @m[ch_i] = nm @e[ch_i] = ne if best_res.score < score best_res = Result.new(score, @b.dup, @m.dup, @e.dup) end else @pos_200[ch_i] = old[0] @dir_200[ch_i] = old[1] K.times do |i| @pos_ts[ch_i][i] = buf_pos_ts[i] @pos_us[ch_i][i] = buf_pos_us[i] end end end return best_res end def accept(diff, cooler) return true if diff >= 0 v = cooler * diff return false if v < -8 return RND.rand < Math.exp(v) end def calc_score sum0 = 0i64 sum1 = 0i64 K.times do |i| sum = 0.0 N.times do |j| j.times do |k| sum += (@pos_ts[j][i] - @pos_ts[k][i]).abs / (@b[j] + @b[k]) end end sum0 += (sum * 20_000_000 / (N * (N - 1))).round.to_i min = 1 << 20 max = -(1 << 20) N.times do |j| min = {min, @pos_us[j][i]}.min max = {max, @pos_us[j][i]}.max end sum1 += (10_000_000 / (((max - min) * 0.05) ** 0.5 + 1)).round.to_i end # debug([sum0, sum1, sum0 * sum1]) return sum0 * sum1 end end solver = Solver.new res = solver.solve N.times do |i| puts "#{res.b[i]} #{{res.b[i], res.m[i]}.min} #{res.e[i]}" end