AtCoder Regular Contest 015

Submission #1098193

Source codeソースコード

# gets.chomp.to_i
# gets.chomp.split(" ").map(&:to_i)
# gets.chomp.split(" ").map{|x| x.to_i}

n = gets.chomp.to_i
large = Array.new(n)
small = Array.new(n)
m = Array.new(n)

unit_id = {}
v_units = []

for i in 0...n
  a, b, c = gets.chomp.split(" ")
  large[i] = a 
  small[i] = c
  m[i] = b.to_i
  if unit_id[large[i]] == nil
    unit_id[large[i]] = unit_id.size
    v_units.push(large[i])
  end
  if unit_id[small[i]] == nil
    unit_id[small[i]] = unit_id.size
    v_units.push(small[i])
  end
end

unit_num = v_units.size

g = Array.new(unit_num){ Array.new() }
for i in 0...n
  g[unit_id[large[i]]].push([Rational(m[i], 1), unit_id[small[i]]])
  g[unit_id[small[i]]].push([Rational(1, m[i]), unit_id[large[i]]])
end

ratio = Array.new(unit_num)
ratio[0] = Rational(1, 1)

reached = Array.new(unit_num, false)
reached[0] = true

stack = [0]
while !(stack.empty?)
  u = stack.pop
  for ar in g[u]
    v = ar[1]
    if reached[v]
      next
    end
    ratio[v] = ratio[u] * ar[0]
    stack.push(v)
    reached[v] = true
  end
end

biggest = 0
smallest = 0

for i in 0...unit_num
  if ratio[i] < ratio[biggest]
    biggest = i
  end
  if ratio[i] > ratio[smallest]
    smallest = i
  end
end

ans = ratio[smallest] / ratio[biggest]
printf("1%s=%d%s\n", v_units[biggest], Integer(ans), v_units[smallest])

Submission

Task問題 C - 変わった単位
User nameユーザ名 mu
Created time投稿日時
Language言語 Ruby (1.9.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 1378 Byte
File nameファイル名
Exec time実行時間 38 ms
Memory usageメモリ使用量 3568 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,chokudai_solo_01.txt,chokudai_solo_02.txt,chokudai_solo_03.txt,chokudai_vs_cucumber_01.txt,chokudai_vs_cucumber_02.txt,chokudai_vs_cucumber_03.txt,chokudai_vs_cucumber_04.txt,chokudai_vs_cucumber_05.txt,chokudai_vs_kensho_01.txt,chokudai_vs_kensho_02.txt,chokudai_vs_kensho_03.txt,chokudai_vs_kensho_04.txt,chokudai_vs_kensho_05.txt,chokudai_vs_kensho_06.txt,chokudai_vs_kensho_07.txt,chokudai_vs_kensho_08.txt,chokudai_vs_kensho_09.txt,chokudai_vs_laycurse_01.txt,chokudai_vs_laycurse_02.txt,chokudai_vs_laycurse_03.txt,chokudai_vs_sanagipp_01.txt,chokudai_vs_sanagipp_02.txt,chokudai_vs_sanagipp_03.txt,chokudai_vs_sanagipp_04.txt,chokudai_vs_takahashikun_01.txt,chokudai_vs_takahashikun_02.txt,chokudai_vs_takahashikun_03.txt,chokudai_vs_takahashikun_04.txt,chokudai_vs_uwitenpen_01.txt,chokudai_vs_uwitenpen_02.txt,chokudai_vs_uwitenpen_03.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01.txt AC 34 ms 3364 KB
00_sample_02.txt AC 32 ms 3312 KB
00_sample_03.txt AC 33 ms 3348 KB
chokudai_solo_01.txt AC 33 ms 3304 KB
chokudai_solo_02.txt AC 33 ms 3304 KB
chokudai_solo_03.txt AC 36 ms 3352 KB
chokudai_vs_cucumber_01.txt AC 37 ms 3432 KB
chokudai_vs_cucumber_02.txt AC 35 ms 3308 KB
chokudai_vs_cucumber_03.txt AC 35 ms 3428 KB
chokudai_vs_cucumber_04.txt AC 35 ms 3356 KB
chokudai_vs_cucumber_05.txt AC 35 ms 3440 KB
chokudai_vs_kensho_01.txt AC 33 ms 3432 KB
chokudai_vs_kensho_02.txt AC 35 ms 3344 KB
chokudai_vs_kensho_03.txt AC 36 ms 3436 KB
chokudai_vs_kensho_04.txt AC 34 ms 3428 KB
chokudai_vs_kensho_05.txt AC 36 ms 3432 KB
chokudai_vs_kensho_06.txt AC 36 ms 3436 KB
chokudai_vs_kensho_07.txt AC 36 ms 3440 KB
chokudai_vs_kensho_08.txt AC 35 ms 3436 KB
chokudai_vs_kensho_09.txt AC 36 ms 3348 KB
chokudai_vs_laycurse_01.txt AC 35 ms 3440 KB
chokudai_vs_laycurse_02.txt AC 35 ms 3316 KB
chokudai_vs_laycurse_03.txt AC 34 ms 3436 KB
chokudai_vs_sanagipp_01.txt AC 36 ms 3464 KB
chokudai_vs_sanagipp_02.txt AC 35 ms 3384 KB
chokudai_vs_sanagipp_03.txt AC 38 ms 3436 KB
chokudai_vs_sanagipp_04.txt AC 35 ms 3436 KB
chokudai_vs_takahashikun_01.txt AC 33 ms 3440 KB
chokudai_vs_takahashikun_02.txt AC 34 ms 3432 KB
chokudai_vs_takahashikun_03.txt AC 36 ms 3568 KB
chokudai_vs_takahashikun_04.txt AC 36 ms 3440 KB
chokudai_vs_uwitenpen_01.txt AC 35 ms 3436 KB
chokudai_vs_uwitenpen_02.txt AC 32 ms 3436 KB
chokudai_vs_uwitenpen_03.txt AC 36 ms 3440 KB