fork download
copy 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 12
  13. #define MAX 1037471823
  14. #define Q 103
  15.  
  16. using namespace std;
  17.  
  18. int n, s[MS], a, ans, m[MS][MS];
  19.  
  20. int main()
  21. {
  22. 	rep(i, 0, 9) m[0][i] = 1;
  23. 	rep(i, 1, 10) rep(j, 0, 9) rep(k, 0, 9) if (abs(j-k) > 1) m[i][j] += m[i-1][k];
  24. 	rep(i, 0, 10) rep(j, 1, 9) m[i][10] += m[i][j];
  25. 	rep(i, 1, 10) m[i][10] += m[i-1][10];
  26. 	rep(i, 0, 10) s[i] = MAX;
  27. 	scanf("%d", &n); n -= 1; a = -1; 
  28. 	while (n > 0) s[++a] = n % 10, n /= 10;
  29. 	if (a > 0) ans += m[a-1][10];
  30. 	if (a >= 0) ans -= m[a][0];
  31. 	down(i, a, 0) 
  32. 	{
  33. 		rep(j, 0, s[i]-1) 
  34. 			if (abs(j-s[i+1]) > 1) ans += m[i][j];
  35. 		if (abs(s[i]-s[i+1]) <= 1) break;
  36. 		if (i == 0) ans += m[0][s[0]];
  37. 	}
  38. 	ans *= -1;
  39. 	rep(i, 0, 10) s[i] = MAX;
  40. 	scanf("%d", &n); a = -1; 
  41. 	while (n > 0) s[++a] = n % 10, n /= 10;
  42. 	if (a > 0) ans += m[a-1][10];
  43. 	if (a >= 0) ans -= m[a][0];
  44. 	down(i, a, 0) 
  45. 	{
  46. 		rep(j, 0, s[i]-1) 
  47. 			if (abs(j-s[i+1]) > 1) ans += m[i][j];
  48. 		if (abs(s[i]-s[i+1]) <= 1) break;
  49. 		if (i == 0) ans += m[0][s[0]];
  50. 	}
  51. 	printf("%d\n", ans);
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
25 50
stdout
copy 
20
https://ideone.com/siRjmH
BZOJ 1026
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!