| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 656438 | 2022-11-07T13:25:54 Z | 600Mihnea | Sequence (BOI14_sequence) | C++17 | 189 ms | 1236 KB |
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;
ll solve(vector<int> restrictions, int suf_9, bool only_0) {
int n = (int) restrictions.size();
assert(n >= 1);
///cout << "\t\t\t\t\tn = " << n << "\n";
if (n == 1) {
if (restrictions[0] == 0) {
/// 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);
for (int i = 0; i < n; i++) {
int what_digit = (last_digit + i) % 10;
int val = restrictions[i];
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;
}
ll x = solve(new_restrictions, (suf_9 + 1) * (last_digit == 9 && (int) new_restrictions.size() == (int) restrictions.size()), (last_digit == 0));
/*if ((int) restrictions.size() == 1000 && last_digit == 9) {
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";
}
}*/
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);
}
ll sol = solve(restrictions, 0, 1);
cout << sol << "\n";
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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 22 ms | 416 KB | Output is correct |
| 3 | Correct | 21 ms | 340 KB | Output is correct |
| 4 | Correct | 17 ms | 340 KB | Output is correct |
| 5 | Correct | 18 ms | 340 KB | Output is correct |
| 6 | Correct | 20 ms | 328 KB | Output is correct |
| 7 | Correct | 140 ms | 1048 KB | Output is correct |
| 8 | Correct | 88 ms | 804 KB | Output is correct |
| 9 | Correct | 187 ms | 1236 KB | Output is correct |
| 10 | Correct | 189 ms | 1236 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |