bool home = 0;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
fix the last digit of our number
**/
const ll INF = (ll) 1e18 + 7;
vector<int> guy, guy2, guy3;
int cnt;
ll solve(vector<int> restrictions, int suf_9, bool only_0) {
int n = (int) restrictions.size();
/// if all have 0 restrictions => return 0
bool all_0 = 1;
for (auto &x : restrictions) {
all_0 &= (x == 0);
}
if (all_0) {
return 0;
}
if (n == 2 && restrictions[0] == 0) {
assert(restrictions[1] >= 1);
/// our number needs to have some digits
if (restrictions[1] == (1 << 0)) {
/// our number needs to have only the digit 0
return 10 - 1; /// special case because it can't start with 0
}
ll sol = 0;
for (int d = 1; d <= 9; d++) {
if (restrictions[1] & (1 << d)) {
restrictions[1] ^= (1 << d);
sol = 10 * sol + d;
break;
}
}
if (restrictions[1] & (1 << 0)) {
sol = 10 * sol + 0;
restrictions[1] ^= (1 << 0);
}
for (int d = 1; d <= 9; d++) {
if (restrictions[1] & (1 << d)) {
restrictions[1] ^= (1 << d);
sol = 10 * sol + d;
}
}
assert(restrictions[1] == 0);
assert(sol - 1 >= 0);
return sol - 1;
}
assert(n >= 1);
///cout << "\t\t\t\t\tn = " << n << "\n";
if (n == 1) {
if (restrictions[0] == 0) {
return 1;
/// return 1;
if (!only_0) {
return 1;
} else {
return 0;
}
}
/// our number needs to have some digits
if (restrictions[0] == (1 << 0)) {
/// our number needs to have only the digit 0
return 10; /// special case because it can't start with 0
}
ll sol = 0;
for (int d = 1; d <= 9; d++) {
if (restrictions[0] & (1 << d)) {
restrictions[0] ^= (1 << d);
sol = 10 * sol + d;
break;
}
}
if (restrictions[0] & (1 << 0)) {
sol = 10 * sol + 0;
restrictions[0] ^= (1 << 0);
}
for (int d = 1; d <= 9; d++) {
if (restrictions[0] & (1 << d)) {
restrictions[0] ^= (1 << d);
sol = 10 * sol + d;
}
}
assert(restrictions[0] == 0);
return sol;
}
assert(n >= 2);
ll sol = INF;
/// T(N) = 10 * T(N / 10) + N => N * log(N) from master theorem (I don't know if log2(N)) or log10(N) but I assume it
/// is more likely to be log10(N), but nevertheless it intuitively makes sense why it's fast.
for (int last_digit = 0; last_digit <= 9; last_digit++) {
vector<int> new_restrictions((last_digit + n - 1) / 10 + 1, 0);
vector<int> nor((last_digit + n - 1) / 10 + 1, 0);
for (int i = 0; i < n; i++) {
int what_digit = (last_digit + i) % 10;
int val = restrictions[i];
nor[(last_digit + i) / 10] |= val;
if (val & (1 << what_digit)) {
val -= (1 << what_digit);
}
new_restrictions[(last_digit + i) / 10] |= val;
/// (last_digit + i) / 10
}
if ((int)restrictions.size() == 2 && (int) new_restrictions.size() == 2 && last_digit == 9 && suf_9 >= 2) {
continue;
}
if ((int) restrictions.size() == 1000 && last_digit == 9) {
guy = new_restrictions;
cnt++;
}
if (restrictions == guy && last_digit == 9) {
guy2 = new_restrictions;
}
if (restrictions == guy2 && last_digit == 9) {
guy3 = new_restrictions;
}
ll x = solve(new_restrictions, (suf_9 + 1) * (last_digit == 9 && (int) new_restrictions.size() == (int) restrictions.size()), only_0 | (last_digit > 0));
if (x == 0 && last_digit == 0 && (nor[0] & (1 << 0))) {
x = 1;
}
/**if (restrictions == vector<int> {1 << 0, 1 << 1} && last_digit == 0) {
/// assert((int) new_restrictions.size() == 2);
cout << "last_digit = " << last_digit << "\n";
for (int i = 0; i < (int) new_restrictions.size(); i++) {
cout << i << " : ";
for (int dig = 0; dig <= 9; dig++) {
if (new_restrictions[i] & (1 << dig)) {
cout << dig << " ";
}
}
cout << "\n";
}
// cout << new_restrictions[0] << "\n";
// cout << " x = " << x << "\n";
}**/
sol = min(sol, x * 10 + last_digit);
}
return sol;
}
signed main() {
if (home == 0) {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
} else {
freopen ("___input___.txt", "r", stdin);
}
int n;
cin >> n;
vector<int> restrictions(n, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
assert(0 <= x && x < 10);
restrictions[i] |= (1 << x);
}
/// restrictions = {(1 << 0), (1 << 1)};
ll sol = solve(restrictions, 0, 0);
cout << sol << "\n";
///assert(cnt == 1);
return 0;
}
/**
N has digit d[0]
N + 1 has digit d[1]
...
N + i has digit d[i]
N + (K - 1)
what is the smallest possible value of N?
give just a possible value of N, not the smallest one
N = 12345678900000000 is a valid solution
N + 1 = 12345678900000001
N + 2 = 12345678900000002
...
what are the last log10(N) digits?
N = -----.-----A
N + k - 1 = -----.-----B
with B = A + k - 1 and A, B have the same number of digits
K = 10
A = 00000004
B = 00000013
N = CA
N + k - 1 = CB
with B = A + k - 1
fix the digits in C in o(2^10)
and after that we have just some restrictions (because we covered some)
restriction of form N + i has digit d[i]
**/
Compilation message
sequence.cpp: In function 'int main()':
sequence.cpp:154:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | freopen ("___input___.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 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 |
212 KB |
Output is correct |
8 |
Correct |
3 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
324 KB |
Output is correct |
10 |
Correct |
3 ms |
324 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
3 ms |
328 KB |
Output is correct |
15 |
Correct |
3 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 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 |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
3 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
5 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
4 ms |
212 KB |
Output is correct |
12 |
Correct |
3 ms |
212 KB |
Output is correct |
13 |
Correct |
3 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
4 ms |
328 KB |
Output is correct |
17 |
Correct |
3 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
2 ms |
244 KB |
Output is correct |
20 |
Correct |
3 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
3 ms |
324 KB |
Output is correct |
23 |
Correct |
3 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
11 ms |
416 KB |
Output is correct |
3 |
Correct |
12 ms |
340 KB |
Output is correct |
4 |
Correct |
24 ms |
340 KB |
Output is correct |
5 |
Correct |
25 ms |
340 KB |
Output is correct |
6 |
Correct |
24 ms |
392 KB |
Output is correct |
7 |
Correct |
218 ms |
948 KB |
Output is correct |
8 |
Correct |
46 ms |
732 KB |
Output is correct |
9 |
Correct |
254 ms |
1236 KB |
Output is correct |
10 |
Correct |
316 ms |
1232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 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 |
145 ms |
724 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
2 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
3 ms |
212 KB |
Output is correct |
11 |
Correct |
264 ms |
1428 KB |
Output is correct |
12 |
Correct |
212 ms |
1424 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
3 ms |
328 KB |
Output is correct |
15 |
Correct |
2 ms |
212 KB |
Output is correct |
16 |
Correct |
5 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
2 ms |
328 KB |
Output is correct |
19 |
Correct |
4 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
324 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
2 ms |
320 KB |
Output is correct |
23 |
Correct |
3 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
3 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
332 KB |
Output is correct |
27 |
Correct |
11 ms |
336 KB |
Output is correct |
28 |
Correct |
11 ms |
340 KB |
Output is correct |
29 |
Correct |
26 ms |
340 KB |
Output is correct |
30 |
Correct |
27 ms |
340 KB |
Output is correct |
31 |
Correct |
23 ms |
340 KB |
Output is correct |
32 |
Correct |
185 ms |
1112 KB |
Output is correct |
33 |
Correct |
64 ms |
724 KB |
Output is correct |
34 |
Correct |
287 ms |
1428 KB |
Output is correct |
35 |
Correct |
269 ms |
1352 KB |
Output is correct |
36 |
Correct |
202 ms |
1120 KB |
Output is correct |
37 |
Correct |
246 ms |
1400 KB |
Output is correct |
38 |
Correct |
153 ms |
852 KB |
Output is correct |
39 |
Correct |
242 ms |
1424 KB |
Output is correct |
40 |
Correct |
251 ms |
1436 KB |
Output is correct |