C - Snake Numbers
Source: atcoder
Difficulty: 350

Problem Statement
A positive integer not less than
10
whose top digit (the most significant digit) in decimal representation is strictly larger than every other digit in that number is called a
Snake number
.
For example,
31
and
201
are Snake numbers, but
35
and
202
are not.
Find how many Snake numbers exist between
L
and
R
, inclusive.
Constraints
10 \leq L \leq R \leq 10^{18}
All input values are integers.
Input
The input is given from Standard Input in the following format:
L
R
Output
Print the answer.
Sample Input 1
97 210
Sample Output 1
6
The Snake numbers between
97
and
210
, inclusive, are
97
,
98
,
100
,
200
,
201
, and
210
: there are six.
Sample Input 2
1000 9999
Sample Output 2
2025
Sample Input 3
252509054433933519 760713016476190692
Sample Output 3
221852052834757

C++ solution:
#pragma region template
#ifdef USE_PRECOMPILE
#include "pch.h"
#else
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using vi = std::vector<int>;
using vll = std::vector<ll>;
template <typename T> using PA = std::pair<T, T>;
using pi = PA<int>;
using pll = PA<ll>;

#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e, ...) e
#define overload5(a, b, c, d, e, f, ...) f

#define TYPE1(T) template <typename T>
#define TYPE2(T, U) template <typename T, typename U>
#define TYPE(...) overload2(__VA_ARGS__, TYPE2, TYPE1)(__VA_ARGS__)
#define TYPES1(T) template <typename... T>
#define TYPES2(H, T) template <typename H, typename... T>
#define TYPES(...) overload2(__VA_ARGS__, TYPES2, TYPES1)(__VA_ARGS__)

#define REP4(i, s, n, d) for (int i = (s); i < (n); i += (d))
#define REP3(i, s, n) REP4(i, s, n, 1)
#define REP2(i, n) REP3(i, 0, n)
#define REP1(n) REP2(tomato, n)
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)

#define RREP4(i, n, s, d) for (int i = (n) - 1; i >= (s); i -= (d))
#define RREP3(i, n, s) RREP4(i, n, s, 1)
#define RREP2(i, n) RREP3(i, n, 0)
#define RREP1(n) RREP2(tomato, n)
#define RREP(...)                                                              \
    overload4(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__)

#define FOR4(a, b, c, d, v) for (auto [a, b, c, d] : v)
#define FOR3(a, b, c, v) for (auto [a, b, c] : v)
#define FOR2(a, b, v) for (auto [a, b] : v)
#define FOR1(a, v) for (auto a : v)
#define FOR(...) overload5(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define AFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v)
#define AFOR3(a, b, c, v) for (auto &[a, b, c] : v)
#define AFOR2(a, b, v) for (auto &[a, b] : v)
#define AFOR1(a, v) for (auto &a : v)
#define AFOR(...)                                                              \
    overload5(__VA_ARGS__, AFOR4, AFOR3, AFOR2, AFOR1)(__VA_ARGS__)

#define CFOR4(a, b, c, d, v) for (const auto &[a, b, c, d] : v)
#define CFOR3(a, b, c, v) for (const auto &[a, b, c] : v)
#define CFOR2(a, b, v) for (const auto &[a, b] : v)
#define CFOR1(a, v) for (const auto &a : v)
#define CFOR(...)                                                              \
    overload5(__VA_ARGS__, CFOR4, CFOR3, CFOR2, CFOR1)(__VA_ARGS__)

#define RFOR4(a, b, c, d, v) for (auto [a, b, c, d] : v | std::views::reverse)
#define RFOR3(a, b, c, v) for (auto [a, b, c] : v | std::views::reverse)
#define RFOR2(a, b, v) for (auto [a, b] : v | std::views::reverse)
#define RFOR1(a, v) for (auto a : v | std::views::reverse)
#define RFOR(...)                                                              \
    overload5(__VA_ARGS__, RFOR4, RFOR3, RFOR2, RFOR1)(__VA_ARGS__)

#define RAFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v | std::views::reverse)
#define RAFOR3(a, b, c, v) for (auto &[a, b, c] : v | std::views::reverse)
#define RAFOR2(a, b, v) for (auto &[a, b] : v | std::views::reverse)
#define RAFOR1(a, v) for (auto &a : v | std::views::reverse)
#define RAFOR(...)                                                             \
    overload5(__VA_ARGS__, RAFOR4, RAFOR3, RAFOR2, RAFOR1)(__VA_ARGS__)

#define RCFOR4(a, b, c, d, v)                                                  \
    for (const auto &[a, b, c, d] : v | std::views::reverse)
#define RCFOR3(a, b, c, v) for (const auto &[a, b, c] : v | std::views::reverse)
#define RCFOR2(a, b, v) for (const auto &[a, b] : v | std::views::reverse)
#define RCFOR1(a, v) for (const auto &a : v | std::views::reverse)
#define RCFOR(...)                                                             \
    overload5(__VA_ARGS__, RCFOR4, RCFOR3, RCFOR2, RCFOR1)(__VA_ARGS__)

#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define SORT(v) std::ranges::sort(v)
#define RSORT(v) sort(RALL(v))
#define REVERSE(v) std::ranges::reverse(v)
#define UNIQUE(v) SORT(v), v.erase(unique(ALL(v)), v.end())
#define SZ(v) int(v.size())
#define MAX(v) std::ranges::max(v)
#define MIN(v) std::ranges::min(v)
template <typename T>
std::conditional_t<std::is_same_v<T, int>, ll, T> SUM(const std::vector<T> &v) {
    return std::accumulate(
        ALL(v), std::conditional_t<std::is_same_v<T, int>, ll, T>(0));
}

TYPES(T) void input(T &...a) { (std::cin >> ... >> a); }
#define DECLARE(T, ...)                                                        \
    T __VA_ARGS__;                                                             \
    input(__VA_ARGS__);
#define INT(...) DECLARE(int, __VA_ARGS__)
#define STR(...) DECLARE(std::string, __VA_ARGS__)
#define LL(...) DECLARE(long long, __VA_ARGS__)
#define CHR(...) DECLARE(char, __VA_ARGS__)
#define DBL(...) DECLARE(double, __VA_ARGS__)
#define VI(n, v)                                                               \
    vi v(n);                                                                   \
    std::cin >> v;
#define VLL(n, v)                                                              \
    vll v(n);                                                                  \
    std::cin >> v;
#define VS(n, s)                                                               \
    std::vector<std::string> s(n);                                             \
    std::cin >> s;

TYPE(T, S) std::istream &operator>>(std::istream &is, std::pair<T, S> &p) {
    is >> p.first >> p.second;
    return is;
}
TYPE(T, S)
std::ostream &operator<<(std::ostream &os, const std::pair<T, S> &p) {
    os << p.first << " " << p.second;
    return os;
}
TYPE(T) istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &a : v)
        std::cin >> a;
    return is;
}
TYPE(T) std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    if (&os == &std::cerr)
        os << "[";
    REP (i, v.size()) {
        os << v[i];
        if (i + 1 < v.size())
            os << (&os == &std::cerr ? "," : " ");
    }
    if (&os == &std::cerr)
        os << "]";
    return os;
}

#ifdef __DEBUG
#include <debug>
#else
#define debug(...) void(0)
#endif

void print() { cout << '\n'; }
TYPES(T, Ts) void print(const T &a, const Ts &...b) {
    std::cout << a;
    (std::cout << ... << (std::cout << ' ', b));
    std::cout << '\n';
}

TYPE(T) using pq = std::priority_queue<T>;
TYPE(T) using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
TYPE(T) T pick(std::queue<T> &que) {
    assert(que.size());
    T a = que.front();
    que.pop();
    return a;
}
TYPE(T) T pick(pq<T> &que) {
    assert(que.size());
    T a = que.top();
    que.pop();
    return a;
}
TYPE(T) T pick(pqg<T> &que) {
    assert(que.size());
    T a = que.top();
    que.pop();
    return a;
}
TYPE(T) T pick(std::stack<T> &sta) {
    assert(sta.size());
    T a = sta.top();
    sta.pop();
    return a;
}
TYPE(T) void clear(T &v) { v = decltype(v)(); }

std::string YES(bool f = true) { return (f ? "YES" : "NO"); }
std::string Yes(bool f = true) { return (f ? "Yes" : "No"); }
std::string yes(bool f = true) { return (f ? "yes" : "no"); }

constexpr int INF = 1e9 + 7;
constexpr ll LINF = ll(1e18) + 7;
constexpr ld EPS = 1e-10;

vi iota(int n) {
    vi a(n);
    std::iota(ALL(a), 0);
    return a;
}
TYPE(T) void add(std::vector<T> &v, T a = 1) {
    AFOR (p, v)
        p += a;
}
TYPE(T) T rev(T a) {
    REVERSE(a);
    return a;
}
TYPE(T) void fin(T a) {
    std::cout << a << '\n';
    exit(0);
}
TYPE(T) bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
TYPE(T) bool chmin(T &a, T b) { return (a > b && (a = b, true)); }
TYPES(T, Ns) auto make_vector(T x, int n, Ns... ns) {
    if constexpr (sizeof...(ns) == 0)
        return std::vector<T>(n, x);
    else
        return std::vector(n, make_vector<T>(x, ns...));
}
bool in(const ll S, const int a) { return (S >> a) & 1; }
int digit(char c) { return (c >= '0' and c <= '9' ? c - '0' : -1); }

void signal_hander(int signal) { std::exit(EXIT_FAILURE); }
#endif
#pragma endregion template

ll pw(ll n, int k) {
    assert(k >= 0);
    ll res = 1;
    while (k) {
        if (k & 1)
            res *= n;
        n *= n;
        k >>= 1;
    }
    return res;
}

ll f(ll x) {
    // x 未満
    if (x <= 10)
        return 0;
    auto s = std::to_string(x);
    ll res = 0;
    {
        // s より短いやつ
        for (int len = 2; len < s.size(); len++) {
            for (int x = 1; x <= 9; x++) {
                res += pw(x, len - 1);
            }
        }
    }
    debug(res);
    {
        // s と長さが同じで s より top が小さい
        for (int x = 1; x < s[0] - '0'; x++)
            res += pw(x, s.size() - 1);
    }
    debug(res);
    {
        // s に似てるやつ
        for (int i = 1; i < s.size(); i++) {
            if (s[0] > s[i]) {
                // [0, s[i]) を使う
                res += (s[i] - '0') * pw(s[0] - '0', s.size() - i - 1);

                // s[i] を使うパターンは後で
            } else {
                // [0, s[0]) を使う
                res += pw(s[0] - '0', s.size() - i);
                break;
            }
        }
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::signal(SIGABRT, signal_hander);

    LL(l, r);
    fin(f(r + 1) - f(l));
}
// 10, 20, 21, 30, 31, 32

Go solution:
package main

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

// 整数べき乗（base^exp）を計算
func ipow(base int64, exp int) int64 {
    result := int64(1)
    for i := 0; i < exp; i++ {
        result *= base
    }
    return result
}

// x がスネーク数かどうかを判定
func isSnake(x int64) bool {
    s := strconv.FormatInt(x, 10)
    head := int(s[0] - '0')
    for i := 1; i < len(s); i++ {
        if int(s[i]-'0') >= head {
            return false
        }
    }
    return true
}

// x のスネーク数としての順位を数える（countSnake）
func countSnake(x int64) int64 {
    s := strconv.FormatInt(x, 10)
    head := int(s[0] - '0')
    n := len(s)
    var d, m int64 = 0, 0

    // 先頭が小さい／桁が少ないスネーク数の個数 (d) を求める
    for i := 1; i < n; i++ {
        if i < n-1 {
            for j := 1; j <= 9; j++ {
                d += ipow(int64(j), i)
            }
        } else {
            for j := 1; j < head; j++ {
                d += ipow(int64(j), i)
            }
        }
    }
    // 同じ桁数・先頭の場合の順位 (m) を計算
    for i := 1; i < n; i++ {
        c := int(s[i] - '0')
        if c >= head {
            m += ipow(int64(head), n-i)
            break
        } else {
            m += int64(c) * ipow(int64(head), n-i-1)
        }
    }
    return d + m
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    line, _ := reader.ReadString('\n')
    parts := strings.Fields(line)
    if len(parts) < 2 {
        return
    }
    L, _ := strconv.ParseInt(parts[0], 10, 64)
    R, _ := strconv.ParseInt(parts[1], 10, 64)
    p := countSnake(L)
    q := countSnake(R)
    if isSnake(R) {
        fmt.Println(q - p + 1)
    } else {
        fmt.Println(q - p)
    }
}

Java solution:
import java.util.*;
import java.io.*;
import java.util.function.*;
//雛形
public class Main{
	public static void main(String[] args) {
		FastScanner stdin = new FastScanner(System.in);
		long L = stdin.nextLong();
		long R = stdin.nextLong();
		System.out.println(func(R)-func(L-1));
		//long k=func(99);
		//for(int i=100;i<1000;i++){
		//	long next = func(i);
		//	if(func(i)>k){
		//		System.out.println(i);
		//	}
		//	k=next;
		//}
		stdin.close();
	}
	static long func(long x){
		long foo = x;
		int keta = 0;
		while (foo>0) {
			keta++;
			foo=foo/10;
		}
		foo = x;
		long[] array = new long[keta];
		int i=0;
		while (foo>0) {
			array[i] = foo%10;
			i++;
			foo=foo/10;
		}
		if(keta==1){
			return 0;
		}
		long ans = 0;
		for(int j=2;j<keta;j++){
			for(int k=1;k<10;k++){
				ans += mypow(k, j-1);
			}
		}
		for(int k=1;k<array[keta-1];k++){
			ans += mypow(k, keta-1);
		}
		ans += func_main(array,keta-1,array[keta-1]);
		return ans;
	}
	static long func_main(long[] array,int keta,long lim){
		if(keta==1){
			return Long.min(lim, array[0]+1);
		}else if(lim <=array[keta-1]){
			return mypow(lim, keta);
		}
		long ans=0;
		ans += mypow(lim, keta-1)*(array[keta-1]);
		ans += func_main(array, keta-1, lim);
		return ans;

	}
	static long mypow(long a,long b){
		long ans = 1;
		for(int i =0 ;i<b;i++){
			ans =ans*a;
		}
		return ans;

	}
	//しきい値以下でtrueとなるpredを与えると、閾値を求めてくれる。探索範囲は[a,b)
	static int binary_search(int a,int b,Predicate<Integer> pred){
		if(!pred.test(a)){
			return a;
		}else if(pred.test(b)){
			return b;
		}
		return binary_search_main(a,b,pred);
	}
	static int binary_search_main(int a,int b,Predicate<Integer> pred){
		if(b-a<3){
			boolean now = pred.test(a);
			boolean next = true;
			for(int i=a;i<b;i++){
				next = pred.test(i+1);
				if(now&&!next){
					return i;
				}
				now = next;
			}
			return b;
		}else{
			int t =(a+b)/2;
			if(pred.test(t)){
				return binary_search_main(t, b, pred);
			}else{
				return binary_search_main(a, t, pred);
			}
		}
	}
}
class FastScanner implements Closeable {
	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	public FastScanner(InputStream in) {
		this.in = in;
	}
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) nl;
	}
	public double nextDouble() { return Double.parseDouble(next());}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
	}
}

JavaScript solution:
function Main(input) {
	input = load(input)
	let [L, R] = toStr(input[0])
	L = toBigInt(String(BigInt(L) - 1n, 10))
	R = toBigInt(R)

	let left = 0n
	let len = 2n
	while (len <= BigInt(L.length)) {
		const end = len !== BigInt(L.length) ? 9n : L[0]-1n
		for (let i=1n; i<=end; i++) {
			left += i**(len-1n)
		}
		len++
	}
	//console.log(left)

	for (let i = 1; i < L.length; i++) {
		if (L[i] >= L[0]) {
			left += L[0]**BigInt(L.length - i - 1) * (L[0]>L[i] ? L[i] : L[0])
			break
		}
		else {
			left += L[0]**BigInt(L.length - i - 1) * (L[0]>L[i] ? L[i] : L[0])
		}
		if (i === L.length - 1) {
			left++
		}
	}

	let right = 0n
	len = 2n
	while (len <= BigInt(R.length)) {
		const end = len !== BigInt(R.length) ? 9n : R[0]-1n
		for (let i=1n; i<=end; i++) {
			right += i**(len-1n)
		}
		len++
	}
	//console.log(right)

	for (let i = 1; i < R.length; i++) {
		if (R[i] >= R[0]) {
			right += R[0]**BigInt(R.length - i - 1) * (R[0]>R[i] ? R[i] : R[0])
			break
		}
		else {
			right += R[0]**BigInt(R.length - i - 1) * (R[0]>R[i] ? R[i] : R[0])
		}
		if (i === R.length - 1) {
			right++
		}
	}

	//console.log(left, right)
	console.log(String(right-left, 10))
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

function load(input) {
	return input.trim().split("\n")
}

function toStr(row) {
	return row.split(" ")
}

function toNum(row) {
	return row.split("").map(Number)
}

function toBigInt(row) {
	return row.split("").map(BigInt)
}

Python solution:
def snake_num(X: int):
    # dp[keta][max_digit][is_limit][is_zero]
    str_x = str(X)
    keta = len(str_x)
    dp = [[[[0] * 2 for _ in range(2)] for _ in range(10)] for _ in range(keta)]

    init_num = int(str_x[0])
    dp[0][init_num][1][0] = 1
    for i in range(1, init_num):
        dp[0][i][0][0] = 1
    dp[0][0][0][1] = 1

    for k in range(1, keta):
        # non limit -> non limit
        for d1 in range(10):
            dp[k][d1][0][0] += dp[k - 1][d1][0][0] * d1
        for d2 in range(1, 10):
            dp[k][d2][0][0] += dp[k - 1][0][0][1]
        dp[k][0][0][1] += dp[k - 1][0][0][1]

        # limit -> limit
        now_x = int(str_x[k])
        if now_x < init_num:
            dp[k][init_num][1][0] += dp[k - 1][init_num][1][0]

        # limit -> non limit
        dp[k][init_num][0][0] += dp[k - 1][init_num][1][0] * min(now_x, init_num)

    ret = 0
    for d1 in range(10):
        for is_limit in range(2):
            for is_zero in range(2):
                ret += dp[keta - 1][d1][is_limit][is_zero]
    return ret


L, R = map(int, input().split())
ans = snake_num(R) - snake_num(L - 1)
print(ans)

Ruby solution:
def int_pow(a, t)
  res = 1
  t.times { res *= a }
  res
end

# r以下のヘビ数を求める
def count(r)
  digit = []
  while r > 0
    digit.push(r % 10)
    r /= 10
  end
  # 各桁の整数が入ったlistが作られる
  digit.reverse!
  # nは桁数
  n = digit.size
  res = 0

  # 整数が
  # x.......
  # のとき、
  # x0000000
  # から
  # x.......
  # まで考える
  (1..n).each do |i|
    if i == n
      res += 1
      break
    end
    # 整数がx...y...のとき、
    # で、今やってる桁がyについて考えているとき
    # その桁の値がy-1以下のものはすべてやりつくした、というイメージ
    res += int_pow(digit[0], n - 1 - i) * [digit[0], digit[i]].min
    break if digit[i] >= digit[0]
  end

  # 整数が
  # x.......
  # のとき、
  # 0
  # から
  # (x-1)9999999
  # まで考える
  # 1桁は、すべてヘビ数としている（どうせ相殺される）
  n.times do |i|
    mx = i == 0 ? digit[0] - 1 : 9
    (1..mx).each do |j|
      res += int_pow(j, n - 1 - i)
    end
  end

  res
end

l, r = gets.split.map(&:to_i)
puts count(r) - count(l - 1)