#!/usr/bin/env python3 import sys from typing import Optional, Iterator def magnitude(x : int) -> int: assert x >= 0 return len(str(x)) def delta(order : int) -> int: return 10**order + 1 def sum_1_to_excl(x : int) -> int: return x * (x - 1) // 2 def sum_1_to_incl(x : int) -> int: return x * (x + 1) // 2 # incl. both bounds def sum_from_to_incl(lo : int, hi : int) -> int: if lo > hi: return 0 return sum_1_to_incl(hi) - sum_1_to_excl(lo) def div2(x : int) -> Optional[int]: if x % 2: return None else: return x // 2 # inclusive both bounds def sum_invalid_ids(lo : int, hi : int) -> int: total = 0 while True: magnitude_lo = magnitude(lo) order_lo = div2(magnitude_lo) if order_lo is None: # no invalid IDs in that order of magnitude lo = 10**magnitude_lo continue magnitude_hi = magnitude(hi) d = delta(order_lo) if magnitude_lo > magnitude_hi: # this can happen with odd magnitude_hi break elif magnitude_lo == magnitude_hi: assert lo <= hi, f"{lo} <= {hi}" total += d * sum_from_to_incl((lo-1)//d + 1, hi // d) break assert magnitude_lo < magnitude_hi surrogate_hi = 10**magnitude_lo - 1 assert lo <= surrogate_hi, f"{lo} <= {surrogate_hi}" total += d * sum_from_to_incl((lo-1)//d + 1, surrogate_hi // d) lo = surrogate_hi + 1 return total def consolidate(rngs : list[tuple[int, int]]) -> Iterator[tuple[int, int]]: rngs = sorted(rngs) cur = None for lo, hi in rngs: match cur: case None: cur = lo, hi case cur_lo, cur_hi: if lo <= cur_hi+1: cur = cur_lo, hi else: yield cur cur = lo, hi assert cur yield cur if __name__ == '__main__': ranges = [ (int(lo_s), int(hi_s)) for lo_s, hi_s in ( rng.split('-') for rng in sys.stdin.read().strip().split(',') ) ] total = 0 for lo, hi in consolidate(ranges): total += sum_invalid_ids(lo, hi) print(total)