Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.77 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class hillnumber {
  4.  
  5. static int[] a;
  6. static long[][][][] dp;
  7.  
  8. public static void main(String[] args) {
  9. Scanner scan = new Scanner(System.in);
  10. long g = scan.nextLong();
  11. String s = g+"";
  12. a = new int[s.length()];
  13. dp = new long[s.length()][10][2][2];
  14. for(int i = 0; i < s.length(); i++) {
  15. a[i] = s.charAt(i) - '0';
  16. for(int j = 0; j <= 9; j++) {
  17. for(int k = 0; k < 2; k++) {
  18. dp[i][j][k][0] = -1;
  19. dp[i][j][k][1] = -1;
  20. }
  21. }
  22. }
  23. if(!check(a)) System.out.println(-1);
  24. else {
  25. long res = go(0, a[0], 1, 0);
  26. for(int i = 0; i < a[0]; i++) {
  27. res += go(0, i, 0, 0);
  28. }
  29. System.out.println(res-1);
  30. }
  31. }
  32. static long go(int index, int digit, int fixed, int falling) {
  33. if(dp[index][digit][fixed][falling] != -1) return dp[index][digit][fixed][falling];
  34. if(digit > a[index] && fixed == 1) return dp[index][digit][fixed][falling] = 0;
  35. if(index == a.length - 1) return dp[index][digit][fixed][falling] = 1;
  36. long res = 0;
  37. if(falling == 0) {
  38. for(int i = digit; i <= 9; i++) {
  39. if(fixed == 1 && digit < a[index]) res += go(index+1,i,0,0);
  40. else res += go(index+1,i,fixed,0);
  41. }
  42. for(int i = digit - 1; i >= 0; i--) {
  43. if(fixed == 1 && digit < a[index]) res += go(index+1,i,0,1);
  44. else res += go(index+1, i, fixed,1);
  45. }
  46. }
  47. else {
  48. for(int i = digit; i >= 0; i--) {
  49. if(fixed == 1 && digit < a[index]) res += go(index+1,i,0,1);
  50. else res += go(index+1, i, fixed,1);
  51. }
  52. }
  53. return dp[index][digit][fixed][falling] = res;
  54. }
  55.  
  56.  
  57. static boolean check(int[] b) {
  58. boolean falling = false;
  59. for(int x = 1; x < b.length; x++) {
  60. if(b[x] < b[x-1]) falling = true;
  61. else if(b[x] > b[x-1] && falling) return false;
  62. }
  63. return true;
  64. }
  65.  
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement