답안 #736223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736223	2023-05-05T10:35:40 Z	sleepntsheep	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	420 KB

numbers

/*
TASK: 6mar_palindromefree
LANG: C
*/
#include <stdio.h>
#include <string.h>

typedef long long s64;

/* pos, second last char, last char, is palindrome, less than flag, in leading zero */
s64 dp[20][11][11][2][2][2], a, b;
char s[20];

s64 rcs(int pos, int l2, int l1, int pal, int f2, int lz)
{
    s64 &d = dp[pos][l2][l1][pal][f2][lz];
    if (-1 != d) return d;
    if (!s[pos]) return d = pal;
    d = 0;
    for (int i = 0; i <= (f2 ? 9 : s[pos] - '0'); ++i)
    {
        int nlz = lz ? !i : 0;
        int nl2 = nlz ? 10 : l1, nl1 = nlz ? 10 : i;
        d += rcs(pos+1, nl2, nl1, pal || (!lz && (l1 == i || l2 == i)), f2 || (i < s[pos] - '0'), nlz);
    }
    return d;
}

s64 solve(s64 num)
{
    memset(dp, -1, sizeof dp);
    snprintf(s, sizeof s, "%018lld", num);
    return rcs(0, 10, 10, 0, 0, 1);
}

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

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld%lld", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	416 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	412 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	416 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	416 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct

Subtask #2

75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	420 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	416 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	416 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	416 KB	Output is correct
23	Correct	1 ms	416 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	416 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	416 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	416 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	340 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	1 ms	416 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	1 ms	340 KB	Output is correct
44	Correct	1 ms	340 KB	Output is correct
45	Correct	1 ms	340 KB	Output is correct