[URI ONLINE JUDGE] – 2066 – melborP A

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s