# weekly-contest-306

## A

### Statement

• `maxLocal[i][j]` 等于 `grid` 中以 `i + 1` 行和 `j + 1` 列为中心的 `3 x 3` 矩阵中的 最大值

``````输入：grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]

``````输入：grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]

``````

• `n == grid.length == grid[i].length`
• `3 <= n <= 100`
• `1 <= grid[i][j] <= 100`

You are given an `n x n` integer matrix `grid`.

Generate an integer matrix `maxLocal` of size `(n - 2) x (n - 2)` such that:

• `maxLocal[i][j]` is equal to the largest value of the `3 x 3` matrix in `grid` centered around row `i + 1` and column `j + 1`.

In other words, we want to find the largest value in every contiguous `3 x 3` matrix in `grid`.

Return the generated matrix.

Example 1:

``````Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output: [[9,9],[8,6]]
Explanation: The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.``````

Example 2:

``````Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
Output: [[2,2,2],[2,2,2],[2,2,2]]
Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.
``````

Constraints:

• `n == grid.length == grid[i].length`
• `3 <= n <= 100`
• `1 <= grid[i][j] <= 100`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
vector<vector<int>> largestLocal(vector<vector<int>> &grid) {
int n = int(grid.size());
int m = n - 2;
auto res = vector<vector<int>>(m, vector<int>(m, 0));
for (int i = 0; i < n - 2; i++) {
for (int j = 0; j < n - 2; j++) {
int max_ = 0;
for (int k = 0; k < 3; k++) {
for (int l = 0; l < 3; l++) {
max_ = max(max_, grid[i + k][j + l]);
}
}
res[i][j] = max_;
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：edges = [1,0,0,0,0,7,7,5]

- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。

``````

``````输入：edges = [2,0,0,2]

- 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。
- 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。

``````

• `n == edges.length`
• `2 <= n <= 105`
• `0 <= edges[i] < n`
• `edges[i] != i`

You are given a directed graph with `n` nodes labeled from `0` to `n - 1`, where each node has exactly one outgoing edge.

The graph is represented by a given 0-indexed integer array `edges` of length `n`, where `edges[i]` indicates that there is a directed edge from node `i` to node `edges[i]`.

The edge score of a node `i` is defined as the sum of the labels of all the nodes that have an edge pointing to `i`.

Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.

Example 1:

``````Input: edges = [1,0,0,0,0,7,7,5]
Output: 7
Explanation:
- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.
- The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
- The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
- The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11.
Node 7 has the highest edge score so return 7.
``````

Example 2:

``````Input: edges = [2,0,0,2]
Output: 0
Explanation:
- The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
- The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3.
Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.
``````

Constraints:

• `n == edges.length`
• `2 <= n <= 105`
• `0 <= edges[i] < n`
• `edges[i] != i`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int edgeScore(vector<int> &edges) {
int n = int(edges.size());
ll _max = 0;
int res = -1;

auto f = vector<ll>(n, 0);
for (int i = 0; i < n; i++) {
int x = edges[i];
f[x] += i;
}

for (int i = 0; i < n; i++) {
if (f[i] > _max) {
_max = f[i];
res = i;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• `num` 包含数字 `'1'` 到 `'9'` ，其中每个数字 至多 使用一次。
• 如果 `pattern[i] == 'I'` ，那么 `num[i] < num[i + 1]` 。
• 如果 `pattern[i] == 'D'` ，那么 `num[i] > num[i + 1]` 。

``````输入：pattern = "IIIDIDDD"

"123549876" 是满足条件最小的数字。

``````输入：pattern = "DDD"

"4321" 是满足条件最小的数字。
``````

• `1 <= pattern.length <= 8`
• `pattern` 只包含字符 `'I'` 和 `'D'`

You are given a 0-indexed string `pattern` of length `n` consisting of the characters `'I'` meaning increasing and `'D'` meaning decreasing.

A 0-indexed string `num` of length `n + 1` is created using the following conditions:

• `num` consists of the digits `'1'` to `'9'`, where each digit is used at most once.
• If `pattern[i] == 'I'`, then `num[i] < num[i + 1]`.
• If `pattern[i] == 'D'`, then `num[i] > num[i + 1]`.

Return the lexicographically smallest possible string `num` that meets the conditions.

Example 1:

``````Input: pattern = "IIIDIDDD"
Output: "123549876"
Explanation:
At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1].
At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1].
Some possible values of num are "245639871", "135749862", and "123849765".
It can be proven that "123549876" is the smallest possible num that meets the conditions.
Note that "123414321" is not possible because the digit '1' is used more than once.``````

Example 2:

``````Input: pattern = "DDD"
Output: "4321"
Explanation:
Some possible values of num are "9876", "7321", and "8742".
It can be proven that "4321" is the smallest possible num that meets the conditions.
``````

Constraints:

• `1 <= pattern.length <= 8`
• `pattern` consists of only the letters `'I'` and `'D'`.

### Solution

``````#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
string smallestNumber(string pattern) {
int n = int(pattern.size()) + 1;
auto f = vector<int>(n, 0);
for (int i = 1; i <= n; i++) {
f[i - 1] = i;
}

string res = "";

for (int i = n - 1; i >= 0; i--) {
res += to_string(i + 1);
}

do {
bool ok = true;
for (int i = 0; i < n - 1; i++) {
if (pattern[i] == 'I') {
if (f[i] > f[i + 1]) {
ok = false;
break;
}
} else {
if (f[i] < f[i + 1]) {
ok = false;
break;
}
}
}

if (ok) {
string _res = "";
for (const auto &i : f) {
_res += to_string(i);
}
res = min(res, _res);
break;
}
} while (next_permutation(f.begin(), f.end()));

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

``````输入：n = 20

``````

``````输入：n = 5

``````

``````输入：n = 135

• `1 <= n <= 2 * 109`

We call a positive integer special if all of its digits are distinct.

Given a positive integer `n`, return the number of special integers that belong to the interval `[1, n]`.

Example 1:

``````Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
``````

Example 2:

``````Input: n = 5
Output: 5
Explanation: All the integers from 1 to 5 are special.
``````

Example 3:

``````Input: n = 135
Output: 110
Explanation: There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.``````

Constraints:

• `1 <= n <= 2 * 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
// #include <debug.hpp>
#else
#define dbg(...)
#endif

bool ok(int x) {
auto f = vector<int>(10, 0);

while (x) {
int y = x % 10;
++f[y];
if (f[y] > 1) {
return false;
}

x /= 10;
}

return true;
}

class Solution {
public:
inline static int f[] = {0, 168570, 229050, 289530, 350010, 410490, 470970, 531450, 591930, 652410, 712890, 733050,
733050, 753210, 773370, 793530, 813690, 833850, 854010, 874170, 894330, 914490, 934650, 934650, 954810,
974970, 995130, 1015290, 1035450, 1055610, 1075770, 1095930, 1116090, 1136250, 1136250, 1156410, 1176570,
1196730, 1216890, 1237050, 1257210, 1277370, 1297530, 1317690, 1337850, 1337850, 1358010, 1378170, 1398330,
1418490, 1438650, 1458810, 1478970, 1499130, 1519290, 1539450, 1539450, 1559610, 1579770, 1599930, 1620090,
1640250, 1660410, 1680570, 1700730, 1720890, 1741050, 1741050, 1761210, 1781370, 1801530, 1821690, 1841850,
1862010, 1882170, 1902330, 1922490, 1942650, 1942650, 1962810, 1982970, 2003130, 2023290, 2043450, 2063610,
2083770, 2103930, 2124090, 2144250, 2144250, 2164410, 2184570, 2204730, 2224890, 2245050, 2265210, 2285370,
2305530, 2325690, 2345850, 2345850, 2345850, 2345850, 2350890, 2355930, 2360970, 2366010, 2371050, 2376090,
2381130, 2386170, 2386170, 2386170, 2386170, 2386170, 2386170, 2386170, 2386170, 2386170, 2386170, 2386170,
2391210, 2391210, 2391210, 2396250, 2401290, 2406330, 2411370, 2416410, 2421450, 2426490, 2431530, 2431530,
2436570, 2436570, 2441610, 2446650, 2451690, 2456730, 2461770, 2466810, 2471850, 2471850, 2476890, 2481930,
2481930, 2486970, 2492010, 2497050, 2502090, 2507130, 2512170, 2512170, 2517210, 2522250, 2527290, 2527290,
2532330, 2537370, 2542410, 2547450, 2552490, 2552490, 2557530, 2562570, 2567610, 2572650, 2572650, 2577690,
2582730, 2587770, 2592810, 2592810, 2597850, 2602890, 2607930, 2612970, 2618010, 2618010, 2623050, 2628090,
2633130, 2633130, 2638170, 2643210, 2648250, 2653290, 2658330, 2663370, 2663370, 2668410, 2673450, 2673450,
2678490, 2683530, 2688570, 2693610, 2698650, 2703690, 2708730, 2708730, 2708730, 2713770, 2713770, 2718810,
2723850, 2728890, 2733930, 2738970, 2744010, 2749050, 2754090, 2754090, 2754090, 2759130, 2764170, 2769210,
2774250, 2779290, 2784330, 2789370, 2789370, 2789370, 2789370, 2789370, 2789370, 2789370, 2789370, 2789370,
2789370, 2789370, 2794410, 2799450, 2799450, 2799450, 2804490, 2809530, 2814570, 2819610, 2824650, 2829690,
2834730, 2839770, 2839770, 2844810, 2844810, 2849850, 2854890, 2859930, 2864970, 2870010, 2875050, 2880090,
2880090, 2885130, 2890170, 2890170, 2895210, 2900250, 2905290, 2910330, 2915370, 2920410, 2920410, 2925450,
2930490, 2935530, 2935530, 2940570, 2945610, 2950650, 2955690, 2960730, 2960730, 2965770, 2970810, 2975850,
2980890, 2980890, 2985930, 2990970, 2996010, 3001050, 3001050, 3006090, 3011130, 3016170, 3021210, 3026250,
3026250, 3031290, 3036330, 3041370, 3041370, 3046410, 3051450, 3056490, 3061530, 3066570, 3071610, 3071610,
3071610, 3076650, 3081690, 3081690, 3086730, 3091770, 3096810, 3101850, 3106890, 3111930, 3116970, 3116970,
3122010, 3122010, 3127050, 3132090, 3137130, 3142170, 3147210, 3152250, 3157290, 3162330, 3162330, 3162330,
3167370, 3172410, 3177450, 3182490, 3187530, 3192570, 3192570, 3192570, 3192570, 3192570, 3192570, 3192570,
3192570, 3192570, 3192570, 3192570, 3197610, 3202650, 3207690, 3207690, 3207690, 3212730, 3217770, 3222810,
3227850, 3232890, 3237930, 3242970, 3248010, 3248010, 3253050, 3253050, 3258090, 3263130, 3268170, 3273210,
3278250, 3283290, 3288330, 3288330, 3293370, 3298410, 3298410, 3303450, 3308490, 3313530, 3318570, 3323610,
3328650, 3328650, 3333690, 3338730, 3343770, 3343770, 3348810, 3353850, 3358890, 3363930, 3368970, 3368970,
3374010, 3379050, 3384090, 3389130, 3389130, 3394170, 3399210, 3404250, 3409290, 3409290, 3414330, 3419370,
3424410, 3429450, 3434490, 3434490, 3434490, 3439530, 3444570, 3449610, 3449610, 3454650, 3459690, 3464730,
3469770, 3474810, 3479850, 3479850, 3484890, 3489930, 3489930, 3494970, 3500010, 3505050, 3510090, 3515130,
3520170, 3525210, 3525210, 3530250, 3530250, 3535290, 3540330, 3545370, 3550410, 3555450, 3560490, 3565530,
3570570, 3570570, 3570570, 3575610, 3580650, 3585690, 3590730, 3595770, 3595770, 3595770, 3595770, 3595770,
3595770, 3595770, 3595770, 3595770, 3595770, 3595770, 3600810, 3605850, 3610890, 3615930, 3615930, 3615930,
3620970, 3626010, 3631050, 3636090, 3641130, 3646170, 3651210, 3656250, 3656250, 3661290, 3661290, 3666330,
3671370, 3676410, 3681450, 3686490, 3691530, 3696570, 3696570, 3701610, 3706650, 3706650, 3711690, 3716730,
3721770, 3726810, 3731850, 3736890, 3736890, 3741930, 3746970, 3752010, 3752010, 3757050, 3762090, 3767130,
3772170, 3777210, 3777210, 3782250, 3787290, 3792330, 3797370, 3797370, 3797370, 3802410, 3807450, 3812490,
3817530, 3817530, 3822570, 3827610, 3832650, 3837690, 3842730, 3842730, 3847770, 3852810, 3857850, 3857850,
3862890, 3867930, 3872970, 3878010, 3883050, 3888090, 3888090, 3893130, 3898170, 3898170, 3903210, 3908250,
3913290, 3918330, 3923370, 3928410, 3933450, 3933450, 3938490, 3938490, 3943530, 3948570, 3953610, 3958650,
3963690, 3968730, 3973770, 3978810, 3978810, 3978810, 3983850, 3988890, 3993930, 3998970, 3998970, 3998970,
3998970, 3998970, 3998970, 3998970, 3998970, 3998970, 3998970, 3998970, 4004010, 4009050, 4014090, 4019130,
4024170, 4024170, 4024170, 4029210, 4034250, 4039290, 4044330, 4049370, 4054410, 4059450, 4064490, 4064490,
4069530, 4069530, 4074570, 4079610, 4084650, 4089690, 4094730, 4099770, 4104810, 4104810, 4109850, 4114890,
4114890, 4119930, 4124970, 4130010, 4135050, 4140090, 4145130, 4145130, 4150170, 4155210, 4160250, 4160250,
4160250, 4165290, 4170330, 4175370, 4180410, 4185450, 4185450, 4190490, 4195530, 4200570, 4205610, 4205610,
4210650, 4215690, 4220730, 4225770, 4225770, 4230810, 4235850, 4240890, 4245930, 4250970, 4250970, 4256010,
4261050, 4266090, 4266090, 4271130, 4276170, 4281210, 4286250, 4291290, 4296330, 4296330, 4301370, 4306410,
4306410, 4311450, 4316490, 4321530, 4326570, 4331610, 4336650, 4341690, 4341690, 4346730, 4346730, 4351770,
4356810, 4361850, 4366890, 4371930, 4376970, 4382010, 4387050, 4387050, 4387050, 4392090, 4397130, 4402170,
4402170, 4402170, 4402170, 4402170, 4402170, 4402170, 4402170, 4402170, 4402170, 4402170, 4407210, 4412250,
4417290, 4422330, 4427370, 4432410, 4432410, 4432410, 4437450, 4442490, 4447530, 4452570, 4457610, 4462650,
4467690, 4472730, 4472730, 4477770, 4477770, 4482810, 4487850, 4492890, 4497930, 4502970, 4508010, 4513050,
4513050, 4518090, 4523130, 4523130, 4523130, 4528170, 4533210, 4538250, 4543290, 4548330, 4553370, 4553370,
4558410, 4563450, 4568490, 4568490, 4573530, 4578570, 4583610, 4588650, 4593690, 4593690, 4598730, 4603770,
4608810, 4613850, 4613850, 4618890, 4623930, 4628970, 4634010, 4634010, 4639050, 4644090, 4649130, 4654170,
4659210, 4659210, 4664250, 4669290, 4674330, 4674330, 4679370, 4684410, 4689450, 4694490, 4699530, 4704570,
4704570, 4709610, 4714650, 4714650, 4719690, 4724730, 4729770, 4734810, 4739850, 4744890, 4749930, 4749930,
4754970, 4754970, 4760010, 4765050, 4770090, 4775130, 4780170, 4785210, 4790250, 4795290, 4795290, 4795290,
4800330, 4805370, 4805370, 4805370, 4805370, 4805370, 4805370, 4805370, 4805370, 4805370, 4805370, 4805370,
4810410, 4815450, 4820490, 4825530, 4830570, 4835610, 4840650, 4840650, 4840650, 4845690, 4850730, 4855770,
4860810, 4865850, 4870890, 4875930, 4880970, 4880970, 4886010, 4886010, 4886010, 4891050, 4896090, 4901130,
4906170, 4911210, 4916250, 4921290, 4921290, 4926330, 4931370, 4931370, 4936410, 4941450, 4946490, 4951530,
4956570, 4961610, 4961610, 4966650, 4971690, 4976730, 4976730, 4981770, 4986810, 4991850, 4996890, 5001930,
5001930, 5006970, 5012010, 5017050, 5022090, 5022090, 5027130, 5032170, 5037210, 5042250, 5042250, 5047290,
5052330, 5057370, 5062410, 5067450, 5067450, 5072490, 5077530, 5082570, 5082570, 5087610, 5092650, 5097690,
5102730, 5107770, 5112810, 5112810, 5117850, 5122890, 5122890, 5127930, 5132970, 5138010, 5143050, 5148090,
5153130, 5158170, 5158170, 5163210, 5163210, 5168250, 5173290, 5178330, 5183370, 5188410, 5193450, 5198490,
5203530, 5203530, 5203530, 5208570, 5208570, 5208570, 5208570, 5208570, 5208570, 5208570, 5208570, 5208570,
5208570, 5208570, 5213610, 5218650, 5223690, 5228730, 5233770, 5238810, 5243850, 5248890, 5248890, 5248890,
5248890, 5253930, 5258970, 5264010, 5269050, 5274090, 5279130, 5284170, 5289210, 5289210, 5294250, 5294250,
5299290, 5304330, 5309370, 5314410, 5319450, 5324490, 5329530, 5329530, 5334570, 5339610, 5339610, 5344650,
5349690, 5354730, 5359770, 5364810, 5369850, 5369850, 5374890, 5379930, 5384970, 5384970, 5390010, 5395050,
5400090, 5405130, 5410170, 5410170, 5415210, 5420250, 5425290, 5430330, 5430330, 5435370, 5440410, 5445450,
5450490, 5450490, 5455530, 5460570, 5465610, 5470650, 5475690, 5475690, 5480730, 5485770, 5490810, 5490810,
5495850, 5500890, 5505930, 5510970, 5516010, 5521050, 5521050, 5526090, 5531130, 5531130, 5536170, 5541210,
5546250, 5551290, 5556330, 5561370, 5566410, 5566410, 5571450, 5571450, 5576490, 5581530, 5586570, 5591610,
5596650, 5601690, 5606730, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770,
5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770,
5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770, 5611770,
5611770, 5611770, 5611770, 5612490, 5613210, 5613930, 5614650, 5615370, 5616090, 5616810, 5616810, 5616810,
5617530, 5617530, 5618250, 5618970, 5619690, 5620410, 5621130, 5621850, 5621850, 5621850, 5622570, 5623290,
5623290, 5624010, 5624730, 5625450, 5626170, 5626890, 5626890, 5626890, 5627610, 5628330, 5629050, 5629050,
5629770, 5630490, 5631210, 5631930, 5631930, 5631930, 5632650, 5633370, 5634090, 5634810, 5634810, 5635530,
5636250, 5636970, 5636970, 5636970, 5637690, 5638410, 5639130, 5639850, 5640570, 5640570, 5641290, 5642010,
5642010, 5642010, 5642730, 5643450, 5644170, 5644890, 5645610, 5646330, 5646330, 5647050, 5647050, 5647050,
5647770, 5648490, 5649210, 5649930, 5650650, 5651370, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090, 5652090,
5652090, 5652090, 5652090, 5652810, 5653530, 5654250, 5654970, 5655690, 5656410, 5657130, 5657130, 5657130,
5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657130,
5657130, 5657130, 5657130, 5657130, 5657130, 5657130, 5657850, 5657850, 5657850, 5657850, 5658570, 5659290,
5660010, 5660730, 5661450, 5662170, 5662890, 5662890, 5662890, 5663610, 5663610, 5664330, 5665050, 5665770,
5666490, 5667210, 5667930, 5667930, 5667930, 5668650, 5669370, 5669370, 5670090, 5670810, 5671530, 5672250,
5672970, 5672970, 5672970, 5673690, 5674410, 5675130, 5675130, 5675850, 5676570, 5677290, 5678010, 5678010,
5678010, 5678730, 5679450, 5680170, 5680890, 5680890, 5681610, 5682330, 5683050, 5683050, 5683050, 5683770,
5684490, 5685210, 5685930, 5686650, 5686650, 5687370, 5688090, 5688090, 5688090, 5688810, 5689530, 5690250,
5690970, 5691690, 5692410, 5692410, 5692410, 5692410, 5693130, 5693130, 5693850, 5694570, 5695290, 5696010,
5696730, 5697450, 5697450, 5697450, 5697450, 5697450, 5697450, 5697450, 5697450, 5697450, 5697450, 5697450,
5698170, 5698170, 5698170, 5698170, 5698890, 5699610, 5700330, 5701050, 5701770, 5702490, 5702490, 5702490,
5702490, 5702490, 5702490, 5702490, 5702490, 5702490, 5702490, 5702490, 5703210, 5703210, 5703930, 5703930,
5703930, 5704650, 5705370, 5706090, 5706810, 5707530, 5708250, 5708250, 5708970, 5708970, 5709690, 5709690,
5710410, 5711130, 5711850, 5712570, 5713290, 5713290, 5714010, 5714010, 5714730, 5715450, 5715450, 5716170,
5716890, 5717610, 5718330, 5718330, 5719050, 5719050, 5719770, 5720490, 5721210, 5721210, 5721930, 5722650,
5723370, 5723370, 5724090, 5724090, 5724810, 5725530, 5726250, 5726970, 5726970, 5727690, 5728410, 5728410,
5729130, 5729130, 5729850, 5730570, 5731290, 5732010, 5732730, 5732730, 5732730, 5732730, 5733450, 5734170,
5734170, 5734890, 5735610, 5736330, 5737050, 5737770, 5737770, 5737770, 5737770, 5737770, 5737770, 5737770,
5737770, 5737770, 5737770, 5737770, 5738490, 5738490, 5738490, 5739210, 5739210, 5739930, 5740650, 5741370,
5742090, 5742810, 5743530, 5743530, 5744250, 5744250, 5744250, 5744970, 5745690, 5746410, 5747130, 5747850,
5747850, 5747850, 5747850, 5747850, 5747850, 5747850, 5747850, 5747850, 5747850, 5747850, 5748570, 5748570,
5749290, 5750010, 5750010, 5750010, 5750730, 5751450, 5752170, 5752890, 5753610, 5753610, 5754330, 5755050,
5755050, 5755770, 5755770, 5756490, 5757210, 5757930, 5758650, 5758650, 5759370, 5760090, 5760090, 5760810,
5761530, 5761530, 5762250, 5762970, 5763690, 5763690, 5764410, 5765130, 5765130, 5765850, 5766570, 5767290,
5767290, 5768010, 5768730, 5768730, 5769450, 5770170, 5770170, 5770890, 5771610, 5772330, 5773050, 5773050,
5773050, 5773050, 5773770, 5774490, 5775210, 5775210, 5775930, 5776650, 5777370, 5778090, 5778090, 5778090,
5778090, 5778090, 5778090, 5778090, 5778090, 5778090, 5778090, 5778090, 5778810, 5778810, 5778810, 5779530,
5780250, 5780250, 5780970, 5781690, 5782410, 5783130, 5783850, 5783850, 5784570, 5784570, 5785290, 5785290,
5786010, 5786730, 5787450, 5788170, 5788890, 5788890, 5789610, 5790330, 5790330, 5790330, 5791050, 5791770,
5792490, 5793210, 5793210, 5793210, 5793210, 5793210, 5793210, 5793210, 5793210, 5793210, 5793210, 5793210,
5793930, 5793930, 5794650, 5795370, 5796090, 5796090, 5796090, 5796810, 5797530, 5798250, 5798970, 5798970,
5799690, 5800410, 5801130, 5801130, 5801850, 5801850, 5802570, 5803290, 5804010, 5804010, 5804730, 5805450,
5806170, 5806170, 5806890, 5807610, 5807610, 5808330, 5809050, 5809050, 5809770, 5810490, 5811210, 5811210,
5811930, 5812650, 5813370, 5813370, 5813370, 5813370, 5814090, 5814810, 5815530, 5816250, 5816250, 5816970,
5817690, 5818410, 5818410, 5818410, 5818410, 5818410, 5818410, 5818410, 5818410, 5818410, 5818410, 5818410,
5819130, 5819130, 5819130, 5819850, 5820570, 5821290, 5821290, 5822010, 5822730, 5823450, 5824170, 5824170,
5824890, 5824890, 5825610, 5826330, 5826330, 5827050, 5827770, 5828490, 5829210, 5829210, 5829930, 5830650,
5830650, 5831370, 5831370, 5832090, 5832810, 5833530, 5834250, 5834250, 5834970, 5835690, 5836410, 5836410,
5836410, 5837130, 5837850, 5838570, 5838570, 5838570, 5838570, 5838570, 5838570, 5838570, 5838570, 5838570,
5838570, 5838570, 5839290, 5839290, 5840010, 5840730, 5841450, 5842170, 5842170, 5842170, 5842890, 5843610,
5844330, 5844330, 5845050, 5845770, 5846490, 5847210, 5847210, 5847930, 5847930, 5848650, 5849370, 5849370,
5850090, 5850810, 5851530, 5852250, 5852250, 5852970, 5853690, 5853690, 5853690, 5853690, 5854410, 5855130,
5855850, 5856570, 5857290, 5857290, 5858010, 5858730, 5858730, 5858730, 5858730, 5858730, 5858730, 5858730,
5858730, 5858730, 5858730, 5858730, 5859450, 5859450, 5859450, 5860170, 5860890, 5861610, 5862330, 5862330,
5863050, 5863770, 5864490, 5864490, 5865210, 5865210, 5865930, 5866650, 5867370, 5867370, 5868090, 5868810,
5869530, 5869530, 5870250, 5870970, 5870970, 5871690, 5872410, 5872410, 5873130, 5873850, 5874570, 5874570,
5875290, 5876010, 5876730, 5876730, 5877450, 5877450, 5878170, 5878890, 5879610, 5879610, 5880330, 5881050,
5881770, 5882490, 5882490, 5882490, 5883210, 5883930, 5883930, 5883930, 5883930, 5883930, 5883930, 5883930,
5883930, 5883930, 5883930, 5883930, 5884650, 5884650, 5885370, 5886090, 5886810, 5887530, 5888250, 5888250,
5888250, 5888970, 5889690, 5889690, 5890410, 5891130, 5891850, 5892570, 5893290, 5893290, 5894010, 5894010,
5894010, 5894010, 5894730, 5895450, 5896170, 5896890, 5897610, 5898330, 5898330, 5899050, 5899050, 5899050,
5899050, 5899050, 5899050, 5899050, 5899050, 5899050, 5899050, 5899050, 5899770, 5899770, 5899770, 5900490,
5901210, 5901930, 5902650, 5903370, 5903370, 5904090, 5904810, 5904810, 5905530, 5905530, 5906250, 5906970,
5907690, 5908410, 5908410, 5909130, 5909850, 5909850, 5910570, 5911290, 5911290, 5912010, 5912730, 5913450,
5913450, 5914170, 5914890, 5914890, 5915610, 5916330, 5917050, 5917050, 5917770, 5918490, 5918490, 5919210,
5919930, 5919930, 5920650, 5921370, 5922090, 5922810, 5922810, 5923530, 5923530, 5924250, 5924970, 5924970,
5925690, 5926410, 5927130, 5927850, 5928570, 5928570, 5928570, 5929290, 5929290, 5929290, 5929290, 5929290,
5929290, 5929290, 5929290, 5929290, 5929290, 5929290, 5930010, 5930010, 5930730, 5931450, 5932170, 5932890,
5933610, 5934330, 5934330, 5934330, 5934330, 5934330, 5935050, 5935770, 5936490, 5937210, 5937930, 5938650,
5939370, 5939370, 5939370, 5939370, 5939370, 5939370, 5939370, 5939370, 5939370, 5939370, 5939370, 5939370,
5940090, 5940090, 5940090, 5940810, 5941530, 5942250, 5942970, 5943690, 5944410, 5944410, 5945130, 5945130,
5945850, 5945850, 5946570, 5947290, 5948010, 5948730, 5949450, 5949450, 5950170, 5950170, 5950890, 5951610,
5951610, 5952330, 5953050, 5953770, 5954490, 5954490, 5955210, 5955210, 5955930, 5956650, 5957370, 5957370,
5958090, 5958810, 5959530, 5959530, 5960250, 5960250, 5960970, 5961690, 5962410, 5963130, 5963130, 5963850,
5964570, 5964570, 5965290, 5965290, 5966010, 5966730, 5967450, 5968170, 5968890, 5968890, 5969610, 5969610,
5970330, 5970330, 5971050, 5971770, 5972490, 5973210, 5973930, 5974650, 5974650, 5974650, 5974650, 5974650,
5974650, 5974650, 5974650, 5974650, 5974650, 5974650, 5974650, 5974650};

int countSpecialNumbers(int n) {
int x = n / 1000000;
int res = f[x];

for (int i = 1000000 * x + 1; i <= n; i++) {
if (ok(i)) {
++res;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
int res = 0;
for (int i = 1, j = 1; i <= 2000000000; i++, j++) {
if (ok(i)) {
++res;
}

if (j == 1000000) {
j = 0;
cout << res << ",";
}
}

return 0;
}

#endif
``````

### Solution1

``````#include <bits/stdc++.h>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
// #include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int dp[20][2][2][2050];
bool init{false};

int dfs(int pos, int up, int pre_zero, int flag, vector<int> x) {
if (pos == 0) {
return !pre_zero;
}

int &res = dp[pos][up][pre_zero][flag];
if (res != -1) {
return res;
}

res = 0;

int current_up = x.back();
auto _x = x;
_x.pop_back();

for (int i = 0; i <= 9; i++) {
if (up && i > current_up) {
break;
}

int _flag = flag;
if (pre_zero && i == 0) {
} else {
_flag |= (1 << i);
if (_flag == flag) {
continue;
}
}

res += dfs(pos - 1, up && current_up == i, pre_zero && i == 0, _flag, _x);
}

return res;
}

int countSpecialNumbers(int n) {
if (!init) {
memset(dp, -1, sizeof dp);
init = true;
}

auto f = [](int x) {
int res = 0;
while (x) {
++res;
x /= 10;
}
return res;
};

auto g = [](int x) {
auto f = vector<int>();
while (x) {
f.push_back(x % 10);
x /= 10;
}
return f;
};

return dfs(f(n), 1, 1, 0, g(n));
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````