Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class hillnumber {
- static int[] a;
- static long[][][][] dp;
- public static void main(String[] args) {
- Scanner scan = new Scanner(System.in);
- long g = scan.nextLong();
- String s = g+"";
- a = new int[s.length()];
- dp = new long[s.length()][10][2][2];
- for(int i = 0; i < s.length(); i++) {
- a[i] = s.charAt(i) - '0';
- for(int j = 0; j <= 9; j++) {
- for(int k = 0; k < 2; k++) {
- dp[i][j][k][0] = -1;
- dp[i][j][k][1] = -1;
- }
- }
- }
- if(!check(a)) System.out.println(-1);
- else {
- long res = go(0, a[0], 1, 0);
- for(int i = 0; i < a[0]; i++) {
- res += go(0, i, 0, 0);
- }
- System.out.println(res-1);
- }
- }
- static long go(int index, int digit, int fixed, int falling) {
- if(dp[index][digit][fixed][falling] != -1) return dp[index][digit][fixed][falling];
- if(digit > a[index] && fixed == 1) return dp[index][digit][fixed][falling] = 0;
- if(index == a.length - 1) return dp[index][digit][fixed][falling] = 1;
- long res = 0;
- if(falling == 0) {
- for(int i = digit; i <= 9; i++) {
- if(fixed == 1 && digit < a[index]) res += go(index+1,i,0,0);
- else res += go(index+1,i,fixed,0);
- }
- for(int i = digit - 1; i >= 0; i--) {
- if(fixed == 1 && digit < a[index]) res += go(index+1,i,0,1);
- else res += go(index+1, i, fixed,1);
- }
- }
- else {
- for(int i = digit; i >= 0; i--) {
- if(fixed == 1 && digit < a[index]) res += go(index+1,i,0,1);
- else res += go(index+1, i, fixed,1);
- }
- }
- return dp[index][digit][fixed][falling] = res;
- }
- static boolean check(int[] b) {
- boolean falling = false;
- for(int x = 1; x < b.length; x++) {
- if(b[x] < b[x-1]) falling = true;
- else if(b[x] > b[x-1] && falling) return false;
- }
- return true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement