355A.md (1945B)
1 Source: https://codeforces.com/problemset/problem/355/A 2 3 A. Vasya and Digital Root 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 stdin 16 17 output 18 19 stdout 20 21 Vasya has recently found out what a digital root of a number is and he decided to share his knowledge with you. 22 23 Let's assume that *S*(*n*) is the sum of digits of number *n*, for example, *S*(4098) = 4 + 0 + 9 + 8 = 21. Then the digital root of number *n* equals to: 24 25 1. *dr*(*n*) = *S*(*n*), if *S*(*n*) < 10; 26 2. *dr*(*n*) = *dr*( *S*(*n*) ), if *S*(*n*) ≥ 10. 27 28 For example, *dr*(4098) = *dr*(21) = 3. 29 30 Vasya is afraid of large numbers, so the numbers he works with are at most 101000. For all such numbers, he has proved that *dr*(*n*) = *S*( *S*( *S*( *S*(*n*) ) ) ) (*n* ≤ 101000). 31 32 Now Vasya wants to quickly find numbers with the given digital root. The problem is, he hasn't learned how to do that and he asked you to help him. You task is, given numbers *k* and *d*, find the number consisting of exactly *k* digits (the leading zeroes are not allowed), with digital root equal to *d*, or else state that such number does not exist. 33 34 Input 35 36 The first line contains two integers *k* and *d* (1 ≤ *k* ≤ 1000; 0 ≤ *d* ≤ 9). 37 38 Output 39 40 In a single line print either any number that meets the requirements (without the leading zeroes) or "No solution" (without the quotes), if the corresponding number does not exist. 41 42 The chosen number must consist of exactly *k* digits. We assume that number 0 doesn't contain any leading zeroes. 43 44 Examples 45 46 Input 47 48 ``` 49 4 4 50 ``` 51 52 Output 53 54 ``` 55 5881 56 ``` 57 58 Input 59 60 ``` 61 5 1 62 ``` 63 64 Output 65 66 ``` 67 36172 68 ``` 69 70 Input 71 72 ``` 73 1 0 74 ``` 75 76 Output 77 78 ``` 79 0 80 ``` 81 82 Note 83 84 For the first test sample *dr*(5881) = *dr*(22) = 4. 85 86 For the second test sample *dr*(36172) = *dr*(19) = *dr*(10) = 1.