# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def move_zeroes(nums)
  # 2つのポインタを使って、その2つのポインタの幅が0の数だと考えれば良い
  # a[right]が0だった場合、rigthに+1をして幅を広げる
  left = 0
  right = 0

  while right < nums.length && left <= right
    if nums[right].zero?
      right += 1
      next
    end

    # 0以外の時の処理

    # 一番手前の0とrightが指し示す0以外の値を入れ替える
    nums[left], nums[right] = nums[right], nums[left]
    left += 1

   # leftが先に行っちゃうパターンがあるから、rightも追いつかせる。
   # leftとrightが同じ位置にいるのは問題なくてleftが先に行っちゃうのが問題
    if right < left
      right = left
    end
  end

  nums
end

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def longest_ones(nums, k)
  max_count = 0
  i = 0
  j = 0
  c = k

  while j <= nums.length - 1 && i <= j
    if nums[j] == 1
      j += 1
    elsif nums[j].zero?
      if c.positive?
        j += 1
        c -= 1
      else
        # これ以上区間を拡張できない時の処理
        # jは動かず、iを動かす
        # 本当にnumsが変わっているわけではなくて、cが減っているだけ
        total_count = ((j - 1) - i) + 1
        max_count = total_count if total_count >= max_count
        c += 1 if nums[i].zero? && k > 0
        i += 1

        # i + 1番目に関しては、以前のウインドウでc -= 1しているはずだから、0かどうかは考慮しなくて良い
        j = i if j <= i
      end
    end

    if j == nums.length
      total_count = ((j - 1) - i) + 1
      max_count = total_count if total_count >= max_count
    end
  end

  max_count
end

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Integer[][]}
def find_difference(nums1, nums2)
  nums1_hash = nums1.tally
  nums1_hash.default = 0
  nums2_hash = nums2.tally
  nums2_hash.default = 0

  answers = [[], []]
  nums1_hash.keys.each do |key|
    if nums2_hash[key].zero?
      answers[0].push(key)
    end
  end

  nums2_hash.keys.each do |key|
    if nums1_hash[key].zero?
      answers[1].push(key)
    end
  end

  answers
end

h = Hash.new(0)

words.map { |word| h[word] += 1 }

lines = readlines.map(&:chomp)

words = lines[1].split(" ")
querys = lines[3..]

word_hash = words.tally
word_hash.default = 0

until querys.empty?
  query = querys.shift
  puts word_hash[query]
end

# TLEになっちゃうアルゴリズム(TLE: Time Limit Exceeded)
# データ構造の選定に失敗している。(配列を採用した)

lines = readlines.map(&:chomp)

words = lines[1].split(" ")
querys = lines[3..]

until querys.empty?
  query = querys.shift

  puts words.count(query)
end

def asteroid_collision(asteroids)
  # この配列をスタックのデータ構造とする
  asteroid_stack = []

  asteroid_stack.push(asteroids[0])

  asteroids[1..].each do |asteroid|
    poped_asteroid = asteroid_stack.pop

    if poped_asteroid.nil?
      asteroid_stack.push(asteroid)
      next
    end

    if (poped_asteroid.positive? && asteroid.positive?) \
        || (poped_asteroid.negative? && asteroid.negative?) \
        || (poped_asteroid.negative? && asteroid.positive?)
      asteroid_stack.push(poped_asteroid, asteroid)
    else
      while asteroid_stack.length >= 0
        if (poped_asteroid.positive? && asteroid.positive?) \
            || (poped_asteroid.negative? && asteroid.negative?) \
            || (poped_asteroid.negative? && asteroid.positive?)
          asteroid_stack.push(poped_asteroid, asteroid)
          break
        end

        if poped_asteroid.abs > asteroid.abs
          asteroid_stack.push(poped_asteroid)
          break
        elsif poped_asteroid.abs == asteroid.abs
          break
        else
          # asteroidの方がでかい場合
          poped_asteroid = asteroid_stack.pop

          # もし、asteroid_stackが空になってしまった場合
          if poped_asteroid.nil?
            asteroid_stack.push(asteroid)
            break
          end
        end
      end
    end
  end

  asteroid_stack
end

# @param {Integer[]} asteroids
# @return {Integer[]}
def asteroid_collision(asteroids)
  # この配列をスタックのデータ構造とする
  asteroid_stack = []

  asteroids.each do |asteroid|
    # 衝突するパターンだけ、whileで処理する
    # 衝突するパターンが終了するまで、ループする
    while !asteroid_stack.empty? && asteroid.negative? && asteroid_stack.last.positive?
      diff = asteroid + asteroid_stack.last

      if diff.negative? # アステロイドの方がでかい
        asteroid_stack.pop
      elsif diff.positive? # stack.lastの方がでかい
        # アステロイドが消えたことを表したいので、0を使う
        asteroid = 0
      else # 同じ大きさの惑星の時
        asteroid = 0
        asteroid_stack.pop
      end
    end

    asteroid_stack.push(asteroid) if asteroid != 0
  end

  asteroid_stack
end

def search_bst(root, val)
  # 2分探索木からwhileでノードを探索する場合
  # この2分探索木の問題の場合、whileのがシンプルに探索できるな
  while root
    break if root.val == val

    root = val > root.val ? root.right : root.left
  end
  root
end

def search_bst(root, val)
  # 2分探索木から再起的にノードを探索する場合
  return nil if root.nil?

  current_val = root.val
  result_node = nil

  if current_val == val
    result_node = root
  elsif val > current_val
    # データ構造が2分探索木なので、current_valがvalより小さいってことは、
    # 右を探索しに行った方が良い
    result_node = search_bst(root.right, val)
  elsif val < current_val
    result_node = search_bst(root.left, val)
  end

  result_node
end

def find_min_node(node)
  while node.left
    node = node.left
  end

  node
end

# 特定ノード削除後のルートノードを返してくれる
def delete_node(root, key)
  return nil if root.nil?

  if key == root.val
    # 子を持たない場合
    if root.left.nil? && root.right.nil?
      root = nil

    # 子を一つ持つ場合
    # 上のif文を書かないと、この条件文に子を持たない場合が内包される
    elsif root.left.nil? || root.right.nil?
      root = root.left || root.right

    # 子を2つ持つ場合
    # 右ツリーが持つ最小値をrootのvalueにする
    else
      min_right_node = find_min_node(root.right)
      root.val = min_right_node.val
      root.right = delete_node(root.right, min_right_node.val)
    end
  elsif key > root.val
    root.right = delete_node(root.right, key)
  elsif key < root.val
    root.left = delete_node(root.left, key)
  end

  root
end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
  return 0 if root.nil?

  unless root.nil?
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
  end

  1 + [left_depth, right_depth].max
end

n, x, y = gets.chomp.split(" ").map(&:to_i)
index = n - 1
# param [Integer] n
# param [Integer] x
# param [Integer] y
def main(n, x, y)
  num_array = Array.new(n, 0)
  sum_nums(n, x, y, num_array)  
end

def sum_nums(n, x, y, num_array)
  return x if n == 0
  return y if n == 1



  left_num = if num_array[n - 1] > 0
              num_array[n - 1]
             else
               num = sum_nums(n - 1, x, y, num_array)
               num_array[n - 1] = num
               num
             end

  right_num = if num_array[n - 2] > 0
                num_array[n - 2]
              else
                num = sum_nums(n - 2, x, y, num_array)
                num_array[n - 2] = num
                num
              end

  (left_num + right_num) % 100
end

p main(index, x, y)

n, x, y = gets.chomp.split(" ").map(&:to_i)
# param [Integer] n
# param [Integer] x
# param [Integer] y

def sum_nums(n, x, y)
  num_array = Array.new(n, 0)
  num_array[0] = x
  num_array[1] = y
  (2..n - 1).each do|i|
    num_array[i] = (num_array[i - 1] + num_array[i -2]) % 100
  end

  num_array[n - 1]
end

p sum_nums(n, x, y)

カメのアルルは N 段の階段をのぼろうとしています。
それぞれの段には、次の 2 通りの方法でのぼることができます。
(階段を降りることはできません。)

1 つ前の段からのぼる。
(存在する場合のみ) 2 つ前の段からのぼる。
今、アルルは階段の 0 段目にいます。
アルルが階段の N 段目までのぼる方法は全部で何通りありますか。

graph = {
  a: ["b", "c"] ,
  b: ["a", "d", "e"],
  c: ["a", "f"],
  d: ["b"], 
  e: ["b", "f"],
  f: ["c", "e"],
}

graph = [
  ["a", "b"],
  ["a", "c"] ,
  ["b", "d"] ,
  ["b", "e"] ,
  ["c", "f"] ,
  ["e", "f"] ,
]

## 方針1
# まず与えられたデータから隣接リストを作る。その隣接リストをハッシュでもつ
# そのハッシュに対してループをかけて、そのノードまでの最短経路を求める

## 方針1の実装手順
# 1. 標準入力を受け取る。友達関係の配列をedgesとする
# 2. edgesからグラフを作成して、変数graphに代入する
# 3. 変数queue = []を用意する
# 4. 0からの距離を表すd = 1を用意する。
# 5. 既に会ったことのある友人をまとめるmet_friends = Set.new([])を定義する
# 5. graph[0]をqueueに入れる
# 6. distances = Array.new(n - 1, 0)を定義する
# 7. queueが空になるまでループを続ける
# 8. ループ内では、queueの長さを取得して、その長さだけループをする。ループ2とする
# 9. ループ2の中では、
#    - queueからnodeを取り出す。そのnodeがもしmet_friendsに含まれていたら次のループに行く
#    - met_friendsにnodeをaddする
#    - disatnces[node] = dを実行する
#    - queueにnodeの連結リストをpushする
# 10. これらの一連の処理が終わったら、distances.maxを出力して終了
require "set"
n, m = gets.chomp.split(" ").map(&:to_i)
edges = readlines.map { |line| line.chomp.split(" ").map(&:to_i) }
graph = Hash.new { |hash, key| hash[key] = Set.new([]) }
edges.each do |edge|
  graph[edge[0]].add(edge[1])
  graph[edge[1]].add(edge[0])
end

# 主要な変数を定義する
queue = []
d = 1
met_friends = Set.new([0])
distances = Array.new(n - 1, 0)

queue.push(*graph[0])

until queue.empty?
  range = queue.length

  range.times do
    node = queue.shift
    next if met_friends.include?(node)

    met_friends.add(node)
    distances[node - 1] = d
    queue.push(*graph[node])
  end

  d += 1
end

p distances.max

# 方針1
# graph = Hash.new { |hash, key| hahs[key] = Set.new([]) }を用意する
# S_iを解析して、黒いマス(i, j)をblack_spacesとして保持する
# グリッドグラフをデータに変換して、変数grid_graphに代入する。
# データに変換する際に、頂点がblack_spacesに含まれていたら、その点を含めないようにする
# あとは、キューを用意して、BFSを目的地までの実行して最短距離を求めて出力する

# 方針1の実装手順
# 1. 標準入力を受け取る。入力を変数h, w, start, goalに代入する
#    sの集合は、変数space_statesで保持する
# 2. space_statesから、黒の点の集合を作って、変数balock_spacesに代入する
# 3. h, mから、グリッドグラフを頂点と辺で構成されたグラフに変換する。そのグラフを変数grid_graphに代入する
#    グラフに変換する際に、頂点がblack_spacesに含まれていたら、その点を含めないようにする
# 4. あとは、キューを用意してBFSを実施する。そして、目的地までの最短距離の手数を出力する
require "set"

# メインの処理
def main()
  h, w = gets.chomp.split(" ").map(&:to_i)
  start_and_goal = gets.chomp.split(" ").map(&:to_i)
  start = start_and_goal[0..1]
  goal = start_and_goal[2..3]
  black_spaces = Set.new([])

  readlines.each.with_index do |line, i|
    line.each_char.with_index do |c, j|
      if c == "B"
        black_spaces.add([i, j])
      end
    end
  end

  grid_graph = create_grid_graph(h, w, black_spaces: black_spaces)

  # BFS
  passed_space = Set.new([start])
  queue = []
  queue.push(*grid_graph[start])
  d = 1

  until queue.empty?
    range = queue.length

    range.times do
      space = queue.shift
      next if passed_space.include?(space)

      if space == goal
        puts d
        return
      end

      passed_space.add(space)
      queue.push(*grid_graph[space])
    end

    d += 1
  end
end  

# @param [Integer] h
# @param [Integer] w
# `param [Array<Set<Integer>> black_spaces]
def create_grid_graph(h, w, black_spaces: [])
  grid_graph = Hash.new { |hash, key| hash[key] = Set.new([]) }

  # グリッドの行数と列数を定義
  rows = h
  cols = w

  # グリッドの各セルをハッシュに追加
  rows.times do |i|
    cols.times do |j|
      cell = [i, j]
      next if black_spaces.include?(cell)

      bottom_cell = [cell[0] + 1, cell[1]]
      right_cell = [cell[0], cell[1] + 1]
      left_cell = [cell[0] - 1, cell[1]]
      top_cell = [cell[0], cell[1] - 1]

      grid_graph[cell].add(bottom_cell) if i < rows - 1 && !black_spaces.include?(bottom_cell)
      grid_graph[cell].add(right_cell) if j < cols - 1 && !black_spaces.include?(right_cell)
      grid_graph[cell].add(left_cell) if i > 0 && !black_spaces.include?(left_cell)
      grid_graph[cell].add(top_cell) if j > 0 && !black_spaces.include?(top_cell)
    end
  end

  grid_graph
end

main()

## 方針1
# 2マス間の上下右左の距離をdistancesとして定義する
# queueを用意して、スタート地点をqueueに入れる
# 手数を表すd = 1を用意する。
# キューが空になるまでループする
# ループ内で、distancesでループをかける。ループカウンタをdとする
#   - スタート地点(x_0, y_0)にdをたす。この点をcurrent_spaceとする
#   - dが範囲外ではないかつ黒いスペースではないなら、その地点に進むと仮定する
#   - falseならnextを実行する
#   - もし、goalと一致するマスなら、putsを実行する。その後、returnを実行する
#   - current_spaceをqueueに入れて、次のdistanceのループに行く。
# distancesのループが終了した後に、d += 1を実行する

## 方針1の実装
# 1 標準入力を受け取る。その入力を変数h, w, start, goal, space_conditionsに入れる
# 2. queue = [start]を用意する。
# 3. d = 1を用意する, distancesも定義する。passed_spacesも定義する
# 4. キューが空になるまでループする
# 5. ループ内でdisntancesでループをかける。ループカウンタをdとする
# 6. 一連のBFSの処理をする
# 7. goalと一致するますがあったらuptsを実行して、returnする
# 8. distancesのループが終了した後に、d += 1を実行する

require "matrix"
require "set"

h, w = gets.chomp.split(" ").map(&:to_i)
start_and_goal = gets.chomp.split(" ").map(&:to_i)
start = start_and_goal[0..1]
goal = start_and_goal[2..3]
space_conditions = readlines.map(&:chomp).map(&:chars)
queue = [start]
move_counts = Array.new(h).map { Array.new(w, -1) }
move_counts[start[0]][start[1]] = 0
# 上下右左
distances = [[-1, 0], [1, 0], [0, 1], [0, -1]]
passed_spaces = Set.new([start])

until queue.empty?
  space = queue.shift

  distances.each do |d|
    current_space = (Vector.elements(space) + Vector.elements(d)).to_a
    next if current_space[0] < 0 || current_space[0] > h - 1
    next if current_space[1] < 0 || current_space[1] > w - 1
    next if space_conditions[current_space[0]][current_space[1]] == "B"
    next if passed_spaces.include?(current_space)
    
    passed_spaces.add(current_space)
    move_counts[current_space[0]][current_space[1]] = move_counts[space[0]][space[1]] + 1
    queue.push(current_space)
  end
end

puts move_counts[goal[0]][goal[1]]

# 方針1
# i日目の最大の報酬を

# 方針1の修正
# - n日間のそれぞれの最大報酬を持つ配列と、n日間で何の仕事を実施したのかを管理する配列day_tasks必要かも

def main
  n = gets.chomp.to_i
  rewards = readlines.map { |line| line.chomp.split(" ").map(&:to_i) }
  day_max_rewards = Array.new(n).map { Array.new(3, -1)}
  day_max_rewards[0] = rewards[0]

  (1..n - 1).each do |i|
    (0..2).each do |j|
      prev_day_rewards = []
      if j == 0
        prev_day_rewards.push(day_max_rewards[i - 1][1], day_max_rewards[i - 1][2])
      end

      if j == 1
        prev_day_rewards.push(day_max_rewards[i - 1][0], day_max_rewards[i - 1][2])
      end
      
      if j == 2
        prev_day_rewards.push(day_max_rewards[i - 1][0], day_max_rewards[i - 1][1])
      end
 
      day_max_rewards[i][j] = prev_day_rewards.max + rewards[i][j]
    end
  end

  puts day_max_rewards[n - 1].max
end

main

# 方針1
# i日目の最大の報酬を

# 方針1の修正
# - n日間のそれぞれの最大報酬を持つ配列と、n日間で何の仕事を実施したのかを管理する配列day_tasks必要かも

def main
  n = gets.chomp.to_i
  rewards = readlines.map { |line| line.chomp.split(" ").map(&:to_i) }
  day_max_rewards = Array.new(n).map { Array.new(3, -1)}
  day_max_rewards[0] = rewards[0]

  (1..n - 1).each do |i|
    day_max_rewards[i][0] = [day_max_rewards[i - 1][1], day_max_rewards[i - 1][2]].max + rewards[i][0]
    day_max_rewards[i][1] = [day_max_rewards[i - 1][0], day_max_rewards[i - 1][2]].max + rewards[i][1]
    day_max_rewards[i][2] = [day_max_rewards[i - 1][0], day_max_rewards[i - 1][1]].max + rewards[i][2]
  end

  puts day_max_rewards[n - 1].max
end

main

# 方針
# 箱に入れられる最大の重さをjとして、0 <= j <= m + 1 と考える。
# ボールの重さの集合をball_weightsとして、インデックスをiとする(0 <= i <= n - 1)
# jの時の箱が0からi個のボールを含められるかを、is_box_includable[i][j]とする
# (配列定義時に初期値は全部falseにしておく)
# 0 <= i <= n - 1と0 <= j <= m + 1の範囲で2重ループをかける。
#   - j == 0ならnextを実行
#   - j == ball_weigths[i]なら、is_box_includable[i][j]にtrueを代入する
#   - i >= 1 && is_box_includable[i - 1][j] == trueなら、is_box_includable[i][j]はtrue
#   - j >= 1 && is_box_includable[i - 1][j - ball_values[i][j]] == trueなら、is_box_includable[i][j]はtrue
# 以上のループをかけた後で、is_box_includable[n - 1][m]を実行すれば、
# 重さの合計がMとなるようなボールの選び方が存在するかがわかる。(何通りの選び方が存在するかに関心がなくて、あるかないかに関心がある)

def main
  n, m = gets.chomp.split(" ").map(&:to_i)
  ball_weights = gets.chomp.split(" ").map(&:to_i)
  is_box_includable = Array.new(n).map { Array.new(m + 1, false) }

  (0..n - 1).each do |i|
    (0..m).each do |j|
      # 箱に入れられる最大の重さが0なら次のループに行く。
      next if j.zero?

      # i番目のボールの重さが、箱に入れられる最大の重さと同じなら、
      # 当然ボールは入れられるからtrue
      if j == ball_weights[i]
        is_box_includable[i][j] = true
        next
      end

      # 条件1に関しては、0 ~ i - 1個のボールを使って、is_box_includedable[i - 1][j]を満たすなら、
      # 0 ~ i個のボールを使った場合、0 ~ i ~ 1個のボールを使えば、is_box_includedable[i][j]を満たす
      # 条件2に関しては、0 ~ i - 1個のボールを使って、is_box_includedable[i - 1][j - ball_weights[i]]を満たすなら、
      # 0 ~ i個のボールを使った場合、ボールiが使えるので、is_box_includedable[i - 1][j - ball_weights[i]]にボールiのball_weight[i]を追加すれば、
      # is_box_includalbe[i][j]は満たす
      if (i >= 1 && is_box_includable[i - 1][j]) || (j >= 1 && is_box_includable[i - 1][j - ball_weights[i]])
        is_box_includable[i][j] = true
        next
      end
    end
  end

  puts is_box_includable[n - 1][m] ? "Yes" : "No"
end


main

5 1
3 1

require "set"

# param [Array<Array<integer>>]
# return [Hash<Integer, Set<Integer>>]
def create_indirected_graph(edges)
  graph = Hash.new { |hash, key| hash[key] = Set.new([]) } 
  edges.each do |edge|
    graph[edge[0]].add(edge[1])
    graph[edge[1]].add(edge[0])
  end

  graph
end

def get_value_by_input_line
  n = gets.chomp.to_i
end

def get_two_values_by_lines
   readlines.map { |line| line.chomp.split(" ").map(&:to_i) }
end

def get_max_height_by_graph(graph, start_node: 0)
  visited = Set.new([start_node])
  queue = [*graph[start_node]]
  max_height = 0

  while !queue.empty?
    range = queue.length

    range.times do
      node = queue.shift

      if !visited.include?(node)
        visited.add(node)
        graph[node].each do |n|
          queue.push(n) unless visited.include?(n)
        end
      end
    end

    max_height += 1
  end

  max_height
end

def get_max_height_node_by_graph(graph, start_node: 0)
  visited = [start_node]
  queue = [*graph[start_node]]


  while !queue.empty?
    range = queue.length

    range.times do
      node = queue.shift

      if !visited.include?(node)
        visited.push(node)
        graph[node].each do |n|
          queue.push(n) unless visited.include?(n)
        end
      end
    end
  end

  visited.last
end

def get_tree_height_by_graph(graph, start_node: 0)
  visited = Set.new([start_node])
  queue = [*graph[start_node]]
  height = 0

  while !queue.empty?
    range = queue.length

    range.times do
      node = queue.shift

      if !visited.include?(node)
        visited.add(node)
        graph[node].each do |n|
          queue.push(n) unless visited.include?(n)
        end
      end
    end

    height += 1
  end

   height
end

def get_value_by_input_line
  n = gets.chomp.to_i
end

def get_two_values_by_lines
   readlines.map { |line| line.chomp.split(" ").map(&:to_i) }
end

require "set"

# param [Array<Array<integer>>]
# return [Hash<Integer, Set<Integer>>]
def indirected_graph(edges)
  graph = Hash.new { |hash, key| hash[key] = Set.new([]) } 
  edges.each do |edge|
    graph[edge[0]].add(edge[1])
    graph[edge[1]].add(edge[0])
  end

  graph
end

def get_max_height_by_graph(graph, start_node: 0)
  visited = Set.new([start_node])
  queue = [*graph[start_node]]
  max_height = 0

  while !queue.empty?
    range = queue.length

    range.times do
      node = queue.shift

      if !visited.include?(node)
        visited.add(node)
        graph[node].each do |n|
          queue.push(n) unless visited.include?(n)
        end
      end
    end

    max_height += 1
  end

  max_height
end

def get_max_height_node_by_graph(graph, start_node: 0)
  visited = [start_node]
  queue = [*graph[start_node]]


  while !queue.empty?
    range = queue.length

    range.times do
      node = queue.shift

      if !visited.include?(node)
        visited.push(node)
        graph[node].each do |n|
          queue.push(n) unless visited.include?(n)
        end
      end
    end
  end

  visited.last
end

def main
  n = get_value_by_input_line
  edges = get_two_values_by_lines
  graph = indirected_graph(edges)

  s_node = get_max_height_node_by_graph(graph)
  max_height = get_max_height_by_graph(graph, start_node: s_node)

  puts (max_height / 2.0).ceil
end

main