Submission #37604

#TimeUsernameProblemLanguageResultExecution timeMemory
3760414kgPalindrome-Free Numbers (BOI13_numbers)C++11
100 / 100
0 ms1132 KiB
#include <stdio.h> bool check[11][11][21]; long long d[11][11][21]; long long f(int x, int y, int len) { if (len == 0) return 1; if (!check[x][y][len]) { check[x][y][len] = true; if (x == 10 && y == 10) { for (int i = 1; i < 10; i++) d[x][y][len] += f(10, i, len - 1); d[x][y][len] += f(10, 10, len - 1); } else if (x == 10) { for (int i = 0; i < 10; i++) if (i != y) d[x][y][len] += f(y, i, len - 1); } else { for (int i = 0; i < 10; i++) { if (i == x || i == y) continue; d[x][y][len] += f(y, i, len - 1); } } } return d[x][y][len]; } long long out(long long x) { long long sum = 0, check_m; int len = 0, temp[21] = { 0 }, in[21] = { 0 }; while (x) temp[++len] = x % 10, x /= 10; for (int i = 1; i <= len; i++) in[len - i + 1] = temp[i]; in[0] = 10; for (int i = len; i >= 2; i--) { check_m = 1; for (int j = 2; j < i; j++) if (in[j - 2] == in[j] || in[j - 1] == in[j]) check_m = 0; for (int j = 0; j < in[i]; j++) if (j != in[i - 1] && j != in[i - 2]) sum += f(in[i - 1], j, len - i)*check_m; } for (int i = 1; i < in[1]; i++) sum += f(10, i, len - 1); sum += f(10, 10, len - 1); check_m = 1; for (int j = 2; j <=len; j++) if (in[j - 2] == in[j] || in[j - 1] == in[j]) check_m = 0; return sum + check_m; } int main() { long long x, y, sum; scanf("%lld %lld", &x, &y); sum = y ? out(y) : 1; if (x > 1) sum -= out(x - 1); else if (x == 1) sum -= 1; printf("%lld", sum); }

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:58:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &x, &y); 
                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...