oj.uz

Submission #656426

# Submission time Handle Problem Language Result Execution time Memory
656426 2022-11-07T13:10:27 Z 600Mihnea Sequence (BOI14_sequence) C++17
25 / 100
 197 ms 1364 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) {
  int n = (int) restrictions.size();
  assert(n >= 1);
  ///cout << "\t\t\t\t\tn = " << n << "\n";
  if (n == 1) {
    /// 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()));

    if (last_digit == 0 && x == 0) {
      x++;
    }
    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);
  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

sequence.cpp: In function 'int main()':
sequence.cpp:79:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 24 ms 468 KB Output is correct
3 Correct 23 ms 340 KB Output is correct
4 Correct 18 ms 340 KB Output is correct
5 Correct 18 ms 340 KB Output is correct
6 Correct 16 ms 468 KB Output is correct
7 Correct 154 ms 1068 KB Output is correct
8 Correct 93 ms 724 KB Output is correct
9 Correct 191 ms 1364 KB Output is correct
10 Correct 197 ms 1308 KB Output is correct

Subtask #4
0 / 33.0

# 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 -