Submission #77608

#	Time	Username	Problem	Language	Result	Execution time	Memory
77608		xiaowuc1	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	3 ms	748 KiB

numbers

#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

ll dp[25][11][11][2][2];
bool seen[25][11][11][2][2];

ll solve(vector<int>& digits, int idx, int a, int b, int constrained, int first) {
  if(seen[idx][a][b][constrained][first]) return dp[idx][a][b][constrained][first];
  seen[idx][a][b][constrained][first] = true;
  if(idx == digits.size()) {
    dp[idx][a][b][constrained][first] = 1;
    return 1;
  }
  for(int i = 0; i <= 9 && (i <= digits[idx] || !constrained); i++) {
    if(i == a || i == b) continue;
    int nc = constrained == 1 && i == digits[idx] ? 1 : 0;
    int nf = first == 0 || i > 0 ? 0 : 1;
    int na = i == 0 && first ? a : b;
    int nb = i == 0 && first ? b : i;
    dp[idx][a][b][constrained][first] += solve(digits, idx+1, na, nb, nc, nf);
  }
  return dp[idx][a][b][constrained][first];
}

ll solve(ll n) {
  if(n < 0) return 0;
  vector<int> digits;
  while(n) {
    digits.push_back(n%10);
    n /= 10;
  }
  reverse(digits.begin(), digits.end());
  memset(dp, 0, sizeof(dp));
  memset(seen, 0, sizeof(seen));
  return solve(digits, 0, 10, 10, 1, 1);
}

int main() {
  ll a, b;
  scanf("%lld %lld", &a, &b);
  printf("%lld\n", solve(b) - solve(a-1));
}

Compilation message (stderr)

numbers.cpp: In function 'll solve(std::vector<int>&, int, int, int, int, int)':
numbers.cpp:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx == digits.size()) {
      ~~~~^~~~~~~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75