<commit_before>class Solver
  def initialize players
    @players = players
    @line = Array.new @players * 2
    @memo = Hash.new
  end

  def create_key line, players
    pattern = line.map{|pos| pos.nil? ? "0" : "*"}.join(":")
    pattern = pattern.scan(/^((\*:)*)(.+?)((:\*)*)$/)[0][2]
    filled_pos = pattern.index("*")
    pattern.reverse! if !filled_pos.nil? && filled_pos > pattern.length / 2
    # p pattern
    players.to_s + ">>" + pattern
  end

  def solve max_number
    # メモ化のためのkey生成
    # 配列の空きパターンと残りの選手
    key = create_key @line, max_number
    # p key
    # if max_number == 0
    #   p "*" * 20 + "answer" + "*" * 20
    #   p @line
    #   p "*" * 20 + "answer" + "*" * 20
    # end

    return 1 if max_number == 0
    return @memo[key] if @memo.include? key

    # 探索
    answer = 0
    @line.each_with_index do |pos, i|
      j = i + max_number + 1
      if pos.nil? && j < @line.length && @line[j].nil?
        @line[i] = max_number
        @line[j] = max_number
        # p @line
        answer += solve(max_number - 1)
        @line[i] = nil
        @line[j] = nil
      end
    end

    # p "*" * 20 + "memoization" + "*" * 20
    # p key
    # p @line
    # p answer
    # p "*" * 20 + "memoization" + "*" * 20    
    @memo[key] = answer
    answer
  end
end

players = STDIN.gets.chomp.to_i
solver = Solver.new players
p 35584
# p solver.solve players<commit_msg>improve: by immadiately returning 0 if can't put any player to target position #82<commit_after>class Solver
  attr_accessor :hit, :total

  def initialize players
    @players = players
    @line = Array.new @players * 2
    @memo = Hash.new
    @hit = 0
    @total = 0
  end

  def create_key line, players
    pattern = line.map{|pos| pos.nil? ? "0" : "*"}.join(":")
    pattern = pattern.scan(/^((\*:)*)(.+?)((:\*)*)$/)[0][2]
    filled_pos = pattern.index("*")
    pattern.reverse! if !filled_pos.nil? && filled_pos > pattern.length / 2
    # p pattern
    players.to_s + ">>" + pattern
  end

  def solve max_number
    @total += 1
    # メモ化のためのkey生成
    # 配列の空きパターンと残りの選手
    key = create_key @line, max_number
    # p key

    return 1 if max_number == 0
    if @memo.include? key
      @hit += 1
      # p "cached answer ***** >> #{key}, #{@memo[key]}"
      return @memo[key] 
    end

    # 探索
    answer = 0
    @line.each_with_index do |pos, i|
      j = i + max_number + 1
      break if j >= @line.length
      if pos.nil? && @line[j].nil?
        @line[i] = max_number
        @line[j] = max_number
        # p @line
        answer += solve(max_number - 1)
        @line[i] = nil
        @line[j] = nil
      elsif pos.nil?
        # 対象の場所に配置できる選手がいるか確認
        # いなければこの空きパターンの答えは0
        # p "possibility ******* >> #{@line}, #{pos}, #{@line[j]}"
        impossible = true
        (max_number - 1).downto(1) do |number|
          k = i + number + 1
          l = i - (number + 1)
          break if k >= @line.length && l < 0
          # p "possibility ******* >> number:#{number}, #{pos}, #{@line[k]}, #{@line[l]}"
          if (k < @line.length && @line[k].nil?) || (l >= 0 && @line[l].nil?)
            impossible = false
            break
          end
        end
        break if impossible
      end
    end

    # p "memoization ******* >> #{key}, #{answer}, #{@line}"
    @memo[key] = answer
    answer
  end
end

players = STDIN.gets.chomp.to_i
solver = Solver.new players
# p 35584
p solver.solve players
p "cache hit ********* >> #{solver.total}, #{solver.hit}"
{'fraction_non_alphanumeric': 0.16905444126074498, 'fraction_numerical': 0.017478510028653294, 'mean_word_length': 2.100355239786856, 'pattern_counts': {'":': 2, '<': 6, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5381714', 'n_tokens_mistral': 1395, 'n_tokens_neox': 1320, 'n_words': 329}