Skip to content

Instantly share code, notes, and snippets.

@taksatou
Created October 10, 2014 09:50
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save taksatou/f22569247e08b9a72a87 to your computer and use it in GitHub Desktop.
#!/usr/bin/env ruby
class Node
attr_accessor :size, :num, :left, :right
def initialize(n)
self.size = 1
self.num = n
self.left = nil
self.right = nil
end
def insert(node)
self.size += 1
if self.num < node.num
if self.right.nil?
self.right = node
return 0
else
return self.right.insert(node)
end
else
if self.left.nil?
self.left = node
return self.size - 1
else
return self.left.insert(node) + 1 + (self.right.nil? ? 0 : self.right.size)
end
end
end
end
def solve(lis)
sum = 0
root = Node.new lis.shift
lis.each do |e|
sum += root.insert(Node.new(e))
end
sum
end
if __FILE__ == $0
lis = ARGF.read.split
puts solve(lis)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment