E - Digit Sum Divisible 2
Source: atcoder
Difficulty: 500

Problem Statement
The digit sum of a positive integer
n
is defined as the sum of its digits when
n
is written in decimal. For example, the digit sum of
2025
is
2 + 0 + 2 + 5 = 9
.
A positive integer
n
is called a
good integer
if it is divisible by its digit sum. For example,
2025
is a good integer because it is divisible by its digit sum of
9
.
A pair of positive integers
(a, a+1)
is called
twin good integers
if both
a
and
a+1
are good integers. For example,
(2024, 2025)
is twin good integers.
You are given a positive integer
N
. Find a pair of twin good integers
(a, a + 1)
such that
N \leq a
and
a + 1 \leq 2N
. If no such pair exists, report that fact.
Constraints
N
is an integer at least
1
and less than
10^{100000}
.
Input
The input is given from Standard Input in the following format:
N
Output
If there exists such a pair
(a, a+1)
, output
a
. Otherwise, output
-1
. Do not print leading zeros.
If there are multiple such pairs, you may print any.
Sample Input 1
5
Sample Output 1
8
(8, 9)
is a valid pair of twin good integers satisfying the conditions. Other examples include
(5, 6), (6, 7), (7, 8), (9, 10)
.
Sample Input 2
21
Sample Output 2
-1
No pair of twin good integers satisfies the conditions.
Sample Input 3
1234
Sample Output 3
2024
(2024, 2025)
is a valid pair of twin good integers.
Sample Input 4
1234567890123456789012345678901234567890
Sample Output 4
1548651852734633803438094164372911259190

C++ solution:
/**
 *    author:  otera
 *    created: 01.26.2025 05:36:41
**/
#include<bits/stdc++.h>

namespace otera {}
using namespace std;
using namespace otera;

struct io_setup {
    io_setup(int precision = 20) {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout << fixed << setprecision(precision);
    }
} io_setup_ {};

#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
#define repa(i, n) for(int i = 0; i < (n); ++ i)
#define repb(i, a, b) for(int i = (a); i < (b); ++ i)
#define repc(i, a, b, c) for(int i = (a); i < (b); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define rep(...) overload4(__VA_ARGS__, repc, repb, repa)(__VA_ARGS__)
#define rep1a(i, n) for(int i = 1; i <= (n); ++ i)
#define rep1b(i, a, b) for(int i = (a); i <= (b); ++ i)
#define rep1c(i, a, b, c) for(int i = (a); i <= (b); i += (c))
#define rep1(...) overload4(__VA_ARGS__, rep1c, rep1b, rep1a)(__VA_ARGS__)
#define rev_repa(i, n) for(int i=(n)-1;i>=0;i--)
#define rev_repb(i, a, b) for(int i=(b)-1;i>=(a);i--)
#define rev_rep(...) overload3(__VA_ARGS__, rev_repb, rev_repa)(__VA_ARGS__)
#define rev_rep1a(i, n) for(int i=(n);i>=1;i--)
#define rev_rep1b(i, a, b) for(int i=(b);i>=(a);i--)
#define rev_rep1(...) overload3(__VA_ARGS__, rev_rep1b, rev_rep1a)(__VA_ARGS__)
#define for_subset(t, s) for(ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define sc second
#define all(c) std::begin(c), std::end(c)
#define rall(c) std::rbegin(c), std::rend(c)
#define lb(c, x) distance(std::begin(c), lower_bound(all(c), (x)))
#define ub(c, x) distance(std::begin(c), upper_bound(all(c), (x)))
#define Sort(a) sort(all(a))
#define Rev(a) reverse(all(a))
#define Uniq(a) sort(all(a));(a).erase(unique(all(a)),std::end(a))
#define si(c) (int)(c).size()
inline ll popcnt(ull a){ return __builtin_popcountll(a); }
#define kth_bit(x, k) ((x>>k)&1)
#define unless(A) if(!(A))
#define elif else if
ll modulo(ll n, ll d){ return (n % d + d) % d; };
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll intpow(ll a, ll b, ll m) {ll ans = 1; while(b){ if(b & 1) (ans *= a) %= m; (a *= a) %= m; b /= 2; } return ans; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> constexpr inline int pow_m1(T n) { return -(n & 1) | 1; }
template <typename T> constexpr inline T fld(const T x, const T y) { return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y; }
template <typename T> constexpr inline T cld(const T x, const T y) { return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y; }
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type>name(__VA_ARGS__)
#define VEC(type,name,size) vector<type>name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T> using vvvc = vector<vvc<T>>;
template <class T> using vvvvc = vector<vvvc<T>>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T, class U> using umap = unordered_map<T, U>;
template<class T> void scan(T& a){ cin >> a; }
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ cout << ' '; }
template<class T> void print(const T& a){ cout << a; }
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout << ' '; print(*i); } }
int out(){ cout << '\n'; return 0; }
template<class T> int out(const T& t){ print(t); cout << '\n'; return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); cout << ' '; out(tail...); return 0; }
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#define dump(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...)
#define dump(...)
#endif

void solve() {
    auto good = [&](int x) -> bool {
        int sum = 0;
        string str = to_string(x);
        rep(i, si(str)) sum += (str[i] - '0');
        return x % sum == 0;
    };

    STR(s);
    int sz = si(s);

    if(sz <= 5) {
        int n = stoi(s);
        for(int a = n; a + 1 <= 2 * n; ++ a) {
            if(good(a) and good(a + 1)) {
                out(a);
                return;
            }
        } 
        out(-1);
    } else {
        int val = s[0] - '0';
        int val2 = s[1] - '0';
        if(val == 1 and val2 == 0) {
            string ans(sz, '0');
            ans[0] = '1';
            ans[1] = '1';
            out(ans);
        } else if(val <= 7) {  
            string ans(sz, '0');
            int nxt = val + 1;
            ans[0] = (char)('0' + nxt);
            ans[1] = (char)('0' + ((nxt <= 2 ? 2 : 8) - nxt));
            out(ans);
        } else {
            string ans(sz + 1, '0');
            ans[0] = '1';
            ans[sz - 1] = '1';
            out(ans);
        }
    }
}

signed main() {
    int testcase = 1;
    // in(testcase);
    while(testcase--) solve();
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

func main() { solve(os.Stdin, os.Stdout) }

func solve(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	sum := func(x int) (res int) {
		for x > 0 {
			res += x % 10
			x /= 10
		}
		return
	}

	s := readString(in)
	if len(s) <= 4 {
		n, _ := strconv.Atoi(s)
		for i := n; i < n*2; i++ {
			si := sum(i)
			si1 := sum(i + 1)
			if i%si == 0 && (i+1)%si1 == 0 {
				fmt.Fprintln(out, i)
				return
			}
		}
		fmt.Fprintln(out, -1)
	} else {
		res := make([]byte, len(s))
		for i := range res {
			res[i] = '0'
		}
		if s[0] == '1' {
			if s[1] <= '6' {
				res[0], res[1] = '1', '7'
			} else {
				res[0], res[1] = '2', '6'
			}
		} else if s[0] <= '7' {
			res[0], res[1] = s[0]+1, '8'+'0'-s[0]-1
		} else {
			res[0], res[1] = '1', '1'
			res = append(res, '0')
		}
		fmt.Fprintln(out, string(res))
	}
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    static String N;

    public static void main(String[] args) {
        var sc = new FastScanner(System.in);
        N = sc.next();

        System.out.println(solve());
    }

    static String solve() {
        // 式書いてこねこねしてもわからないので実験をする
        // => (18,19)のペアが多い(100000で134回)
        // => 桁和18になるものを作って条件達成するか見ていくとそのうち上手く行く…？
        // => Nがデカいので無理そう
        // => 投了
        // (8,9)のペアがいい感じになるの実験の時に数値をもっと眺めてたら気づけた？無理では？
        // ずいぶん昔に見た覚えはあるので典型なんだろうか
        //
        // 桁和が8の場合
        // 100a + 10b + c
        // = 99a + 9b + (a+b+c)
        // であり+1すると9で割れる
        // 1000が8で割れるので桁和が8の1000の倍数を適当に作るとよい

        if( isSmall() ) {
            return solveSmall();
        } else {
            return solveBig();
        }
    }

    static boolean isSmall() {
        // 1_000_000 くらいならまぁいいだろう
        return N.length() <= 6;
    }

    static String solveSmall() {
        // 全探索する
        int n = Integer.parseInt(N);
        for (int a = n; a < n*2; a++) {
            int k = ketawa(a);
            if( a%k != 0 ) continue;

            int b = a+1;
            int kb = ketawa(b);
            if( b%kb != 0 ) continue;

            return String.valueOf(a);
        }
        return "-1";
    }

    static String solveBig() {
        // うーん
        int x = N.charAt(0) - '0';
        int y = N.charAt(1) - '0';
        int xy = 10*x+ y;
        if( xy <= 16 ) {
            return "17" + "0".repeat(N.length()-2);
        } else if( xy <= 25 ) {
            return "26" + "0".repeat(N.length()-2);
        } else if( xy <= 34 ) {
            return "35" + "0".repeat(N.length()-2);
        } else if( xy <= 43 ) {
            return "44" + "0".repeat(N.length()-2);
        } else if( xy <= 52 ) {
            return "53" + "0".repeat(N.length()-2);
        } else if( xy <= 61 ) {
            return "62" + "0".repeat(N.length()-2);
        } else {
            return "107" + "0".repeat(N.length()-2);
        }
    }

    static int ketawa(int a) {
        return ketawa(String.valueOf(a));
    }

    static int ketawa(String s) {
        int k = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            k += c - '0';
        }
        return k;
    }

    static void writeLines(int[] as) {
        var pw = new PrintWriter(System.out);
        for (var a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        var pw = new PrintWriter(System.out);
        for (var a : as) pw.println(a);
        pw.flush();
    }

    static void writeSingleLine(int[] as) {
        var pw = new PrintWriter(System.out);
        for (var i = 0; i < as.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(as[i]);
        }
        pw.println();
        pw.flush();
    }

    static void debug(Object... args) {
        var j = new StringJoiner(" ");
        for (var arg : args) {
            if (arg == null) j.add("null");
            else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j);
    }

    @SuppressWarnings("unused")
    private static class FastScanner {

        private final InputStream in;
        private final byte[] buffer = new byte[1024];
        private int curbuf;
        private int lenbuf;

        public FastScanner(InputStream in) {
            this.in = in;
            this.curbuf = this.lenbuf = 0;
        }

        public boolean hasNextByte() {
            if (curbuf >= lenbuf) {
                curbuf = 0;
                try {
                    lenbuf = in.read(buffer);
                } catch (IOException e) {
                    throw new RuntimeException();
                }
                if (lenbuf <= 0)
                    return false;
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte())
                return buffer[curbuf++];
            else
                return -1;
        }

        private boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        private void skip() {
            while (hasNextByte() && isSpaceChar(buffer[curbuf]))
                curbuf++;
        }

        public boolean hasNext() {
            skip();
            return hasNextByte();
        }

        public String next() {
            if (!hasNext())
                throw new RuntimeException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (!isSpaceChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            if (!hasNext())
                throw new RuntimeException();
            int c = readByte();
            while (isSpaceChar(c))
                c = readByte();
            boolean minus = false;
            if (c == '-') {
                minus = true;
                c = readByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new RuntimeException();
                res = res * 10 + c - '0';
                c = readByte();
            } while (!isSpaceChar(c));
            return (minus) ? -res : res;
        }

        public long nextLong() {
            if (!hasNext())
                throw new RuntimeException();
            int c = readByte();
            while (isSpaceChar(c))
                c = readByte();
            boolean minus = false;
            if (c == '-') {
                minus = true;
                c = readByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new RuntimeException();
                res = res * 10 + c - '0';
                c = readByte();
            } while (!isSpaceChar(c));
            return (minus) ? -res : res;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) {
            double[] a = new double[n];
            for (int i = 0; i < n; i++)
                a[i] = nextDouble();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

        public char[][] nextCharMap(int n, int m) {
            char[][] map = new char[n][m];
            for (int i = 0; i < n; i++)
                map[i] = next().toCharArray();
            return map;
        }
    }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var n = nextstr(), m = n.length;
  if(m >= 5){
    var s = xArray(0,m);
    if(+n[0] >= 8){
      s.push(0);
      s[0] = s[1] = 1;
    }else if(+n[0] > 1){
      s[0] = +n[0] + 1;
      s[1] = 8 - s[0];
    }else if(n[1] > "0"){
      s[0] = 2;
    }else{
      s[0] = s[1] = 1;
    }
    return s.join("");
  }
  n = Number(n);
  for(var i = n; i < n*2; i++){
    var t = 0, j = i;
    while(j)t += j % 10, j = j/10|0;
    if(i % t === 0){
      t = 0, j = i+1;
      while(j)t += j % 10, j = j/10|0;
      if((i+1) % t === 0)return i;
    }
  }
  return -1;
}

Python solution:
def num_sum(n):
  res = 0
  while n > 0:
    res += n%10
    n = n//10
  return res
  
def find(n):
  for i in range(n, 2*n):
    if i%num_sum(i) == 0 and (i+1)%num_sum(i+1) == 0:
      return i
  return -1
  
n = input()

if len(n) <= 6:
  print(find(int(n)))

else:
  f = n[0]
  if f == '1':
    if n[1] == '0':
    #   assert False
      print('11'+(len(n)-2)*'0')
    else:
      print('2'+(len(n)-1)*'0')

  elif f == '2':
    print('3'+ (len(n)-4)*'0' + '104')

  elif f == '3':
    print('4'+(len(n)-3)*'0'+'40')

  elif n[:2] == '40':
    print('44'+(len(n)-2)*'0')
  
  elif f in ['4', '5', '6', '7']:
    print('8'+(len(n)-1)*'0')

  elif f in ['8', '9']:
    print('11'+(len(n)-1)*'0')

Ruby solution:
n = gets.chomp.chars.map(&:to_i)
keta = n.length
if keta <= 6
  n = n.join.to_i
  arr = []
  n.upto(2*n) do |i|
    str = i.to_s.chars.map(&:to_i)
    len = str.length
    sum = 0
    len.times do |i|
      sum += str[i]
    end
    arr << i if i % sum == 0
  end
  len = arr.length
  i = 0
  (len-1).times do |i|
    if arr[i]+1 == arr[i+1]
      puts arr[i]
      exit
    end
  end
  puts -1
  exit
end

new_n = (n[0..2].join + n[keta-3..].join).to_i
ans = []
if 100001 <= new_n && new_n < 200001
  ans << 2
  (keta-1).times do
    ans << 0
  end
elsif 200001 <= new_n && new_n < 300000
  ans << 3
  (keta-3).times do
    ans << 0
  end
  ans << 3
  ans << 2
elsif 300000 <= new_n && new_n < 500006
  ans << 5
  (keta-4).times do
    ans << 0
  end
  ans << 1
  ans << 2
  ans << 0
elsif new_n.to_s.chars.map(&:to_i)[0] != 1
  ans << 1
  (keta-2).times do
    ans << 0
  end
  ans << 1
  ans << 0
else
  ans << 1
  (keta-3).times do
    ans << 0
  end
  ans << 1
  ans << 0
end
puts ans.join