Submission #656448

#	Time	Username	Problem	Language	Result	Execution time	Memory
656448		600Mihnea	Sequence (BOI14_sequence)	C++17	100 / 100	316 ms	1436 KiB

sequence

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 (stderr)

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);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33