A *reverse number* of a natural number **N** is the number which we obtain when we read the digits of **N** from the right to the left. For example, the reverse number of 1234 is 4321 and the reverse number of 150 (a number with 3 digits) is 51 (a number with 2 digits). In this problem, we say that a number is *well-reversible* if it is strictly less than its reverse number. Examples of well-reversible numbers are 1234, 15 and 819.

## Input

The single line of the input consists of a single positive integer **K** (**K** ≤ 18).

## Output

The single line of the output shall consist singly of the number of numbers with exact **K** digits which are well-reversible.

Input Samples | Output Samples |

1 | 0 |

2 | 36 |

18 | 404999999550000000 |

solution:

<br /> #include <bits/stdc++.h> #define ll long long using namespace std; ll pal(int x) { x = x/2LL; ll res = 9LL; for(int i = 1; i < x; i++) { res *= 10LL; } return res; } int main() { ll ans[20]; ans[1] = 0LL; ans[2] = 36LL; for(int i = 3; i <=18; i++) { if(i % 2 == 1) { ans[i] = ans[i - 1] * 10LL; } else { ans[i] = ans[i - 2] * 100LL; ans[i] += 45LL * pal(i - 2); } } int k; cin >> k; printf("%lld\n", ans[k]); return 0; }

Advertisements