Advertisement
Guest User

Untitled

a guest
Oct 16th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Ruby 1.44 KB | None | 0 0
  1. #!/bin/ruby
  2.  
  3. require 'json'
  4. require 'stringio'
  5.  
  6. #
  7. # Complete the 'cutTheTree' function below.
  8. #
  9. # The function is expected to return an INTEGER.
  10. # The function accepts following parameters:
  11. #  1. INTEGER_ARRAY data
  12. #  2. 2D_INTEGER_ARRAY edges
  13. #
  14.  
  15. def cutTheTree(data, edges)
  16.     nnext = Array.new(data.length+1, [])
  17.     edges.each do |ed|
  18.         a = ed[0]
  19.         b = ed[1]
  20.         #puts "#{a},#{b}"
  21.         nnext[a] |= [b]
  22.         nnext[b] |= [a]
  23.         #puts "#{nnext}"
  24.     end
  25.     #puts "#{nnext}"
  26.     nval = []
  27.     vted = []
  28.     define_method(:countnval) do |nod|
  29.         vted[nod] = true
  30.         count = data[nod-1]
  31.         nnext[nod].each do |nx|
  32.             next if vted[nx]
  33.             count += countnval(nx)
  34.         end
  35.         nval[nod] = count
  36.         return count
  37.     end
  38.     countnval 1
  39.     nval.shift
  40.     mid = nval[0]/2
  41.     puts "#{mid}"
  42.     if nval[0] % 2 == 0 then
  43.         nval.map! do |val|
  44.             2*(val-mid).abs
  45.         end
  46.     else
  47.         nval.map! do |val|
  48.             val - mid > 0 ? 2*(val-mid).abs - 1 : 2*(val-mid).abs + 1
  49.         end
  50.     end
  51.     return nval.min
  52.     #puts "#{nval}"
  53. end
  54.  
  55. fptr = File.open(ENV['OUTPUT_PATH'], 'w')
  56.  
  57. n = gets.strip.to_i
  58.  
  59. data = gets.rstrip.split.map(&:to_i)
  60.  
  61. edges = Array.new(n - 1)
  62.  
  63. (n - 1).times do |i|
  64.     edges[i] = gets.rstrip.split.map(&:to_i)
  65. end
  66.  
  67. result = cutTheTree data, edges
  68.  
  69. fptr.write result
  70. fptr.write "\n"
  71.  
  72. fptr.close()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement