1143B.md (1055B)
1 Source: https://codeforces.com/problemset/problem/1143/B 2 3 B. Nirvana 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 Kurt reaches nirvana when he finds the product of all the digits of some positive integer. Greater value of the product makes the nirvana deeper. 22 23 Help Kurt find the maximum possible product of digits among all integers from $1$ to $n$. 24 25 Input 26 27 The only input line contains the integer $n$ ($1 \le n \le 2\cdot10^9$). 28 29 Output 30 31 Print the maximum product of digits among all integers from $1$ to $n$. 32 33 Examples 34 35 Input 36 37 ``` 38 390 39 ``` 40 41 Output 42 43 ``` 44 216 45 ``` 46 47 Input 48 49 ``` 50 7 51 ``` 52 53 Output 54 55 ``` 56 7 57 ``` 58 59 Input 60 61 ``` 62 1000000000 63 ``` 64 65 Output 66 67 ``` 68 387420489 69 ``` 70 71 Note 72 73 In the first example the maximum product is achieved for $389$ (the product of digits is $3\cdot8\cdot9=216$). 74 75 In the second example the maximum product is achieved for $7$ (the product of digits is $7$). 76 77 In the third example the maximum product is achieved for $999999999$ (the product of digits is $9^9=387420489$).