codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1277A.md (1596B)


      1 Source: https://codeforces.com/problemset/problem/1277/A
      2 
      3 A. Happy Birthday, Polycarp!
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Hooray! Polycarp turned $n$ years old! The Technocup Team sincerely congratulates Polycarp!
     22 
     23 Polycarp celebrated all of his $n$ birthdays: from the $1$-th to the $n$-th. At the moment, he is wondering: how many times he turned beautiful number of years?
     24 
     25 According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: $1$, $77$, $777$, $44$ and $999999$. The following numbers are not beautiful: $12$, $11110$, $6969$ and $987654321$.
     26 
     27 Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).
     28 
     29 Help Polycarpus to find the number of numbers from $1$ to $n$ (inclusive) that are beautiful.
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.
     34 
     35 Each test case consists of one line, which contains a positive integer $n$ ($1 \le n \le 10^9$) — how many years Polycarp has turned.
     36 
     37 Output
     38 
     39 Print $t$ integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between $1$ and $n$, inclusive.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 6
     47 18
     48 1
     49 9
     50 100500
     51 33
     52 1000000000
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 10
     59 1
     60 9
     61 45
     62 12
     63 81
     64 ```
     65 
     66 Note
     67 
     68 In the first test case of the example beautiful years are $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ and $11$.