AGC021 A - Digit Sum 2
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import numpy as np from numpy import linalg as LA # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() S = str(N) if len(S) == 1: print(N) else: for i in range(len(S)-1): if S[-i-1] != '9': N -= (int(S[-i-1]) + 1) * 10 ** i S = str(N) ret = 0 for s in S: ret += int(s) print(ret) if __name__ == '__main__': main()
考え方
全ての桁を出来る限り大きい値に近づけて、各桁の和を求めます。
N
がN < 10
の場合には、N
が回答となります。
そのため、N
が二桁以上(N >= 10`)場合を考えます。
N
が二桁以上の場合には、各桁を出来る限り9
に近づけるまたは9
にすることが最善です。
例えばn
桁目がx
(9
以外の0 ~ 8
)の場合、
N - (x + 1) * 10 ** n
でn
桁を9
にすることができます。