1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

AtCoder AGC021 A - Digit Sum 2(300点)

Last updated at Posted at 2019-05-23

#問題概要
問題のリンク

$N$ 以下の正の整数の $10$ 進法での各桁の和の最大値を求めてください。

#制約条件

  • $1≤N≤10^{16}$
  • $N$ は整数である

#考えたこと

やることは一見とてもシンプル!$1$から$N$までの整数を、それぞれ各桁の和をとっていき最大値を求めたい。
だが制約をみたらわかる通り、全探索はとても間に合わない。

求めたいのは最大値なのでできるだけ9が多いほうがいいのは自明である。よって$(N-1)*9+N桁目の値f$が答えとなる。この時、$N$の$1$から$N-1$桁目が全て9である場合、$f$は$N$桁目の値であるが、そうでない場合、$N$桁目の値 - $1$が$f$となる。(そうしないと$N$より大きい値の各桁の和をとることになるので。)

#解答

a.cs
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        long n = long.Parse(Console.ReadLine());
        long l = digitLength(n);
        long f = digitFirst(n);
        Console.WriteLine((l-1)*9 + f);
    }
    static long digitLength(long x) {
        long length = 0;
        while(x>0) {
            length++;
            x /= 10;
        }
        return length;
    }
    static long digitFirst(long x) {
        long first = 0;
        List<long> digit = new List<long>();
        while(x>0) {
            first = x%10;
            digit.Add(x%10);
            x/=10;
        }
        for(int i = 0; i < digit.Count()-1; i ++) {
            if(digit[i] != 9) {
                first -= 1L;
                break;
            }
        }
        return first;
    }
}
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?