답안 #561872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
561872 2022-05-13T17:02:58 Z tj14 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
2 ms 340 KB
#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

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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 288 KB Output is correct
14 Correct 1 ms 284 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 1 ms 292 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 2 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 296 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 292 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 2 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 288 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 292 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct