제출 #490737

#제출 시각아이디문제언어결과실행 시간메모리
490737tht2005Palindrome-Free Numbers (BOI13_numbers)C++14
38.75 / 100
1 ms340 KiB
#include <stdio.h> #include <string.h> #define LL long long int n; char s[20]; LL dp[19][11][11][2][2]; LL calc(int i, int j, int k, int tight, int lz) { if(i == n) return 1; LL& res = dp[i][j][k][tight][lz]; if(~res) return res; res = 0; if(tight) { if(lz) { res += calc(i + 1, 10, 10, 1, 1); for(int dig = 1; dig < 10; ++dig) res += calc(i + 1, 10, dig, 1, 0); } else { for(int dig = 0; dig < 10; ++dig) { if(dig != j && dig != k) res += calc(i + 1, k, dig, 1, 0); } } } else { if(lz) { res += calc(i + 1, 10, 10, s[i] > '0', 1); for(int dig = 1; dig < s[i] - '0'; ++dig) res += calc(i + 1, k, dig, 1, 0); if(s[i] > '0' && s[i] != j + '0' && s[i] != k + '0') res += calc(i + 1, k, s[i] - '0', 0, 0); } else { for(int dig = 0; dig < s[i] - '0'; ++dig) { if(dig != j && dig != k) { res += calc(i + 1, k, dig, 1, 0); } } if(s[i] != j + '0' && s[i] != k + '0') res += calc(i + 1, k, s[i] - '0', 0, 0); } } return res; } LL f(LL N) { sprintf(s, "%d", N); n = strlen(s); memset(dp, -1, sizeof(dp)); return calc(0, 10, 10, 0, 1); } int main() { LL L, R; scanf("%lld %lld", &L, &R); printf("%lld", f(R) - f(L - 1)); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

numbers.cpp: In function 'long long int f(long long int)':
numbers.cpp:50:18: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   50 |     sprintf(s, "%d", N);
      |                 ~^   ~
      |                  |   |
      |                  int long long int
      |                 %lld
numbers.cpp: In function 'int main()':
numbers.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld %lld", &L, &R);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...