B. Ordinary Numbers | #719 Div.3

LONGNEW·2021년 7월 11일
0

CP

목록 보기
30/155

https://codeforces.com/contest/1520/problem/B
시간 2초, 메모리 256MB

input :

  • t (1 ≤ t ≤ 104)
  • n (1 ≤ n ≤ 109)

output :

  • For each test case output the number of ordinary numbers among numbers from 1 to n.
    각 테스트케이스에서 평범한 숫자의 개수를 출력한다.

조건 :

  • Let's call a positive integer n ordinary if in the decimal notation all its digits are the same. For example, 1, 2 and 99 are ordinary numbers, but 719 and 2021 are not ordinary numbers.
    수를 이루고 있는 모든 숫자가 동일한 경우 이 숫자 n을 평범하다 한다.

모든 경우를 1 ~ n까지 확인하는 것은 당연히 시간이 부족하다.
차라리 평범한 놈들을 다 만들어서 한다면?

3자리 수라면 111, 222, 333, 444 ... 9개이고
4자리 여도 1111, 2222, 3333, 4444, ... 9개인걸 보면
전체를 다 만들어도 몇 개 안 된다.

그러니까 이 전체를 배열로 만들어서 개수를 세면 정답을 얻을 수 있다.

import sys

data = []
for j in range(1, 10):
    num = j
    data.append(num)
    while num < 1000000000:
        num *= 10
        num += j
        data.append(num)
data.sort()

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    cnt = 0

    for item in data:
        if n < item:
            print(cnt)
            break

        cnt += 1

0개의 댓글