


"""simple docstring"""







lowerCAmelCase__      				=   range(2, 20 + 1)
lowerCAmelCase__      				=   [10**k for k in range(ks[-1] + 1)]
lowerCAmelCase__      				=   {}
def 					a__			(				SCREAMING_SNAKE_CASE    :    str				,      SCREAMING_SNAKE_CASE    :    Optional[Any]				,      SCREAMING_SNAKE_CASE    :    Tuple				,      SCREAMING_SNAKE_CASE    :    List[str]				):


  '''simple docstring'''







  lowerCAmelCase     :     Union[str, Any]								=							sum(a_i[j] for j in range(SCREAMING_SNAKE_CASE				,      len(SCREAMING_SNAKE_CASE				)				)				)
  lowerCAmelCase     :     int								=							sum(a_i[j] * base[j] for j in range(min(len(SCREAMING_SNAKE_CASE				)				,      SCREAMING_SNAKE_CASE				)				)				)

  lowerCAmelCase						,  lowerCAmelCase     :     List[Any]								=							0, 0
  lowerCAmelCase     :     int								=							n - i

  lowerCAmelCase     :     Optional[Any]								=							memo.get(SCREAMING_SNAKE_CASE				)

  if sub_memo is not None:
    lowerCAmelCase     :     Dict								=							sub_memo.get(SCREAMING_SNAKE_CASE				)

    if jumps is not None and len(SCREAMING_SNAKE_CASE				) > 0:
      # find and make the largest jump without going over
      lowerCAmelCase     :     int								=							-1
      for _k in range(len(SCREAMING_SNAKE_CASE				) - 1				,      -1				,      -1				):
        if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
          lowerCAmelCase     :     str								=							_k
          break

      if max_jump >= 0:
        lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase     :     Optional[int]								=							jumps[max_jump]
        # since the difference between jumps is cached, add c
        lowerCAmelCase     :     Optional[int]								=							diff + c
        for j in range(min(SCREAMING_SNAKE_CASE				,      len(SCREAMING_SNAKE_CASE				)				)				):
          lowerCAmelCase						,  lowerCAmelCase     :     Any								=							divmod(SCREAMING_SNAKE_CASE				,      1_0				)
        if new_c > 0:
          add(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)

    else:
      lowerCAmelCase     :     Dict								=							[]
  else:
    lowerCAmelCase     :     Union[str, Any]								=							{c: []}
    lowerCAmelCase     :     List[Any]								=							sub_memo

  if dn >= max_dn or c + diff >= base[k]:
    return diff, dn

  if k > ks[0]:
    while True:
      # keep doing smaller jumps
      lowerCAmelCase						,  lowerCAmelCase     :     Any								=							next_term(SCREAMING_SNAKE_CASE				,      k - 1				,      i + dn				,      SCREAMING_SNAKE_CASE				)
      diff += _diff
      dn += terms_jumped

      if dn >= max_dn or c + diff >= base[k]:
        break
  else:
    # would be too small a jump, just compute sequential terms instead
    lowerCAmelCase						,  lowerCAmelCase     :     Dict								=							compute(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				,      i + dn				,      SCREAMING_SNAKE_CASE				)
    diff += _diff
    dn += terms_jumped

  lowerCAmelCase     :     Any								=							sub_memo[c]

  # keep jumps sorted by # of terms skipped
  lowerCAmelCase     :     Optional[Any]								=							0
  while j < len(SCREAMING_SNAKE_CASE				):
    if jumps[j][1] > dn:
      break
    j += 1

  # cache the jump for this value digitsum(b) and c
  sub_memo[c].insert(SCREAMING_SNAKE_CASE				,      (diff, dn, k)				)
  return (diff, dn)
def 					a__			(				SCREAMING_SNAKE_CASE    :    Union[str, Any]				,      SCREAMING_SNAKE_CASE    :    Dict				,      SCREAMING_SNAKE_CASE    :    Optional[int]				,      SCREAMING_SNAKE_CASE    :    Optional[Any]				):


  '''simple docstring'''







  if i >= n:
    return 0, i
  if k > len(SCREAMING_SNAKE_CASE				):
    a_i.extend([0 for _ in range(k - len(SCREAMING_SNAKE_CASE				)				)]				)

  # note: a_i -> b * 10^k + c
  # ds_b -> digitsum(b)
  # ds_c -> digitsum(c)
  lowerCAmelCase     :     int								=							i
  lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase     :     List[Any]								=							0, 0, 0
  for j in range(len(SCREAMING_SNAKE_CASE				)				):
    if j >= k:
      ds_b += a_i[j]
    else:
      ds_c += a_i[j]

  while i < n:
    i += 1
    lowerCAmelCase     :     Dict								=							ds_c + ds_b
    diff += addend
    lowerCAmelCase     :     str								=							0
    for j in range(SCREAMING_SNAKE_CASE				):
      lowerCAmelCase     :     Any								=							a_i[j] + addend
      lowerCAmelCase						,  lowerCAmelCase     :     Any								=							divmod(SCREAMING_SNAKE_CASE				,      1_0				)

      ds_c += a_i[j]

    if addend > 0:
      break

  if addend > 0:
    add(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
  return diff, i - start_i
def 					a__			(				SCREAMING_SNAKE_CASE    :    Any				,      SCREAMING_SNAKE_CASE    :    Optional[Any]				,      SCREAMING_SNAKE_CASE    :    Tuple				):


  '''simple docstring'''







  for j in range(SCREAMING_SNAKE_CASE				,      len(SCREAMING_SNAKE_CASE				)				):
    lowerCAmelCase     :     Optional[int]								=							digits[j] + addend
    if s >= 1_0:
      lowerCAmelCase						,  lowerCAmelCase     :     Dict								=							divmod(SCREAMING_SNAKE_CASE				,      1_0				)
      lowerCAmelCase     :     str								=							addend // 1_0 + quotient
    else:
      lowerCAmelCase     :     List[Any]								=							s
      lowerCAmelCase     :     Dict								=							addend // 1_0

    if addend == 0:
      break

  while addend > 0:
    lowerCAmelCase						,  lowerCAmelCase     :     List[str]								=							divmod(SCREAMING_SNAKE_CASE				,      1_0				)
    digits.append(SCREAMING_SNAKE_CASE				)
def 					a__			(				SCREAMING_SNAKE_CASE    :    int = 1_0**1_5				):


  '''simple docstring'''







  lowerCAmelCase     :     Any								=							[1]
  lowerCAmelCase     :     Optional[int]								=							1
  lowerCAmelCase     :     Optional[Any]								=							0
  while True:
    lowerCAmelCase						,  lowerCAmelCase     :     Any								=							next_term(SCREAMING_SNAKE_CASE				,      2_0				,      i + dn				,      SCREAMING_SNAKE_CASE				)
    dn += terms_jumped
    if dn == n - i:
      break

  lowerCAmelCase     :     Any								=							0
  for j in range(len(SCREAMING_SNAKE_CASE				)				):
    a_n += digits[j] * 1_0**j
  return a_n


if __name__ == "__main__":
     print(F"{solution() = }")













import os

# Precomputes a list of the 100 first triangular numbers
__UpperCAmelCase								=						[int(0.5 * n * (n + 1)) for n in range(1, 101)]




def      lowercase__      (     ):


					'''simple docstring'''


					UpperCAmelCase_    :      Any            =						os.path.dirname(os.path.realpath(__snake_case  )  )
					UpperCAmelCase_    :      Optional[Any]            =						os.path.join(__snake_case     ,       'words.txt'  )

					UpperCAmelCase_    :      Union[str, Any]            =						''
					with open(__snake_case  ) as f:
										UpperCAmelCase_    :      List[Any]            =						f.readline()

					UpperCAmelCase_    :      Optional[int]            =						[word.strip('"'  ) for word in words.strip('\r\n'  ).split(','  )]
					UpperCAmelCase_    :      Optional[int]            =						[
					    word
					    for word in [sum(ord(__snake_case  ) - 64 for x in word  ) for word in words]
					    if word in TRIANGULAR_NUMBERS
					]
					return len(__snake_case  )


if __name__ == "__main__":
		print(solution())






