Submission #561872

#	Time	Username	Problem	Language	Result	Execution time	Memory
561872		tj14	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	340 KiB

numbers

#include <cstdio>
#include <algorithm>

#define ll long long

using namespace std;

ll dp[20][12][12];
int N;

ll kat(int st){
  for(int c = st+1 ; c <= N ; c++)
    for(int d = 0 ; d < 10 ; d++)
      for(int e = 0 ; e <= 10 ; e++)
	for(int f = 0 ; f <= 10 ; f++)
	  if(d != e and d != f)
	    dp[c][f][(f==10 and d==0)?10:d] += dp[c-1][e][f];
  ll ret = 0;
  for(int c = 0 ; c <= 10 ; c++)
    for(int d = 0 ; d <= 10 ; d++)
      ret += dp[N][c][d];
  return ret;
}

ll solv(ll x){
  // printf(":%d\n",x);
  if(x == -1)return 0;
  if(x == 0)return 1;
  ll ret = 0;
  char a[20];
  N = -1;
  while(x > 0)
    a[++N] = x%10, x /= 10;
  a[N+1] = 10, a[N+2] = 11;

  for(int c = N, st = 0 ; c >= 0 ; c--, st++){
    for(int d = 0 ; d <= N ; d++)
      for(int e = 0 ; e <= 11 ; e++)
	for(int f = 0 ; f <= 11 ; f++)
	  dp[d][e][f] = 0;
    for(int d = 0 ; d < a[c] ; d++)
      if(d != a[c+1] and d != a[c+2])
	dp[st][a[c+1]][(c == N and d==0)?10:d] = 1;
    ret += kat(st);
    // printf("%d %d %d :%lld\n",st,a[c+1],a[c],ret);
    if(a[c] == a[c+1] or a[c] == a[c+2])
      break;
  }
  // printf("------------\n");

  bool ok = true;
  for(int c = N ; c >= 0 ; c--)
    if(a[c] == a[c+1] or a[c] == a[c+2])
      ok = false;
  if(ok and N >= 0)
    ret++;
  return ret;
}

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

Compilation message (stderr)

numbers.cpp: In function 'long long int solv(long long int)':
numbers.cpp:43:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |  dp[st][a[c+1]][(c == N and d==0)?10:d] = 1;
      |         ~~~~~^
numbers.cpp: In function 'int main()':
numbers.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%lld %lld",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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