






lowerCamelCase			:					List[str]         =	range(2, 20 + 1)
lowerCamelCase			:					Optional[Any]         =	[10**k for k in range(ks[-1] + 1)]
lowerCamelCase			:					dict[int, dict[int, list[list[int]]]]         =	{}





def       __lowerCAmelCase      (						__snake_case					, __snake_case					, __snake_case					, __snake_case       ):
     __lowerCAmelCase								=					sum(a_i[j] for j in range(__UpperCamelCase					, len(__UpperCamelCase       )       )       )
     __lowerCAmelCase								=					sum(a_i[j] * base[j] for j in range(min(len(__UpperCamelCase       )					, __UpperCamelCase       )       )       )

     __lowerCAmelCase								=					0, 0
     __lowerCAmelCase								=					n - i

     __lowerCAmelCase								=					memo.get(__UpperCamelCase       )

     if sub_memo is not None:
          __lowerCAmelCase								=					sub_memo.get(__UpperCamelCase       )

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

               if max_jump >= 0:
                    __lowerCAmelCase								=					jumps[max_jump]
                    # since the difference between jumps is cached, add c
                    __lowerCAmelCase								=					diff + c
                    for j in range(min(__UpperCamelCase					, len(__UpperCamelCase       )       )       ):
                         __lowerCAmelCase								=					divmod(__UpperCamelCase					, 10       )
                    if new_c > 0:
                         add(__UpperCamelCase					, __UpperCamelCase					, __UpperCamelCase       )

          else:
               __lowerCAmelCase								=					[]
     else:
          __lowerCAmelCase								=					{c: []}
          __lowerCAmelCase								=					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								=					next_term(__UpperCamelCase					, k - 1					, i + dn					, __UpperCamelCase       )
               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								=					compute(__UpperCamelCase					, __UpperCamelCase					, i + dn					, __UpperCamelCase       )
          diff += _diff
          dn += terms_jumped

     __lowerCAmelCase								=					sub_memo[c]

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

     # cache the jump for this value digitsum(b) and c
     sub_memo[c].insert(__UpperCamelCase					, (diff, dn, k)       )
     return (diff, dn)





def       __lowerCAmelCase      (						__snake_case					, __snake_case					, __snake_case					, __snake_case       ):







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

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

     while i < n:
          i += 1
          __lowerCAmelCase								=					ds_c + ds_b
          diff += addend
          __lowerCAmelCase								=					0
          for j in range(__UpperCamelCase       ):
               __lowerCAmelCase								=					a_i[j] + addend
               __lowerCAmelCase								=					divmod(__UpperCamelCase					, 10       )

               ds_c += a_i[j]

          if addend > 0:
               break

     if addend > 0:
          add(__UpperCamelCase					, __UpperCamelCase					, __UpperCamelCase       )
     return diff, i - start_i





def       __lowerCAmelCase      (						__snake_case					, __snake_case					, __snake_case       ):







     for j in range(__UpperCamelCase					, len(__UpperCamelCase       )       ):
          __lowerCAmelCase								=					digits[j] + addend
          if s >= 10:
               __lowerCAmelCase								=					divmod(__UpperCamelCase					, 10       )
               __lowerCAmelCase								=					addend // 10 + quotient
          else:
               __lowerCAmelCase								=					s
               __lowerCAmelCase								=					addend // 10

          if addend == 0:
               break

     while addend > 0:
          __lowerCAmelCase								=					divmod(__UpperCamelCase					, 10       )
          digits.append(__UpperCamelCase       )





def       __lowerCAmelCase      (						__snake_case = 10**15       ):
     __lowerCAmelCase								=					[1]
     __lowerCAmelCase								=					1
     __lowerCAmelCase								=					0
     while True:
          __lowerCAmelCase								=					next_term(__UpperCamelCase					, 20					, i + dn					, __UpperCamelCase       )
          dn += terms_jumped
          if dn == n - i:
               break

     __lowerCAmelCase								=					0
     for j in range(len(__UpperCamelCase       )       ):
          a_n += digits[j] * 10**j
     return a_n


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











# Copyright 2021 The HuggingFace Team. All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

from pathlib import Path

import torch

from ...utils import is_npu_available, is_xpu_available
from .config_args import ClusterConfig, default_json_config_file
from .config_utils import SubcommandHelpFormatter


lowerCamelCase			:					List[str]         =	'''Create a default config file for Accelerate with only a few flags set.'''





def       __lowerCAmelCase      (						__snake_case="no"					, __snake_case = default_json_config_file					, __snake_case = False       ):
     __lowerCAmelCase								=					Path(__snake_case       )
     path.parent.mkdir(parents=__snake_case					, exist_ok=__snake_case       )
     if path.exists():
          print(
              F"""Configuration already exists at {save_location}, will not override. Run `accelerate config` manually or pass a different `save_location`."""       )
          return False
     __lowerCAmelCase								=					mixed_precision.lower()
     if mixed_precision not in ["no", "fp16", "bf16", "fp8"]:
          raise ValueError(
              F"""`mixed_precision` should be one of 'no', 'fp16', 'bf16', or 'fp8'. Received {mixed_precision}"""       )
     __lowerCAmelCase								=					{
         "compute_environment": "LOCAL_MACHINE",
         "mixed_precision": mixed_precision,
     }
     if torch.cuda.is_available():
          __lowerCAmelCase								=					torch.cuda.device_count()
          __lowerCAmelCase								=					num_gpus
          __lowerCAmelCase								=					False
          if num_gpus > 1:
               __lowerCAmelCase								=					"MULTI_GPU"
          else:
               __lowerCAmelCase								=					"NO"
     elif is_xpu_available() and use_xpu:
          __lowerCAmelCase								=					torch.xpu.device_count()
          __lowerCAmelCase								=					num_xpus
          __lowerCAmelCase								=					False
          if num_xpus > 1:
               __lowerCAmelCase								=					"MULTI_XPU"
          else:
               __lowerCAmelCase								=					"NO"
     elif is_npu_available():
          __lowerCAmelCase								=					torch.npu.device_count()
          __lowerCAmelCase								=					num_npus
          __lowerCAmelCase								=					False
          if num_npus > 1:
               __lowerCAmelCase								=					"MULTI_NPU"
          else:
               __lowerCAmelCase								=					"NO"
     else:
          __lowerCAmelCase								=					0
          __lowerCAmelCase								=					True
          __lowerCAmelCase								=					1
          __lowerCAmelCase								=					"NO"
     __lowerCAmelCase								=					ClusterConfig(**__snake_case       )
     config.to_json_file(__snake_case       )
     return path





def       __lowerCAmelCase      (						__snake_case					, __snake_case       ):
     __lowerCAmelCase								=					parser.add_parser("default"					, parents=__snake_case					, help=__snake_case					, formatter_class=__snake_case       )
     parser.add_argument(
         "--config_file"					, default=__snake_case					, help=(
             "The path to use to store the config file. Will default to a file named default_config.yaml in the cache "
             "location, which is the content of the environment `HF_HOME` suffixed with 'accelerate', or if you don't have "
             "such an environment variable, your cache directory ('~/.cache' or the content of `XDG_CACHE_HOME`) suffixed "
             "with 'huggingface'."
         )					, dest="save_location"					, )

     parser.add_argument(
         "--mixed_precision"					, choices=["no", "fp16", "bf16"]					, type=__snake_case					, help="Whether or not to use mixed precision training. "
         "Choose between FP16 and BF16 (bfloat16) training. "
         "BF16 training is only supported on Nvidia Ampere GPUs and PyTorch 1.10 or later."					, default="no"					, )
     parser.set_defaults(func=__snake_case       )
     return parser





def       __lowerCAmelCase      (						__snake_case       ):
     __lowerCAmelCase								=					write_basic_config(args.mixed_precision					, args.save_location       )
     if config_file:
          print(F"""accelerate configuration saved at {config_file}"""       )






